Python 栈（后进先出）|极客教程

Python 栈，栈是含有一组对象的容器，支持快速后进先出（LIFO）的插入和删除操作。与列表或数组不同，栈通常不允许随机访问所包含的对象。插入和删除操作通常称为入栈（push）和出栈（pop）。

现实世界中与栈数据结构相似的是一叠盘子。

新盘子会添加到栈的顶部。由于这些盘子非常宝贵且很重，所以只能移动最上面的盘子（后进先出）。要到达栈中位置较低的盘子，必须逐一移除最顶端的盘子。

栈和队列相似，都是线性的元素集合，但元素的访问顺序不同。

从队列删除元素时，移除的是最先添加的项（先进先出，FIFO）；而栈是移除最近添加的项（后进先出，LIFO）。

在性能方面，合理的栈实现在插入和删除操作的预期耗时是。
栈在算法中有广泛的应用，比如用于语言解析和运行时的内存管理（“调用栈”）。树或图数据结构上的深度优先搜索（DFS）是简短而美丽的算法，其中就用到了栈。

Python中有几种栈实现，每个实现的特性略有不同。下面来分别介绍并比较各自的特性。

Python 栈列表——简单的内置栈

Python的内置列表类型能在正常的时间内完成入栈和出栈操作，因此适合作为栈数据结构。

Python的列表在内部以动态数组实现，这意味着在添加或删除时，列表偶尔需要调整元素的存储空间大小。列表会预先分配一些后备存储空间，因此并非每个入栈或出栈操作都需要调整大小，所以这些操作的均摊时间复杂度为。

这么做的缺点是列表的性能不如基于链表的实现（如collections.deque，下面会介绍），后者能为插入和删除操作提供稳定的时间复杂度。另一方面，列表能在时间快速随机访问堆栈上的元素，这能带来额外的好处。

使用列表作为堆栈应注意下面几个重要的性能问题。

为了获得的插入和删除性能，必须使用append()方法将新项添加到列表的末尾，删除时也要使用pop()从末尾删除。为了获得最佳性能，基于Python列表的栈应该向高索引增长并向低索引缩小。

从列表前部添加和删除元素很慢，耗时为，因为这种情况下必须移动现有元素来为新元素腾出空间。这是一个性能反模式，应尽可能避免。

>>> s = []
>>> s.append('eat')
>>> s.append('sleep')
>>> s.append('code')

>>> s
['eat', 'sleep', 'code']

>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'

>>> s.pop()
IndexError: "pop from empty list"

Python 栈 `collections.deque`——快速且稳健的栈

deque类实现了一个双端队列，支持在时间（非均摊）从两端添加和移除元素。因为双端队列支持从两端添加和删除元素，所以既可以作为队列也可以作为栈。

Python的deque对象以双向链表实现，这为插入和删除元素提供了出色且一致的性能，但是随机访问位于栈中间元素的性能很差，耗时为。

总之，如果想在Python的标准库中寻找一个具有链表性能特征的栈数据结构实现，那么collections.deque是不错的选择。

>>> from collections import deque
>>> s = deque()
>>> s.append('eat')
>>> s.append('sleep')
>>> s.append('code')

>>> s
deque(['eat', 'sleep', 'code'])

>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'

>>> s.pop()
IndexError: "pop from an empty deque"

Python 栈 `queue.LifoQueue`——为并行计算提供锁语义

queue.LifoQueue这个位于Python标准库中的栈实现是同步的，提供了锁语义来支持多个并发的生产者和消费者。

除了LifoQueue之外，queue模块还包含其他几个类，都实现了用于并行计算的多生产者/多用户队列。
在不同情况下，锁语义即可能会带来帮助，也可能会导致不必要的开销。在后面这种情况下，最好使用list或deque作为通用栈。

>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put('eat')
>>> s.put('sleep')
>>> s.put('code')

>>> s
<queue.LifoQueue object at 0x108298dd8>

>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'

>>> s.get_nowait()
queue.Empty

>>> s.get()
# 阻塞，永远停在这里……

Python 栈比较Python中各个栈的实现

从上面可以看出，Python中有多种栈数据结构的实现，各自的特性稍有区别，在性能和用途上也各有优劣。

如果不寻求并行处理支持（或者不想手动处理上锁和解锁），可选择内置列表类型或collections.deque。两者背后使用的数据结构和总体易用性有所不同。

列表底层是动态数组，因此适用于快速随机访问，但在添加或删除元素时偶尔需要调整大小。列表会预先分配一些备用存储空间，因此不是每个入栈或出栈操作都需要调整大小，这些操作的均摊时间复杂度为。但需要小心，只能用append()和pop()从“右侧”插入和删除元素，否则性能会下降为。
collections.deque底层是双向链表，为从两端的添加和删除操作进行了优化，为这些操作提供了一致的性能。collections.deque不仅性能稳定，而且便于使用，不必担心在“错误的一端”添加或删除项。

总之，我认为collections.deque是在Python中实现栈（LIFO队列）的绝佳选择。

关键要点