0. 學(xué)習(xí)目標(biāo)

棧和隊(duì)列是在程序設(shè)計(jì)中常見的數(shù)據(jù)類型，從數(shù)據(jù)結(jié)構(gòu)的角度來講，棧和隊(duì)列也是線性表，是操作受限的線性表，它們的基本操作是線性表操作的子集，但從數(shù)據(jù)類型的角度來講，它們與線性表又有著巨大的不同。本節(jié)將首先介紹棧的定義和其不同實(shí)現(xiàn)，并且給出棧的一些實(shí)際應(yīng)用。

通過本節(jié)學(xué)習(xí)，應(yīng)掌握以下內(nèi)容：

• 棧的基本概念及不同實(shí)現(xiàn)方法
• 棧基本操作的實(shí)現(xiàn)及時(shí)間復(fù)雜度
• 利用棧的基本操作實(shí)現(xiàn)復(fù)雜算法

1. 棧的基本概念

1.1 棧的基本概念

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

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

棧在現(xiàn)實(shí)中的例子隨處可見，如下圖所示，球桶中的球構(gòu)成了一個(gè)棧，每次只能從頂部取出一個(gè)，放回時(shí)也只能置于頂部。假設(shè)棧為 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)，而棧頂元素是第一個(gè)退棧 (pop) 的元素。

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

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

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

ADT Stack:
 數(shù)據(jù)對(duì)象： 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,n\geq0} D=ai?∣ai?∈DataType,i=1,2,...,n,n≥0
 數(shù)據(jù)關(guān)系： 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__(): 初始化棧
   創(chuàng)建一個(gè)空棧
  2. size(): 求取并返回棧中所含元素的個(gè)數(shù) n
   若棧為空，則返回整數(shù)0
  3. isempty(): 判斷是否為空棧
   判斷棧中是否存儲(chǔ)元素
  4. push(data): 入棧
   將元素 data 插入棧頂
  5. pop(): 出棧
   刪除并返回棧頂元素
  4. peek(): 取棧頂元素
   返回棧頂元素值，但并不刪除元素

1.3 棧的應(yīng)用場(chǎng)景

棧具有廣泛的應(yīng)用場(chǎng)景，例如：

• 符號(hào)的匹配，具體描述參考第3.3小節(jié)；
• 函數(shù)調(diào)用，每個(gè)未結(jié)束調(diào)用的函數(shù)都會(huì)在函數(shù)棧中擁有一塊數(shù)據(jù)區(qū)，保存了函數(shù)的重要信息，包括函數(shù)的局部變量、參數(shù)等；
• 后綴表達(dá)式求值，計(jì)算后綴表達(dá)式只需一個(gè)用于存放數(shù)值的棧，遍歷表達(dá)式遇到數(shù)值則入棧，遇到運(yùn)算符則出棧兩個(gè)數(shù)值進(jìn)行計(jì)算，并將計(jì)算結(jié)果入棧，最后棧中保留的唯一值即為表達(dá)式結(jié)果；
• 網(wǎng)頁(yè)瀏覽中的返回按鈕，當(dāng)我們?cè)诰W(wǎng)頁(yè)間進(jìn)行跳轉(zhuǎn)時(shí)，這些網(wǎng)址都被存放在一個(gè)棧中；
• 編輯器中的撤銷序列，與網(wǎng)頁(yè)瀏覽中的返回按鈕類似，棧保存每步的編輯操作。

除了以上應(yīng)用外，我們?cè)谥蟮膶W(xué)習(xí)中還將看到棧用作許多算法的輔助數(shù)據(jù)結(jié)構(gòu)。

2. 棧的實(shí)現(xiàn)

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

2.1 順序棧的實(shí)現(xiàn)

順序棧是棧的順序存儲(chǔ)結(jié)構(gòu)，其利用一組地址連續(xù)的存儲(chǔ)單元從棧底到棧頂依次存放。同時(shí)使用指針 top 來指示棧頂元素在順序棧中的索引，同樣順序棧可以是固定長(zhǎng)度和動(dòng)態(tài)長(zhǎng)度，當(dāng)棧滿時(shí)，定長(zhǎng)順序棧會(huì)拋出棧滿異常，動(dòng)態(tài)順序棧則會(huì)動(dòng)態(tài)申請(qǐng)空閑空間。

2.1.1 棧的初始化

順序棧的初始化需要三部分信息：stack 列表用于存儲(chǔ)數(shù)據(jù)元素，max_size 用于存儲(chǔ) stack 列表的最大長(zhǎng)度，以及 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 求棧長(zhǎng)

由于 top 表示棧頂元素的索引，我們可以據(jù)此方便的計(jì)算順序棧中的數(shù)據(jù)元素?cái)?shù)量，即棧長(zhǎng)：

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

2.1.3 判棧空

根據(jù)棧的長(zhǎng)度可以很容易的判斷棧是否為空棧：

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

2.1.4 判棧滿

由于需要提前申請(qǐng)?？臻g，因此我們需要能夠判斷棧是否還有空閑空間：

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

2.1.5 入棧

入棧時(shí)，需要首先判斷棧中是否還有空閑空間，然后根據(jù)棧為定長(zhǎng)順序?；騽?dòng)態(tài)順序棧，入棧操作稍有不同：

[定長(zhǎng)順序棧的入棧操作] 如果棧滿，則引發(fā)異常：

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

[動(dòng)態(tài)順序棧的入棧操作] 如果棧滿，則首先申請(qǐng)新空間：

    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

入棧的時(shí)間復(fù)雜度為O(1)。這里需要注意的是，雖然當(dāng)動(dòng)態(tài)順序棧滿時(shí)，原棧中的元素需要首先復(fù)制到新棧中，然后添加新元素，但根據(jù)《順序表及其操作實(shí)現(xiàn)》中順序表追加操作的介紹，由于 n 次入棧操作的總時(shí)間T(n) 與O(n) 成正比，因此入棧的攤銷時(shí)間復(fù)雜度仍可以認(rè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 鏈棧的實(shí)現(xiàn)

棧的另一種存儲(chǔ)表示方式是使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因此也常稱為鏈棧，其中 push 操作是通過在鏈表頭部插入元素來實(shí)現(xiàn)的，pop 操作是通過從頭部刪除節(jié)點(diǎn)來實(shí)現(xiàn)的。

2.2.1 棧結(jié)點(diǎn)

棧的結(jié)點(diǎn)實(shí)現(xiàn)與鏈表并無差別：

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

2.2.2 棧的初始化

棧的初始化函數(shù)中，使棧頂指針指向 None，并初始化棧長(zhǎng)：

class Stack:
    def __init__(self):
        self.top = None
        # 棧中元素?cái)?shù)
        self.length = 0

2.2.3 求棧長(zhǎng)

返回 length 的值用于求取棧的長(zhǎng)度，如果沒有 length 屬性，則需要遍歷整個(gè)鏈表才能得到棧長(zhǎng)：

    def size(self):
        return self.length

2.2.4 判?？?/h4>

根據(jù)棧的長(zhǎng)度可以很容易的判斷棧是否為空棧：

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

2.2.5 入棧

入棧時(shí)，在棧頂插入新元素即可：

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

由于插入元素是在鏈表頭部進(jìn)行的，因此入棧的時(shí)間復(fù)雜度為 O ( 1 ) O(1) O(1)，在這種情況下鏈尾作為棧底 。

2.2.6 出棧

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

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

由于刪除元素僅需修改頭指針指向其 next 域，因此出棧的時(shí)間復(fù)雜度同樣為 O ( 1 ) O(1) O(1)。

2.2.7 求棧頂元素

若棧不空，返回棧頂元素即可，但棧頂元素并不會(huì)被刪除：

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

2.3 棧的不同實(shí)現(xiàn)對(duì)比

本節(jié)我們將對(duì)比棧的不同實(shí)現(xiàn)之間的異同：

• 順序棧
  • 操作的時(shí)間復(fù)雜度均為O(1)，列表的尾部作為棧頂
  • 棧滿時(shí)需要進(jìn)行動(dòng)態(tài)的擴(kuò)展，復(fù)制原棧元素到新棧中
• 鏈棧
  • 操作的時(shí)間復(fù)雜度均為O(1)，鏈表的頭部作為棧頂
  • 優(yōu)雅的擴(kuò)展，無需考慮棧滿，需要額外的空間存儲(chǔ)指針

3. 棧應(yīng)用

接下來，我們首先測(cè)試上述實(shí)現(xiàn)的鏈表，以驗(yàn)證操作的有效性，然后利用實(shí)現(xiàn)的基本操作來解決實(shí)際算法問題。

3.1 順序棧的應(yīng)用

首先初始化一個(gè)順序棧 stack，然后測(cè)試相關(guān)操作：

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

測(cè)試程序輸出結(jié)果如下：

棧空? True
入棧元素： 0
入棧元素： 1
入棧元素： 2
入棧元素： 3
棧滿? True
棧頂元素： 3
棧長(zhǎng)度為： 4
出棧元素： 3
出棧元素： 2
出棧元素： 1
出棧元素： 0

3.2 鏈棧的應(yīng)用

首先初始化一個(gè)鏈棧 stack，然后測(cè)試相關(guān)操作：

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

測(cè)試程序輸出結(jié)果如下：

?？? True
入棧元素： 0
入棧元素： 1
入棧元素： 2
入棧元素： 3
棧頂元素： 3
棧長(zhǎng)度為： 4
出棧元素： 3
出棧元素： 2
出棧元素： 1
出棧元素： 0

3.3 利用?；静僮鲗?shí)現(xiàn)復(fù)雜算法

[1] 匹配符號(hào)是指正確地匹配左右對(duì)應(yīng)的符號(hào)(符號(hào)允許進(jìn)行嵌套)，不僅每一個(gè)左符號(hào)都有一個(gè)右符號(hào)與之對(duì)應(yīng)，而且兩個(gè)符號(hào)的類型也是一致的，下表展示了一些符號(hào)串的匹配情況：

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

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

由于我們只需要遍歷符號(hào)串一邊，因此算法的時(shí)間復(fù)雜度為O(n)，算法的空間復(fù)雜度同樣為O(n)。

[2] 給定一鏈表(帶有頭結(jié)點(diǎn)) L : L 0 → L 1 → … → L n，將其重排為： L 0 → L n → L 1 → L n − 1 …

例如鏈表中包含 9 個(gè)元素，則下圖現(xiàn)實(shí)了重排前后的鏈表元素情況：

由于棧的先進(jìn)后出原則，可以利用棧與原鏈表的配合進(jìn)行重排，首次按遍歷鏈表，將每個(gè)結(jié)點(diǎn)入棧；棧中元素的出棧順序?yàn)樵湵斫Y(jié)點(diǎn)的逆序，然后交替遍歷鏈表和棧，構(gòu)建新鏈表。

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

該算法的時(shí)間復(fù)雜度和空間復(fù)雜度均為O(n)。

總結(jié)

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容! 

最新評(píng)論