栈由一系列对象对象组织的一个集合,这些对象的增加和删除操作都遵循一个“后进先出”(Last In First Out,LIFO)的原则。
在任何时刻只能向栈中插入一个对象,但只能取得或者删除只能在栈顶进行。比如由书构成的栈,唯一露出封面的书就是顶部的那本,为了拿到其他的书,只能移除压在上面的书,如图:
实际上很多应用程序都会用到栈,比如:
任何数据结构都离不开数据的保存和获得方式,如前所述,栈是元素的有序集合,添加和操作与移除都发生在其顶端(栈顶),那么它的抽象数据类型包括:
Python 栈的大小可能是固定的,也可能有一个动态的实现,即允许大小变化。在大小固定栈的情况下,试图向已经满的栈添加一个元素会导致栈溢出异常。同样,试图从一个已经是空的栈中移除一个元素,进行 pop()
操作这种情况被称为下溢。
在学习 Python 的时候,一定学过 Python 列表 list
, 它能通过一些内置的方式实现栈的功能:
代码如下:
这对一些操作来说非常有效,比如对列表进行索引。获取 myList[3] 的速度很快,因为 Python 确切地知道在内存中寻找它的位置。这种内存布局也允许切片在列表上很好地工作。毗连的内存布局是 list 可能需要花费更多时间来 .append() 一些对象。如果连续的内存块已经满了,那么它将需要获得另一个内存块,先将整体 copy 过去,这个动作可能比一般的 .append() 操作花费更多的时间。而双端队列 deque 是建立在一个双链表的基础上。在一个链接列表结构中,每个条目都存储在它自己的内存块中,并有一个对列表中下一个条目的引用。双链表也是如此,只是每个条目都有对列表中前一个和后一个条目的引用。这使得你可以很容易地在列表的两端添加节点。在一个链接列表结构中添加一个新的条目,只需要设置新条目的引用指向当前堆栈的顶部,然后将堆栈的顶部指向新条目。然而,这种在栈上不断增加和删除条目的时间是有代价的。获取 myDeque[3] 的速度要比列表慢,因为 Python 需要走过列表的每个节点来获取第三个元素。幸运的是,你很少想在栈上做随机索引元素或进行列表切片操作。栈上的大多数操作都是 push 或 pop。如果你的代码不使用线程,常数时间的 .append() 和 .pop() 操作使 deque 成为实现 Python 栈的一个更好的选择。五、用 queue.LifoQueue 实现栈Python 栈在多线程程序中也很有用,我们已经学习了 list 和 deque 两种方式。对于任何可以被多个线程访问的数据结构,在多线程编程中,我们不应该使用 list,因为列表不是线程安全的。deque 的 .append() 和 .pop() 方法是原子性的,意味着它们不会被不同的线程干扰。因此,虽然使用 deque 可以建立一个线程安全的 Python 堆栈,但这样做会使你自己在将来被人误用,造成竞态条件。好吧,如果你是多线程编程,你不能用 list 来做堆栈,你可能也不想用 deque 来做堆栈,那么你如何为一个线程程序建立一个 Python 堆栈?答案就在 queue 模块中:queue.LifoQueue。还记得你是如何学习到栈是按照后进先出(LIFO)的原则运行的吗?嗯,这就是 LifoQueue 的 "Lifo "部分所代表的含义。虽然 list 和 deque 的接口相似,但 LifoQueue 使用 .put() 和 .get() 来从栈中添加和删除数据。>>> from queue import LifoQueue >>> stack = LifoQueue() >>> stack.put('H') >>> stack.put('E') >>> stack.put('L') >>> stack.put('L') >>> stack.put('O') >>> stack >>> >>> stack.get() 'O' >>> stack.get() 'L' >>> stack.empty() False >>> stack.qsize() 3 >>> stack.get() 'L' >>> stack.get() 'E' >>> stack.qsize() 1 >>> stack.get() 'H' >>> stack.get_nowait() Traceback (most recent call last): File "", line 1, in stack.get_nowait() _queue.Empty >>> >>> stack.put('Apple') >>> stack.get_nowait() 'Apple'
与 deque 不同,LifoQueue 被设计为完全线程安全的。它的所有方法都可以在线程环境中安全使用。它还为其操作添加了可选的超时功能,这在线程程序中经常是一个必须的功能。
然而,这种完全的线程安全是有代价的。为了实现这种线程安全,LifoQueue 必须在每个操作上做一些额外的工作,这意味着它将花费更长的时间。
通常情况下,这种轻微的减速对你的整体程序速度并不重要,但如果你已经测量了你的性能,并发现你的堆栈操作是瓶颈,那么小心地切换到 deque 可能是值得做的。
一般来说,如果你不使用多线程,你应该使用 deque。如果你使用多线程,那么你应该使用 LifoQueue,除非你已经测量了你的性能,发现 push 和 pop 的速度的小幅提升会带来足够的差异,以保证维护风险。
你可以对列表可能很熟悉,但需要谨慎使用它,因为它有可能存在内存重新分配的问题。deque 和 list 的接口是相同的,而且 deque 没有线程不安全问题。
本文介绍了栈这一数据结构,并介绍了在现实生活中的程序中如何使用它的情况。在文章的中,介绍了 Python 中实现栈的三种不同方式,知道了 deque 对于非多线程程序是一个更好的选择,如果你要在多线程编程环境中使用栈的话,可以使用 LifoQueue。