Python 實作堆疊的幾種方式及其優劣

想了解更多關於開源的內容，請造訪：

#51CTO 開源基礎軟體社群

#https://ost.51cto.com

#一、堆疊的概念

堆疊由一系列物件物件組織的一個集合，這些物件的增加和刪除操作都遵循一個「後進先出」（Last In First Out，LIFO）的原則。

在任何時刻只能向堆疊中插入一個對象，但只能取得或刪除只能在堆疊頂部進行。例如由書構成的棧，唯一露出封面的書就是頂部的那本，為了拿到其他的書，只能移除壓在上面的書，如圖：

堆疊的實際應用

其實很多應用程式都會用到棧，例如：

1. 網頁瀏覽器將最近瀏覽的網址存放在一個堆疊中。每當使用者訪客造訪一個新網站時，這個新網站的網址就會被壓入棧頂。這樣，每當我們在瀏覽器點擊「後退」按鈕時（或按鍵盤快捷鍵CTRL Z ，大部分撤銷快捷鍵），就可以彈出當前最近一次訪問的網址，以回到其先前訪問的瀏覽狀態。
2. 文字編輯器通常會提供一個「撤銷」機制以取消最近的編輯操作並返回先前狀態。這個撤銷操作也是透過將文字的變化狀態保存在一個堆疊中來實現。
3. 一些高階語言的記憶體管理，JVM 的堆疊、Python 堆疊也用於記憶體管理、巢狀語言特性的執行時間環境等
4. 回溯（玩遊戲，尋找路徑，窮舉搜尋）
5. 在演算法中使用，如漢諾塔、樹形遍歷、直方圖問題，也用於圖演算法，如拓樸排序
6. 語法處理：

• 參數和局部變數的空間是用堆疊在內部建立的。
• 編譯器對大括號匹配的語法檢查
• 對遞歸的支援
• 在編譯器中像後綴或前綴一樣的表達式

二、堆疊的抽象資料型別

任何資料結構都離不開資料的保存與取得方式，如前所述，堆疊是元素的有序集合，新增與操作與移除都發生在其頂端（堆疊頂端），那麼它的抽象資料型別包括：

• Stack() :建立一個空棧，它不需要參數，並且會傳回一個空棧。
• push(e): 將一個元素 e 加到堆疊 S 的堆疊頂，它需要一個參數 e，且無回傳值。
• pop() : 將堆疊頂端的元素移除，它不需要參數，但會傳回頂端的元素，並且修改堆疊的內容。
• top(): 傳回堆疊頂端的元素，但是不移除棧頂元素；若堆疊為空，這個操作會操作。
• is_empty(): 如果堆疊中不包含任何元素，則傳回一個布林值True。
• size()：傳回堆疊中元素的資料。它不需要參數，且會傳回一個整數。在 Python 中，可以用__len__ 這個特殊方法實作。

Python 堆疊的大小可能是固定的，也可能有一個動態的實現，即允許大小變化。在大小固定堆疊的情況下，試圖在已經滿的堆疊中添加一個元素會導致堆疊溢位異常。同樣，試圖從一個已經是空的堆疊中移除一個元素，進行 pop() 操作這種情況稱為下溢。

三、用Python 的列表實現堆疊

在學習Python 的時候，一定學過Python 列表 list , 它能通過一些內置的方式實作堆疊的功能：

• 透過append 方法用來新增一個元素到列表尾部，這種方式就能模擬push() 運算。
• 透過pop() 方法用於模擬出棧操作。
• 透過L[-1] 模擬top()操作。
• 透過判斷len(L)==0 模擬isEmpty() 運算。
• 透過len() 函數實現size() 函數。

程式碼如下：

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

雖然我們改變了抽象資料類型的實現，卻保留了其邏輯特徵，而這種能力體現了抽象思想。不管，雖然兩種方法都實作了堆疊，但兩者的效能方法有差異：

• append() 和pop() 方法的時間複雜度都是*O(1)， *常數層級運算
• 第二種實作的效能則受制於堆疊中的元素個數，這是因為insert(0) 和pop(0) 的時間複雜度都是O(n)，元素越多就越慢。

四、用collections.deque 實作堆疊

在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
>>>

為什麼有了list 還需要deque？

可能你可以看到 deque 和列表 list 對元素的操作差不多，那麼為什麼 Python 中有列表還增加了 deque 這一個資料結構呢？

那是因為，Python 中的列表建立在連續的記憶體區塊中，這意味著列表的元素是緊鄰儲存的。

這對某些操作來說非常有效，例如對清單進行索引。取得 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
<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。

​​想了解更多关于开源的内容，请访问：​​

​​51CTO 开源基础软件社区​​

​​https://ost.51cto.com​​。

以上是Python 實作堆疊的幾種方式及其優劣的詳細內容。更多資訊請關注PHP中文網其他相關文章！