Python 数据结构之栈和队列 —— （一）功能实现
Python 数据结构之栈和队列 —— （一）功能实现继前面链表的学习后，接着学习栈和队列这两种线性表。
链表的特点是灵活运用内存空间，对元素的操作不可直接读取，需要 next 的一个个找。
栈和队列也是特殊的线性表，其特点是限制插入和删除元素的操作，既可以基于顺序存储也可以基于链式存储。
栈
关键记住，后进先出（Last In First Out），简称为 LIFO 线性表，其操作均在一端实现。
栈的基本运算有六种：
构造空栈：InitStack(S)
判栈空：StackEmpty(S)
判栈满：StackFull(S)
进栈：Push(S, x)（可形象地理解为压入，这时栈中会多一个元素）
退栈：Pop(S)（可形象地理解为弹出，弹出后栈中就无此元素了）
取栈顶元素：StackTop(S)（与弹出不同，只是使用栈顶元素的值，该元素仍在栈顶不会改变）
由于栈也是线性表，因此线性表的存储结构对栈也适用。
通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。
关于顺序栈，需要了解 ‘上溢’ 和 ‘下溢’ 的概念。栈满时 push 就会上溢，栈空时 pop 就会下溢。与判栈满和判栈空关系紧密。
链栈由于没有存储空间限制，没有 ‘上溢’ 的限制，链栈只要有头指针即可操作，也十分方便。
队列
队列 (Queue) 也是一种运算受限的线性表，它的运算限制与栈不同，两头都有限制。
插入只能在表的一端进行 (只进不出)，而删除只能在表的另一端进行 (只出不进)。
允许插入的一端称为队尾 (rear)，允许删除的一端称为队头 (Front)，队列的操作原则是先进先出的，所以队列又称作 FIFO 表 (First In First Out)
队列的基本运算也有六种：
构造空队：InitQueue(Q)
判队空：QueueEmpty(Q)
判队满：QueueFull(Q)
入队：EnQueue(Q, x)
出队：DeQueue(Q)
取队头元素：QueueFront(Q)（与出队不同，队头元素仍然保留）
队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。
顺序队列，也有 ‘上溢’ 和 ‘下溢’，但是还有一种 ‘假上溢’。
在一段连续的存储空间中，由一个队列头指针和一个尾指针表示这个队列，当头指针和尾指针指向同一个位置时，队列为空。
也就是说，队列是由两个指针中间的元素构成的。
当元素出队和入队时，实际上是指针在移动，即使队列没有满（头指针不在头部），如果尾指针在尾部也会出现 ‘溢出’，这就是 ‘假上溢’。
为了克服这种现象，我们引入循环向量的概念，就好比是把向量空间弯起来，形成一个头尾相接的环形。
这样，当存于其中的队列头尾指针移到向量空间的上界 (尾部) 时，再加 1 的操作 (入队或出队) 就使指针指向向量的下界，也就是从头开始。
这时的队列就称循环队列。通常我们应用的大都是循环队列。
由于循环的原因，光看头尾指针重叠在一起我们并不能判断队列是空的还是满的，这时就需要处理一些边界条件，以区别队列是空还是满。
方法至少有三种，一种是另设一个布尔变量来判断 (就是请别人看着，是空还是满由他说了算)。
第二种是少用一个元素空间，当入队时，先测试入队后尾指针是不是会等于头指针，如果相等就算队已满，不许入队。
第三种就是用一个计数器记录队列中的元素的总数，这样就可以随时知道队列的长度了。
只要队列中的元素个数等于向量空间的长度，就是队满。一般我们应用第二种即可，少用一个空间。
当然，如果不知道元素最大长度，为了灵活利用内存空间，也可以使用链队。
Python 实现
顺序存储方式的实现：利用 Python 的 list 数据结构及相关方法即可实现。
栈：用 list 的 append 及 pop 方法即可。
队列：用 deque 的 append 及 popleft 方法即可。
stack =
stack.append(1)# append 实现入栈
print(stack)#
stack.append(3)
print(stack)#
print(stack.pop())# pop 实现出栈3
print(stack)#
print(stack.pop(0))# pop(0) 可以实现队列的出队功能，但是其时间复杂度为O(n)2
print(stack)#
from collections import deque
quene = deque()
quene.append(9)# append 入队功能
print(quene)# deque()
quene.extend()# extend 及 extendleft 功能 参数为可迭代对象，区别于append
quene.extendleft()
print(quene)# deque()
print(quene.popleft())# popleft() 出队功能实现，复杂度为O(1)12
print(quene)# deque()
d = deque('12345')
print(d)# deque(['1', '2', '3', '4', '5'])
print(d.popleft())# 1
print(d.pop())# 5
print(d)# deque(['2', '3', '4'])
d = deque('12345', maxlen=5)# 限制 deque 的长度
d.append(6)# 当超过限制数的项时, 另一边的项会自动删除
print(d)# deque(['2', '3', '4', '5', 6], maxlen=5)
也可以将栈、队列写成一个类，实现我们需要的功能，用的时候导入模块：
class Stack:
def __init__(self, size):
self.size = size
self.stack = []
self.top = -1
def push(self, ele):# 入栈之前检查栈是否已满
if self.isfull():
raise Exception("out of range")
else:
self.stack.append(ele)
self.top = self.top + 1
def pop(self):# 出栈之前检查栈是否为空
if self.isempty():
raise Exception("stack is empty")
else:
self.top = self.top - 1
return self.stack.pop()
def isfull(self):
return self.top + 1 == self.size
def isempty(self):
return self.top == -1
class Queue:
def __init__(self, size):
self.size = size
self.front = -1
self.rear = -1
self.queue = []
队列的具体实现可自行完成，与栈类似，注意 front 和 rear 两个指针即可。试着实现一个循环队列更加实用。
栈和队列的链式存储，在熟悉了链表那一套理论后，也不是难事。
比如栈链，push 方法将新元素结点建成与原头结点连接，作为新头结点即可；
pop 将头结点取出，将第二个结点作为新的头结点即可。操作均在头结点上。
n = node(data)
n.next = head
headnew = n
队列的操作需要两个指针，与上文的 Queue 类可能比较像，但是略微麻烦，因为操作的是链表。
总结
理解栈和队列的基本特点，顺序存储方法直接用 Python 实现很方便，有助于我们直接应用解决实际问题。
基于链表的存储，需要我们打好关于链表的理论和应用基础，并不难实现。 沙发，感谢楼主分享{:10_248:}
页:
[1]