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模块还包含其他几个类,都实现了用于并行计算的多生产者/多用户队列。
在不同情况下,锁语义即可能会带来帮助,也可能会导致不必要的开销。在后面这种情况下,最好使用listdeque作为通用栈。

>>> 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队列)的绝佳选择。

关键要点

  • Python中有几个栈实现,每种实现的性能和使用特性略有不同。

  • collections.deque提供安全且快速的通用栈实现。

  • 内置列表类型可以作为栈使用,但要小心只能使用append()pop()来添加和删除项,以避免性能下降。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程