欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python數(shù)據(jù)結(jié)構(gòu)與算法中的棧詳解

 更新時(shí)間:2022年03月13日 18:47:20   作者:盼小輝丶  
這篇文章主要為大家詳細(xì)介紹了Python數(shù)據(jù)結(jié)構(gòu)與算法中的棧,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助

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í)行插入和刪除操作的線性表,對于棧而言,可進(jìn)行操作的一端稱為棧頂 (top),而另一端稱為棧底 (bottom)。如果棧中不含任何元素則稱其為空棧。

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

棧在現(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)含的思想。下圖展示了棧的入棧和出棧過程,棧中元素的插入順序和移除順序恰好是相反的。

棧的反轉(zhuǎn)特性

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

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

ADT Stack:
 數(shù)據(jù)對象: 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(): 判斷是否為空棧
   判斷棧中是否存儲元素
  4. push(data): 入棧
   將元素 data 插入棧頂
  5. pop(): 出棧
   刪除并返回棧頂元素
  4. peek(): 取棧頂元素
   返回棧頂元素值,但并不刪除元素

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

棧具有廣泛的應(yīng)用場景,例如:

  • 符號的匹配,具體描述參考第3.3小節(jié);
  • 函數(shù)調(diào)用,每個(gè)未結(jié)束調(diào)用的函數(shù)都會在函數(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)頁瀏覽中的返回按鈕,當(dāng)我們在網(wǎng)頁間進(jìn)行跳轉(zhuǎn)時(shí),這些網(wǎng)址都被存放在一個(gè)棧中;
  • 編輯器中的撤銷序列,與網(wǎng)頁瀏覽中的返回按鈕類似,棧保存每步的編輯操作。

除了以上應(yīng)用外,我們在之后的學(xué)習(xí)中還將看到棧用作許多算法的輔助數(shù)據(jù)結(jié)構(gòu)。

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

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

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

順序棧是棧的順序存儲結(jié)構(gòu),其利用一組地址連續(xù)的存儲單元從棧底到棧頂依次存放。同時(shí)使用指針 top 來指示棧頂元素在順序棧中的索引,同樣順序??梢允枪潭ㄩL度和動態(tài)長度,當(dāng)棧滿時(shí),定長順序棧會拋出棧滿異常,動態(tài)順序棧則會動態(tài)申請空閑空間。

2.1.1 棧的初始化

順序棧的初始化需要三部分信息:stack 列表用于存儲數(shù)據(jù)元素,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 表示棧頂元素的索引,我們可以據(jù)此方便的計(jì)算順序棧中的數(shù)據(jù)元素?cái)?shù)量,即棧長:

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

2.1.3 判???/h4>

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

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

2.1.4 判棧滿

由于需要提前申請??臻g,因此我們需要能夠判斷棧是否還有空閑空間:

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

2.1.5 入棧

入棧時(shí),需要首先判斷棧中是否還有空閑空間,然后根據(jù)棧為定長順序?;騽討B(tài)順序棧,入棧操作稍有不同:

[定長順序棧的入棧操作] 如果棧滿,則引發(fā)異常:

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

[動態(tài)順序棧的入棧操作] 如果棧滿,則首先申請新空間:

    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)動態(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)

棧的另一種存儲表示方式是使用鏈?zhǔn)酱鎯Y(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,并初始化棧長:

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

2.2.3 求棧長

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

    def size(self):
        return self.length

2.2.4 判???/h4>

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

    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 求棧頂元素

若棧不空,返回棧頂元素即可,但棧頂元素并不會被刪除:

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

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

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

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

3. 棧應(yīng)用

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

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

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

# 初始化一個(gè)最大長度為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())

測試程序輸出結(jié)果如下:

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

3.2 鏈棧的應(yīng)用

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

# 初始化新棧
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())

測試程序輸出結(jié)果如下:

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

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

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

符號串是否匹配
[]()()匹配
[(())()不匹配
{([]())}匹配
(())[]}不匹配

為了檢查符號串的匹配情況,需要遍歷符號串,如果字符是 ([ 或 { 之類的開始分隔符,則將其寫入棧中;當(dāng)遇到諸如 )、] 或 } 等結(jié)束分隔符時(shí),則棧頂元素出棧,并將其與當(dāng)前遍歷元素進(jìn)行比較,如果它們匹配,則繼續(xù)解析符號串,否則表示不匹配。當(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

由于我們只需要遍歷符號串一邊,因此算法的時(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)容! 

相關(guān)文章

最新評論