Python資料結構與演演算法中的棧詳解

0. 學習目標

棧和佇列是在程式設計中常見的資料型別，從資料結構的角度來講，棧和佇列也是線性表，是操作受限的線性表，它們的基本操作是線性表操作的子集，但從資料型別的角度來講，它們與線性表又有著巨大的不同。本節將首先介紹棧的定義和其不同實現，並且給出棧的一些實際應用。

通過本節學習，應掌握以下內容：

• 棧的基本概念及不同實現方法
• 棧基本操作的實現及時間複雜度
• 利用棧的基本操作實現複雜演演算法

1. 棧的基本概念

1.1 棧的基本概念

棧 (Stack) 是限定僅在序列一端執行插入和刪除操作的線性表，對於棧而言，可進行操作的一端稱為棧頂 (top)，而另一端稱為棧底 (bottom)。如果棧中不含任何元素則稱其為空棧。

棧提供了一種基於在集合中的時間來排序的方式，最近新增的元素靠近頂端，舊元素則靠近底端。最新新增的元素被最先移除，這種排序原則也稱為後進先出 (last in first out, LIFO) 或先進後出 (fast in last out, FILO)。

棧在現實中的例子隨處可見，如下圖所示，球桶中的球構成了一個棧，每次只能從頂部取出一個，放回時也只能置於頂部。假設棧為 S = ( a 0 , a 1 , … , a n ) S=(a_0, a_1, …, a_n) S=(a0​,a1​,…,an​)，則棧底元素為 a 0 a_0 a0​， a n a_n an​ 為棧頂元素，棧中元素按的順序入棧 (push)，而棧頂元素是第一個退棧 (pop) 的元素。

通過觀察元素的新增和移除順序，就可以快速理解棧所蘊含的思想。下圖展示了棧的入棧和出棧過程，棧中元素的插入順序和移除順序恰好是相反的。

1.2 棧抽象資料型別

除了主要的操作(入棧和出棧)外，棧還具有初始化、判空和取棧頂元素等輔助操作。具體而言，棧的抽象資料型別定義如下：

ADT Stack:
 資料物件： D = a i ∣ a i ∈ D a t a T y p e , i = 1 , 2 , . . . , n , n ≥ 0 D={a_i|a_i∈DataType, i=1,2,...,n,ngeq0} D=ai​∣ai​∈DataType,i=1,2,...,n,n≥0
 資料關係： R = < a i , a i + 1 > ∣ a i , a i + 1 ∈ D , i = 1 , 2 , . . . , n − 1 R={<a_{i},a_{i+1}>|a_i,a_{i+1}∈D,i=1,2,...,n-1} R=<ai​,ai+1​>∣ai​,ai+1​∈D,i=1,2,...,n−1
       a 1 a_1 a1​為棧底元素， a n a_n an​為棧頂元素
 基本操作：
  1. __itit__(): 初始化棧
   建立一個空棧
  2. size(): 求取並返回棧中所含元素的個數 n
   若棧為空，則返回整數0
  3. isempty(): 判斷是否為空棧
   判斷棧中是否儲存元素
  4. push(data): 入棧
   將元素 data 插入棧頂
  5. pop(): 出棧
   刪除並返回棧頂元素
  4. peek(): 取棧頂元素
   返回棧頂元素值，但並不刪除元素

1.3 棧的應用場景

棧具有廣泛的應用場景，例如：

• 符號的匹配，具體描述參考第3.3小節；
• 函數呼叫，每個未結束呼叫的函數都會在函數棧中擁有一塊資料區，儲存了函數的重要資訊，包括函數的區域性變數、引數等；
• 字尾表示式求值，計算字尾表示式只需一個用於存放數值的棧，遍歷表示式遇到數值則入棧，遇到運運算元則出棧兩個數值進行計算，並將計算結果入棧，最後棧中保留的唯一值即為表示式結果；
• 網頁瀏覽中的返回按鈕，當我們在網頁間進行跳轉時，這些網址都被存放在一個棧中；
• 編輯器中的復原序列，與網頁瀏覽中的返回按鈕類似，棧儲存每步的編輯操作。

除了以上應用外，我們在之後的學習中還將看到棧用作許多演演算法的輔助資料結構。

2. 棧的實現

和線性表一樣，棧同樣有兩種儲存表示方式。

2.1 順序棧的實現

順序棧是棧的順序儲存結構，其利用一組地址連續的儲存單元從棧底到棧頂依次存放。同時使用指標 top 來指示棧頂元素在順序棧中的索引，同樣順序棧可以是固定長度和動態長度，當棧滿時，定長順序棧會丟擲棧滿異常，動態順序棧則會動態申請空閒空間。

2.1.1 棧的初始化

順序棧的初始化需要三部分資訊：stack 列表用於儲存資料元素，max_size 用於儲存 stack 列表的最大長度，以及 top 用於記錄棧頂元素的索引：

class Stack:
    def __init__(self, max_size=10):
        self.max_size = max_size
        self.stack = self.max_size * [None]
        self.top = -1

2.1.2 求棧長

由於 top 表示棧頂元素的索引，我們可以據此方便的計算順序棧中的資料元素數量，即棧長：

    def size(self):
        return self.top + 1

2.1.3 判棧空

根據棧的長度可以很容易的判斷棧是否為空棧：

    def isempty(self):
        if self.size() == 0:
            return True
        else:
            return False

2.1.4 判棧滿

由於需要提前申請棧空間，因此我們需要能夠判斷棧是否還有空閒空間：

    def isfully(self):
        if self.size() == self.max_size:
            return True
        else:
            return False

2.1.5 入棧

入棧時，需要首先判斷棧中是否還有空閒空間，然後根據棧為定長順序棧或動態順序棧，入棧操作稍有不同：

[定長順序棧的入棧操作] 如果棧滿，則引發異常：

    def push(self, data):
        if self.isfully():
            raise IndexError('Stack Overflow!')
        else:
            self.top += 1
            self.stack[self.top_1] = data

[動態順序棧的入棧操作] 如果棧滿，則首先申請新空間：

    def resize(self):
        new_size = 2 * self.max_size
        new_stack = [None] * new_size
        for i in range(self.num_items):
            new_stack[i] = self.items[i]
        self.stack = new_stack
        self.max_size = new_size
    def push(self, data):
        if self.isfully():
            self.resize()
        else:
            self.top += 1
            self.stack[self.top_1] = data

入棧的時間複雜度為O(1)。這裡需要注意的是，雖然當動態順序棧滿時，原棧中的元素需要首先複製到新棧中，然後新增新元素，但根據《順序表及其操作實現》中順序表追加操作的介紹，由於 n 次入棧操作的總時間T(n) 與O(n) 成正比，因此入棧的攤銷時間複雜度仍可以認為是O(1)。

2.1.6 出棧

若棧不空，則刪除並返回棧頂元素：

    def pop(self):
        if self.isempty():
            raise IndexError('Stack Underflow!')
        else:
            result = self.stack[self.top]
            self.top -= 1
            return result

2.1.7 求棧頂元素

若棧不空，則只需返回棧頂元素：

    def pop(self):
        if self.isempty():
            raise IndexError('Stack Underflow!')
        else:
            result = self.stack[self.top]
            self.top -= 1
            return result

2.2 鏈棧的實現

棧的另一種儲存表示方式是使用鏈式儲存結構，因此也常稱為鏈棧，其中 push 操作是通過在連結串列頭部插入元素來實現的，pop 操作是通過從頭部刪除節點來實現的。

2.2.1 棧結點

棧的結點實現與連結串列並無差別：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
    def __str__(self):
        return str(self.data)

2.2.2 棧的初始化

棧的初始化函數中，使棧頂指標指向 None，並初始化棧長：

class Stack:
    def __init__(self):
        self.top = None
        # 棧中元素數
        self.length = 0

2.2.3 求棧長

返回 length 的值用於求取棧的長度，如果沒有 length 屬性，則需要遍歷整個連結串列才能得到棧長：

    def size(self):
        return self.length

2.2.4 判棧空

根據棧的長度可以很容易的判斷棧是否為空棧：

    def isempty(self):
        if self.length == 0:
            return True
        else:
            return False

2.2.5 入棧

入棧時，在棧頂插入新元素即可：

    def pop(self):
        if self.isempty():
            raise IndexError("Stack Underflow!")
        ele = self.top.data
        self.top = self.top.next
        self.length -= 1
        return ele

由於插入元素是在連結串列頭部進行的，因此入棧的時間複雜度為 O ( 1 ) O(1) O(1)，在這種情況下鏈尾作為棧底 。

2.2.6 出棧

若棧不空，則刪除並返回棧頂元素：

    def peek(self):
        if self.isempty():
            raise IndexError("Stack Underflow!")
        return self.top.data

由於刪除元素僅需修改頭指標指向其 next 域，因此出棧的時間複雜度同樣為 O ( 1 ) O(1) O(1)。

2.2.7 求棧頂元素

若棧不空，返回棧頂元素即可，但棧頂元素並不會被刪除：

    def peek(self):
        if self.isempty():
            raise IndexError("Stack Underflow!")
        return self.top.data

2.3 棧的不同實現對比

本節我們將對比棧的不同實現之間的異同：

• 順序棧
  • 操作的時間複雜度均為O(1)，列表的尾部作為棧頂
  • 棧滿時需要進行動態的擴充套件，複製原棧元素到新棧中
• 鏈棧
  • 操作的時間複雜度均為O(1)，連結串列的頭部作為棧頂
  • 優雅的擴充套件，無需考慮棧滿，需要額外的空間儲存指標

3. 棧應用

接下來，我們首先測試上述實現的連結串列，以驗證操作的有效性，然後利用實現的基本操作來解決實際演演算法問題。

3.1 順序棧的應用

首先初始化一個順序棧 stack，然後測試相關操作：

# 初始化一個最大長度為4的棧
s = Stack(4)
print('棧空?', s.isempty())
for i in range(4):
    print('入棧元素：', i)
    s.push(i)
print('棧滿?', s.isfully())
print('棧頂元素：', s.peek())
print('棧長度為：', s.size())
while not s.isempty():
    print('出棧元素：', s.pop())

測試程式輸出結果如下：

棧空? True
入棧元素： 0
入棧元素： 1
入棧元素： 2
入棧元素： 3
棧滿? True
棧頂元素： 3
棧長度為： 4
出棧元素： 3
出棧元素： 2
出棧元素： 1
出棧元素： 0

3.2 鏈棧的應用

首先初始化一個鏈棧 stack，然後測試相關操作：

# 初始化新棧
s = Stack()
print('棧空?', s.isempty())
for i in range(4):
    print('入棧元素：', i)
    s.push(i)
print('棧頂元素：', s.peek())
print('棧長度為：', s.size())
while not s.isempty():
    print('出棧元素：', s.pop())

測試程式輸出結果如下：

棧空? True
入棧元素： 0
入棧元素： 1
入棧元素： 2
入棧元素： 3
棧頂元素： 3
棧長度為： 4
出棧元素： 3
出棧元素： 2
出棧元素： 1
出棧元素： 0

3.3 利用棧基本操作實現複雜演演算法

[1] 匹配符號是指正確地匹配左右對應的符號(符號允許進行巢狀)，不僅每一個左符號都有一個右符號與之對應，而且兩個符號的型別也是一致的，下表展示了一些符號串的匹配情況：

為了檢查符號串的匹配情況，需要遍歷符號串，如果字元是 (、[ 或 { 之類的開始分隔符，則將其寫入棧中；當遇到諸如 )、] 或 } 等結束分隔符時，則棧頂元素出棧，並將其與當前遍歷元素進行比較，如果它們匹配，則繼續解析符號串，否則表示不匹配。當遍歷完成後，如果棧不為空，則同樣表示不匹配：

def isvalid_expression(expression):
    stack = Stack()
    symbols = {')':'(', ']':'[', '}':'{'}
    for s in expression:
        if s in symbols:
            if stack:
                top_element = stack.pop()
            else:
                top_element = '#'
            if symbols[s] != top_element:
                return False
        else:
            stack.push(s)
    return not stack

由於我們只需要遍歷符號串一邊，因此演演算法的時間複雜度為O(n)，演演算法的空間複雜度同樣為O(n)。

[2] 給定一連結串列(帶有頭結點) L : L 0 → L 1 → … → L n，將其重排為： L 0 → L n → L 1 → L n − 1 …

例如連結串列中包含 9 個元素，則下圖現實了重排前後的連結串列元素情況：

由於棧的先進後出原則，可以利用棧與原連結串列的配合進行重排，首次按遍歷連結串列，將每個結點入棧；棧中元素的出棧順序為原連結串列結點的逆序，然後交替遍歷連結串列和棧，構建新連結串列。

def reorder_list(L):
    p = L.head.next
    if p == None:
        return L
    stack = Stack()
    while p!= None:
        stack.push(p)
        p = p.next
    l = L.head.next
    from_head = L.head.next
    from_stack = True
    while (from_stack and l != stack.peek() or (not from_stack and l != from_head)):
        if from_stack:
            from_head = from_head.next
            l.next = stack.pop()
            from_stack = False
        else:
            l.next = from_head
            from_stack = True
        l = l.next
    l.next = None

該演演算法的時間複雜度和空間複雜度均為O(n)。

總結

本篇文章就到這裡了，希望能夠給你帶來幫助，也希望您能夠多多關注it145.com的更多內容!