1 棧的概念

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

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

棧的實際應用

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

• 網(wǎng)絡瀏覽器將最近瀏覽的網(wǎng)址存放在一個棧中。每當用戶訪問者訪問一個新網(wǎng)站時，這個新網(wǎng)站的網(wǎng)址就被壓入棧頂。這樣，每當我們在瀏覽器單擊"后退"按鈕時（或者按鍵盤快捷鍵  ，大部分撤銷快捷鍵），就可以彈出當前最近一次訪問的網(wǎng)址，以回到其先前訪問的瀏覽狀態(tài)。CTRL+Z
• 文本編輯器通常會提供一個"撤銷"機制以取消最近的編輯操作并返回到先前狀態(tài)。這個撤銷操作也是通過將文本的變化狀態(tài)保存在一個棧中得以實現(xiàn)。
• 一些高級語言的內(nèi)存管理，JVM 的棧、Python 棧還用于內(nèi)存管理、嵌套語言特性的運行時環(huán)境等
• 回溯（玩游戲，尋找路徑，窮舉搜索）
• 在算法中使用，如漢諾塔、樹形遍歷、直方圖問題，也用于圖算法，如拓撲排序

語法處理：

• 參數(shù)和局部變量的空間是用堆棧在內(nèi)部創(chuàng)建的。編譯器對大括號匹配的語法檢查對遞歸的支持在編譯器中像后綴或前綴一樣的表達式

2 棧的抽象數(shù)據(jù)類型

任何數(shù)據(jù)結構都離不開數(shù)據(jù)的保存和獲得方式，如前所述，棧是元素的有序集合，添加和操作與移除都發(fā)生在其頂端（棧頂），那么它的抽象數(shù)據(jù)類型包括：

• Stack():創(chuàng)建一個空棧，它不需要參數(shù)，且會返回一個空棧
• push(e)：將一個元素 e 添加到棧 S 的棧頂，它需要一個參數(shù) e，且無返回值
• pop(): 將棧頂端的元素移除，它不需要參數(shù)，但會返回頂端的元素，并且修改棧的內(nèi)容
• top(): 返回棧頂端的元素，但是并不移除棧頂元素；若棧為空，這個操作會操作
• is_empty(): 如果棧中不包含任何元素，則返回一個布爾值True
• size()：返回棧中元素的數(shù)據(jù)。它不需要參數(shù)，且會返回一個整數(shù)。在 Python 中，可以用 這個特殊方法實現(xiàn)。__len__

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

3 用 Python 的列表實現(xiàn)棧

在學習 Python 的時候，一定學過 Python 列表 ， 它能通過一些內(nèi)置的方式實現(xiàn)棧的功能：list

• 通過  方法用于添加一個元素到列表尾部，這種方式就能模擬  操作appendpush()
• 通過  方法用于模擬出棧操作pop()
• 通過  模擬 操作L[-1]top()
• 通過判斷  模擬  操作len(L)==0isEmpty()
• 通過  函數(shù)實現(xiàn)  函數(shù)len()size()

代碼如下：

class ArrayStack:
    """ 通過 Python 列表實現(xiàn) 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 列表實現(xiàn) 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

雖然我們改變了抽象數(shù)據(jù)類型的實現(xiàn)，卻保留了其邏輯特征，這種能力體現(xiàn)了抽象思想。不管，雖然兩種方法都實現(xiàn)了棧，但兩者的性能方法有差異：

• append() 和  方法的時間復雜度都是 _**O(1)**，_常數(shù)級別操作pop()
• 第二種實現(xiàn)的性能則受制于棧中的元素個數(shù)，這是因為  和  的時間復雜度都是 O(n)，元素越多就越慢。insert(0)pop(0)

4 用 collections.deque 實現(xiàn)棧

在 Python 中， 模塊有一個雙端隊列數(shù)據(jù)結構 deque，這個數(shù)據(jù)結構同樣實現(xiàn)了  和  方法：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
>>>

為什么有了 list 還需要 deque？

可能你可以看到 deque 和列表 list 對元素的操作差不多，那么為什么 Python 中有列表還增加了 deque 這一個數(shù)據(jù)結構呢？

那是因為，Python 中的列表建立在連續(xù)的內(nèi)存塊中，意味著列表的元素是緊挨著存儲的。

這對一些操作來說非常有效，比如對列表進行索引。獲取  的速度很快，因為 Python 確切地知道在內(nèi)存中尋找它的位置。這種內(nèi)存布局也允許切片在列表上很好地工作。myList[3]

毗連的內(nèi)存布局是 list 可能需要花費更多時間來  一些對象。如果連續(xù)的內(nèi)存塊已經(jīng)滿了，那么它將需要獲得另一個內(nèi)存塊，先將整體 copy 過去，這個動作可能比一般的  操作花費更多的時間。.append().append()

而雙端隊列  是建立在一個雙鏈表的基礎上。在一個鏈接列表結構中，每個條目都存儲在它自己的內(nèi)存塊中，并有一個對列表中下一個條目的引用。deque

雙鏈表也是如此，只是每個條目都有對列表中前一個和后一個條目的引用。這使得你可以很容易地在列表的兩端添加節(jié)點。

在一個鏈接列表結構中添加一個新的條目，只需要設置新條目的引用指向當前堆棧的頂部，然后將堆棧的頂部指向新條目。

Memory structure of a deque pushing a new element

然而，這種在棧上不斷增加和刪除條目的時間是有代價的。獲取  的速度要比列表慢，因為 Python 需要走過列表的每個節(jié)點來獲取第三個元素。myDeque[3]

幸運的是，你很少想在棧上做隨機索引元素或進行列表切片操作。棧上的大多數(shù)操作都是  或 。pushpop

如果你的代碼不使用線程，常數(shù)時間的  和  操作使 deque 成為實現(xiàn) Python 棧的一個更好的選擇。.append().pop()

5 用 queue.LifoQueue 實現(xiàn)棧

Python 棧在多線程程序中也很有用，我們已經(jīng)學習了  和  兩種方式。對于任何可以被多個線程訪問的數(shù)據(jù)結構，在多線程編程中，我們不應該使用 ，因為列表不是線程安全的。deque 的  和  方法是原子性的，意味著它們不會被不同的線程干擾。listdequelist.append().pop()

因此，雖然使用 deque 可以建立一個線程安全的 Python 堆棧，但這樣做會使你自己在將來被人誤用，造成競態(tài)條件。

好吧，如果你是多線程編程，你不能用  來做堆棧，你可能也不想用  來做堆棧，那么你如何為一個線程程序建立一個 Python 堆棧？listdeque

答案就在  模塊中：queue.LifoQueue。還記得你是如何學習到棧是按照后進先出（LIFO）的原則運行的嗎？嗯，這就是 LifoQueue 的 "Lifo "部分所代表的含義。queue

雖然 list 和 deque 的接口相似，但 LifoQueue 使用  和  來從棧中添加和刪除數(shù)據(jù)。.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 被設計為完全線程安全的。它的所有方法都可以在線程環(huán)境中安全使用。它還為其操作添加了可選的超時功能，這在線程程序中經(jīng)常是一個必須的功能。

然而，這種完全的線程安全是有代價的。為了實現(xiàn)這種線程安全，LifoQueue 必須在每個操作上做一些額外的工作，這意味著它將花費更長的時間。

通常情況下，這種輕微的減速對你的整體程序速度并不重要，但如果你已經(jīng)測量了你的性能，并發(fā)現(xiàn)你的堆棧操作是瓶頸，那么小心地切換到 deque 可能是值得做的。

6 選擇哪一種實現(xiàn)作為棧

一般來說，如果你不使用多線程，你應該使用 。如果你使用多線程，那么你應該使用 ，除非你已經(jīng)測量了你的性能，發(fā)現(xiàn)  和  的速度的小幅提升會帶來足夠的差異，以保證維護風險。dequeLifoQueuepushpop

你可以對列表可能很熟悉，但需要謹慎使用它，因為它有可能存在內(nèi)存重新分配的問題。和  的接口是相同的，而且  沒有線程不安全問題。dequelistdeque

7 總結

本文介紹了棧這一數(shù)據(jù)結構，并介紹了在現(xiàn)實生活中的程序中如何使用它的情況。在文章的中，介紹了 Python 中實現(xiàn)棧的三種不同方式，知道了  對于非多線程程序是一個更好的選擇，如果你要在多線程編程環(huán)境中使用棧的話，可以使用 。