堆疊由一系列物件物件組織的一個集合，這些物件的增加和刪除操作都遵循一個「後進先出」（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
除了將清單的隊尾作為堆疊頂，也可以透過將清單的頭部作為堆疊的頂端。不過在這種情況下，便無法直接使用 pop() 方法和 append()方法，但是可以透過 pop() 和 insert() 方法來明確地存取下標為0 的元素，即列表的第一個元素，程式碼如下：
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 中，collections 模組有一個雙端佇列資料結構 deque，這個資料結構同樣實作了 append() 和 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 中的列表建立在連續的記憶體區塊中，這意味著列表的元素是緊鄰儲存的。
這對某些操作來說非常有效，例如對清單進行索引。取得 myList[3] 的速度很快，因為 Python 確切地知道在記憶體中尋找它的位置。這種記憶體佈局也允許切片在列表上很好地工作。
毗連的記憶體佈局是 list 可能需要花費更多時間來 .append() 一些物件。如果連續的記憶體區塊已經滿了，那麼它將需要獲得另一個記憶體區塊，先將整體 copy 過去，這個動作可能比一般的 .append() 作業花費更多的時間。
而雙端佇列 deque 是建立在雙鍊錶的基礎上。在一個連結清單結構中，每個條目都儲存在它自己的記憶體區塊中，並有一個對清單中下一個條目的引用。
雙鍊錶也是如此，只是每個條目都有對清單中前一個和後一個條目的引用。這使得你可以很容易地在列表的兩端添加節點。
在一個連結清單結構中新增一個新的條目，只需要設定新條目的參考指向目前堆疊的頂部，然後將堆疊的頂部指向新條目。
然而，這種在堆疊上不斷增加和刪除條目的時間是有代價的。取得 myDeque[3] 的速度比清單慢，因為 Python 需要走過清單的每個節點來取得第三個元素。
幸運的是，你很少想在堆疊上做隨機索引元素或進行清單切片操作。堆疊上的大多數操作都是 push 或 pop。
如果你的程式碼不使用線程，常數時間的 .append() 和 .pop() 操作讓 deque 成為實現 Python 堆疊的一個更好的選擇。
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
<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 可能是值得做的。
一般来说，如果你不使用多线程，你应该使用 deque。如果你使用多线程，那么你应该使用 LifoQueue，除非你已经测量了你的性能，发现 push 和 pop 的速度的小幅提升会带来足够的差异，以保证维护风险。
你可以对列表可能很熟悉，但需要谨慎使用它，因为它有可能存在内存重新分配的问题。deque 和 list 的接口是相同的，而且 deque 没有线程不安全问题。
本文介绍了栈这一数据结构，并介绍了在现实生活中的程序中如何使用它的情况。在文章的中，介绍了 Python 中实现栈的三种不同方式，知道了 deque 对于非多线程程序是一个更好的选择，如果你要在多线程编程环境中使用栈的话，可以使用 LifoQueue。
以上是Python 實作堆疊的幾種方式及其優劣的詳細內容。更多資訊請關注PHP中文網其他相關文章！
