Python數(shù)據(jù)結(jié)構(gòu)與算法中的棧詳解
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 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ù)對象: 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)文章
Python+OpenCV圖像處理——圖像二值化的實(shí)現(xiàn)
這篇文章主要介紹了Python+OpenCV實(shí)現(xiàn)圖像二值化,幫助大家更好的利用python處理圖片,感興趣的朋友可以了解下2020-10-10pytorch快速搭建神經(jīng)網(wǎng)絡(luò)_Sequential操作
這篇文章主要介紹了pytorch快速搭建神經(jīng)網(wǎng)絡(luò)_Sequential操作,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06Python Web靜態(tài)服務(wù)器非堵塞模式實(shí)現(xiàn)方法示例
這篇文章主要介紹了Python Web靜態(tài)服務(wù)器非堵塞模式實(shí)現(xiàn)方法,結(jié)合實(shí)例形式分析了Python單進(jìn)程非堵塞模式實(shí)現(xiàn)的Web靜態(tài)服務(wù)器相關(guān)操作技巧,需要的朋友可以參考下2019-11-11Python shelve模塊實(shí)現(xiàn)解析
這篇文章主要介紹了Python shelve模塊實(shí)現(xiàn)解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-08-08利用Python實(shí)現(xiàn)網(wǎng)站自動簽到
小五收藏了一些論壇網(wǎng)站,經(jīng)常需要自己登錄簽到,以此來獲得積分金幣等等。但天天手動太容易忘了這件事啦。畢竟我們都會用python了,那就可以使用Selenium操作,接下來就和大家講講如何利用Python實(shí)現(xiàn)網(wǎng)站自動簽到2022-08-08TensorFlow命名空間和TensorBoard圖節(jié)點(diǎn)實(shí)例
今天小編就為大家分享一篇TensorFlow命名空間和TensorBoard圖節(jié)點(diǎn)實(shí)例,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-01-01ansible-playbook實(shí)現(xiàn)自動部署KVM及安裝python3的詳細(xì)教程
這篇文章主要介紹了ansible-playbook實(shí)現(xiàn)自動部署KVM及安裝python3的詳細(xì)教程,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-05-05詳解Python如何循環(huán)遍歷Numpy中的Array
Numpy是Python中常見的數(shù)據(jù)處理庫,是數(shù)據(jù)科學(xué)中經(jīng)常使用的庫。在本文中,我們將學(xué)習(xí)如何迭代遍歷訪問矩陣中的元素,需要的可以參考一下2022-04-04python解決報(bào)錯(cuò)ImportError: Bad git executable.問題
這篇文章主要介紹了python解決報(bào)錯(cuò)ImportError: Bad git executable.問題。具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-06-06