Stacks (LIFOs)
A stack is a collection of objects that supports fast last-in, first-out (LIFO) semantics for inserts and deletes. Unlike lists or arrays, stacks typically don’t allow for random access to the objects they contain. The insert and delete operations are also often called push and pop.
堆栈是支持后进先出的插入和删除操作的对象集合。不像列表和数组，堆栈一般上不能允许随机访问堆栈中含有的对象。插入和删除操作也被成为压入和弹出。
A useful real-world analogy for a stack data structure is a stack of plates:
New plates are added to the top of the stack. And because the plates are precious and heavy, only the topmost plate can be moved (last-in, first-out). To reach the plates that are lower down in the stack, the topmost plates must be removed one by one.
Stacks and queues are similar. They’re both linear collections of items, and the difference lies in the order that the items are accessed:
堆栈和队列是类似的。它们都是线性物品集合。它们两的区别就是item访问的顺序不一样。
With a queue, you remove the item least recently added (first-in, firstout or FIFO); but with a stack, you remove the item most recently added (last-in, first-out or LIFO).
队列中是先进先出，堆栈是后进先出。
Performance-wise, a proper stack implementation is expected to take O(1) time for insert and delete operations.
堆栈操作插入和删除操作时间复杂度为O(1)。
Stacks have a wide range of uses in algorithms, for example, in language parsing and runtime memory management (“call stack”). A short and beautiful algorithm using a stack is depth-first search (DFS) on a tree or graph data structure.
Python ships with several stack implementations that each have slightly different characteristics. We’ll now take a look at them and compare their characteristics.
list – Simple, Built-In Stacks
Python’s built-in list type makes a decent stack data structure as it supports push and pop operations in amortized O(1) time.
Python’s lists are implemented as dynamic arrays internally, which means they occasionally need to resize the storage space for elements stored in them when elements are added or removed. The list overallocates its backing storage so that not every push or pop requires resizing, and as a result, you get an amortized O(1) time complexity for these operations.
就是是列表操作的时候删改和插入的时候需要重新调整存储空间。
The downside is that this makes their performance less consistent than the stable O(1) inserts and deletes provided by a linked list based implementation (like collections.deque, see below). On the other hand, lists do provide fast O(1) time random access to elements on the stack, and this can be an added benefit.
Here’s an important performance caveat you should be aware of when using lists as stacks:
提醒有缺点要注意了。
To get the amortized O(1) performance for inserts and deletes, new items must be added to the end of the list with the append() method and removed again from the end using pop(). For optimum performance, stacks based on Python lists should grow towards higher indexes and shrink towards lower ones.
为了获得最佳性能，基于python列表的堆栈应该朝着更高的索引增长，并朝着更低的索引收缩。
Adding and removing from the front is much slower and takes O(n) time, as the existing elements must be shifted around to make room for the new element. This is a performance antipattern that you should avoid as much as possible.
添加和删除前面的元素变慢了，因为需要为了这个操作腾出空间给新的元素。这种操作我们应该尽量避免。
>>> 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"
collections.deque – Fast & Robust Stacks
The deque class implements a double-ended queue that supports adding and removing elements from either end in O(1) time (nonamortized). Because deques support adding and removing elements from either end equally well, they can serve both as queues and as stacks.
Python’s deque objects are implemented as doubly-linked lists which gives them excellent and consistent performance for inserting and deleting elements, but poor O(n) performance for randomly accessing elements in the middle of a stack.
deque操作从两端开始的插入和删除操作都是效果不错的，但是在中部的元素的插入和删除相对表现差一些。
Overall, collections.deque is a great choice if you’re looking for a stack data structure in Python’s standard library that has the performance characteristics of a linked-list implementation.
总的来说，如果您在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"
queue.LifoQueue – Locking Semantics for Parallel Computing
This stack implementation in the Python standard library is synchronized and provides locking semantics to support multiple concurrent producers and consumers.
python标准库中的这个堆栈实现是同步的并提供锁语义以支持多个并发。
意思就是这个支持并发操作。
Besides LifoQueue, the queue module contains several other classes that implement multi-producer/multi-consumer queues that are useful for parallel computing.
并行计算。
Depending on your use case, the locking semantics might be helpful, or they might just incur unneeded overhead. In this case you’d be better off with using a list or a deque as a general-purpose stack.
>>> 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()
# Blocks / waits forever...
Comparing Stack Implementations in Python
As you’ve seen, Python ships with several implementations for a stack data structure. All of them have slightly different characteristics, as well as performance and usage trade-offs.
If you’re not looking for parallel processing support (or don’t want to handle locking and unlocking manually), your choice comes down to the built-in list type or collections.deque. The difference lies in the data structure used behind the scenes and overall ease of use:
list is backed by a dynamic array which makes it great for fast random access, but requires occasional resizing when elements are added or removed. The list over-allocates its backing storage so that not every push or pop requires resizing, and you get an amortized O(1) time complexity for these operations. But you do need to be careful to only insert and remove items “from the right side” using append() and pop(). Otherwise, performance slows down to O(n).
collections.deque is backed by a doubly-linked list which optimizes appends and deletes at both ends and provides consistent O(1) performance for these operations. Not only is its performance more stable, the deque class is also easier to use because you don’t have to worry about adding or removing items from “the wrong end.”
In summary, I believe that collections.deque is an excellent choice for implementing a stack (LIFO queue) in Python.
Key Takeaways
- Python ships with several stack implementations that have slightly different performance and usage characteristics.
- collections.deque provides a safe and fast general-purpose stack implementation.
- The built-in list type can be used as a stack, but be careful to only append and remove items with append() and pop() in order to avoid slow performance.
