栈由一系列对象对象组织的一个集合，这些对象的增加和删除操作都遵循一个“后进先出”（Last In First Out，LIFO）的原则。
在任何时刻只能向栈中插入一个对象，但只能取得或者删除只能在栈顶进行。比如由书构成的栈，唯一露出封面的书就是顶部的那本，为了拿到其他的书，只能移除压在上面的书，如图：
实际上很多应用程序都会用到栈，比如：
语法处理：
任何数据结构都离不开数据的保存和获得方式，如前所述，栈是元素的有序集合，添加和操作与移除都发生在其顶端（栈顶），那么它的抽象数据类型包括：
Python 栈的大小可能是固定的，也可能有一个动态的实现，即允许大小变化。在大小固定栈的情况下，试图向已经满的栈添加一个元素会导致栈溢出异常。同样，试图从一个已经是空的栈中移除一个元素，进行 操作这种情况被称为下溢。pop()
在学习 Python 的时候，一定学过 Python 列表 ， 它能通过一些内置的方式实现栈的功能：list
代码如下：
class ArrayStack:
""" 通过 Python 列表实现 LIFO 栈"""
def __init__(self):
self._data = []
def size(self):
""" return the number of elements in the stack"""
return len(self._data)
def is_empty(self):
""" return True if the stack is empty"""
return len(self._data) == 0
def push(self, e):
""" add element e to the top of the stack"""
self._data.append(e)
def pop(self):
""" remove and return the element from the top of the stack
"""
if self.is_empty():
rAIse Exception('Stack is empty')
return self._data.pop()
def top(self):
"""return the top of the stack
Raise Empty exception if the stack is empty
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data[-1] # the last item in the list
arrayStack = ArrayStack()
arrayStack.push("Python")
arrayStack.push("Learning")
arrayStack.push("Hello")
print("Stack top element: ", arrayStack.top())
print("Stack length: ", arrayStack.size())
print("Stack popped item: %s" % arrayStack.pop())
print("Stack is empty?", arrayStack.is_empty())
arrayStack.pop()
arrayStack.pop()
print("Stack is empty?", arrayStack.is_empty())
# arrayStack.pop()
运行该程序，结果：
Stack top element: Hello
Stack length: 3
Stack popped item: Hello
Stack is empty? False
Stack is empty? True
除了将列表的队尾作为栈顶，也可以通过将列表的头部作为栈的顶端。不过在这种情况下，便无法直接使用 方法和 方法，但是可以通过 和 方法显式地访问下标为 0 的元素，即列表的第一个元素，代码如下：pop()append()pop()insert()
class ArrayStack:
""" 通过 Python 列表实现 LIFO 栈"""
def __init__(self):
self._data = []
def size(self):
""" return the number of elements in the stack"""
return len(self._data)
def is_empty(self):
""" return True if the stack is empty"""
return len(self._data) == 0
def push(self, e):
""" add element e to the top of the stack"""
self._data.insert(0, e)
def pop(self):
""" remove and return the element from the top of the stack
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data.pop(0)
def top(self):
"""return the top of the stack
Raise Empty exception if the stack is empty
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data[0] # the last item in the list
虽然我们改变了抽象数据类型的实现，却保留了其逻辑特征，这种能力体现了抽象思想。不管，虽然两种方法都实现了栈，但两者的性能方法有差异：
在 Python 中， 模块有一个双端队列数据结构 deque，这个数据结构同样实现了 和 方法：collectionsappend()pop()
>>> from collections import deque
>>> myStack = deque()
>>> myStack.append('Apple')
>>> myStack.append('Banana')
>>> myStack.append('Orange')
>>>
>>> myStack
deque(['Apple', 'Banana', 'Orange'])
>>> myStack.pop()
'Orange'
>>> myStack.pop()
'Banana'
>>>
>>> len(myStack)
1
>>> myStack[0]
'Apple'
>>> myStack.pop()
'Apple'
>>>
>>> myStack.pop()
Traceback (most recent call last):
File "<pyshell#13>", line 1, in <module>
myStack.pop()
IndexError: pop from an empty deque
>>>
可能你可以看到 deque 和列表 list 对元素的操作差不多，那么为什么 Python 中有列表还增加了 deque 这一个数据结构呢？
那是因为，Python 中的列表建立在连续的内存块中，意味着列表的元素是紧挨着存储的。
这对一些操作来说非常有效，比如对列表进行索引。获取 的速度很快，因为 Python 确切地知道在内存中寻找它的位置。这种内存布局也允许切片在列表上很好地工作。myList[3]
毗连的内存布局是 list 可能需要花费更多时间来 一些对象。如果连续的内存块已经满了，那么它将需要获得另一个内存块，先将整体 copy 过去，这个动作可能比一般的 操作花费更多的时间。.append().append()
而双端队列 是建立在一个双链表的基础上。在一个链接列表结构中，每个条目都存储在它自己的内存块中，并有一个对列表中下一个条目的引用。deque
双链表也是如此，只是每个条目都有对列表中前一个和后一个条目的引用。这使得你可以很容易地在列表的两端添加节点。
在一个链接列表结构中添加一个新的条目，只需要设置新条目的引用指向当前堆栈的顶部，然后将堆栈的顶部指向新条目。
Memory structure of a deque pushing a new element
然而，这种在栈上不断增加和删除条目的时间是有代价的。获取 的速度要比列表慢，因为 Python 需要走过列表的每个节点来获取第三个元素。myDeque[3]
幸运的是，你很少想在栈上做随机索引元素或进行列表切片操作。栈上的大多数操作都是 或 。pushpop
如果你的代码不使用线程，常数时间的 和 操作使 deque 成为实现 Python 栈的一个更好的选择。.append().pop()
Python 栈在多线程程序中也很有用，我们已经学习了 和 两种方式。对于任何可以被多个线程访问的数据结构，在多线程编程中，我们不应该使用 ，因为列表不是线程安全的。deque 的 和 方法是原子性的，意味着它们不会被不同的线程干扰。listdequelist.append().pop()
因此，虽然使用 deque 可以建立一个线程安全的 Python 堆栈，但这样做会使你自己在将来被人误用，造成竞态条件。
好吧，如果你是多线程编程，你不能用 来做堆栈，你可能也不想用 来做堆栈，那么你如何为一个线程程序建立一个 Python 堆栈？listdeque
答案就在 模块中：queue.LifoQueue。还记得你是如何学习到栈是按照后进先出（LIFO）的原则运行的吗？嗯，这就是 LifoQueue 的 "Lifo "部分所代表的含义。queue
虽然 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
<queue.LifoQueue object at 0x00000123159F7310>
>>>
>>> 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 "<pyshell#31>", line 1, in <module>
stack.get_nowait()
_queue.Empty
>>>
>>> stack.put('Apple')
>>> stack.get_nowait()
'Apple'
与 deque 不同，LifoQueue 被设计为完全线程安全的。它的所有方法都可以在线程环境中安全使用。它还为其操作添加了可选的超时功能，这在线程程序中经常是一个必须的功能。
然而，这种完全的线程安全是有代价的。为了实现这种线程安全，LifoQueue 必须在每个操作上做一些额外的工作，这意味着它将花费更长的时间。
通常情况下，这种轻微的减速对你的整体程序速度并不重要，但如果你已经测量了你的性能，并发现你的堆栈操作是瓶颈，那么小心地切换到 deque 可能是值得做的。
一般来说，如果你不使用多线程，你应该使用 。如果你使用多线程，那么你应该使用 ，除非你已经测量了你的性能，发现 和 的速度的小幅提升会带来足够的差异，以保证维护风险。dequeLifoQueuepushpop
你可以对列表可能很熟悉，但需要谨慎使用它，因为它有可能存在内存重新分配的问题。和 的接口是相同的，而且 没有线程不安全问题。dequelistdeque
本文介绍了栈这一数据结构，并介绍了在现实生活中的程序中如何使用它的情况。在文章的中，介绍了 Python 中实现栈的三种不同方式，知道了 对于非多线程程序是一个更好的选择，如果你要在多线程编程环境中使用栈的话，可以使用 。
京公网安备 11010802035086号