Python 棧實現的幾種方式及優劣詳解

2022-11-01 14:02:32

1 棧的概念

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

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

棧的實際應用

實際上很多應用程式都會用到棧，比如：

網路瀏覽器將最近瀏覽的網址存放在一個棧中。每當使用者存取者存取一個新網站時，這個新網站的網址就被壓入棧頂。這樣，每當我們在瀏覽器單擊“後退”按鈕時（或者按鍵盤快捷鍵 CTRL+Z ，大部分復原快捷鍵），就可以彈出當前最近一次存取的網址，以回到其先前存取的瀏覽狀態。

文字編輯器通常會提供一個“復原”機制以取消最近的編輯操作並返回到先前狀態。這個復原操作也是通過將文字的變化狀態儲存在一個棧中得以實現。

一些高階語言的記憶體管理，JVM 的棧、Python 棧還用於記憶體管理、巢狀語言特性的執行時環境等

回溯（玩遊戲，尋找路徑，窮舉搜尋）

在演演算法中使用，如漢諾塔、樹形遍歷、直方圖問題，也用於圖演演算法，如拓撲排序

語法處理：

引數和區域性變數的空間是用堆疊在內部建立的。
編譯器對大括號匹配的語法檢查
對遞迴的支援
在編譯器中像字尾或字首一樣的表示式

2 棧的抽象資料型別

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

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

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

3 用 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)，元素越多就越慢。

4 用 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 棧的一個更好的選擇。

5 用 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 可能是值得做的。