Python 数据结构之栈和队列 —— （一）功能实现

zltzlt

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 = [2, 4, 6, 8]
stack.append(1)  # append 实现入栈
print(stack)  # [2, 4, 6, 8, 1]
stack.append(3)
print(stack)  # [2, 4, 6, 8, 1, 3]
print(stack.pop())  # pop 实现出栈  3
print(stack)  # [2, 4, 6, 8, 1]
print(stack.pop(0))  # pop(0) 可以实现队列的出队功能，但是其时间复杂度为O(n)  2
print(stack)  # [4, 6, 8, 1]

from collections import deque

quene = deque([1, 3, 5, 7])
quene.append(9)  # append 入队功能
print(quene)  # deque([1, 3, 5, 7, 9])
quene.extend([8, 9])  # extend 及 extendleft 功能 参数为可迭代对象，区别于append
quene.extendleft([11, 12])
print(quene)  # deque([12, 11, 1, 3, 5, 7, 9, 8, 9])
print(quene.popleft())  # popleft() 出队功能实现，复杂度为O(1)  12
print(quene)  # deque([11, 1, 3, 5, 7, 9, 8, 9])

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 实现很方便，有助于我们直接应用解决实际问题。

基于链表的存储，需要我们打好关于链表的理论和应用基础，并不难实现。

永恒的蓝色梦想

沙发，感谢楼主分享