首頁(yè)技術(shù)文章正文

如何理解“?!??如何實(shí)現(xiàn)一個(gè)“棧”?

更新時(shí)間:2020-08-03 來(lái)源:黑馬程序員 瀏覽量:

如何理解“?!?

關(guān)于“?!保矣幸粋€(gè)非常貼切的例子,就是一摞疊在一起的盤(pán)子。我們平時(shí)放盤(pán)子的時(shí)候,都是從下往上一個(gè)一個(gè)放;取的時(shí)候,我們也是從上往下一個(gè)一個(gè)地依次取,不能從中間任意抽出。后進(jìn)者先出,先進(jìn)者后出,這就是典型的“棧”結(jié)構(gòu)。

python棧


從棧的操作特性上來(lái)看,棧是一種“操作受限”的線性表,只允許在一端插入和刪除數(shù)據(jù)。

我第一次接觸這種數(shù)據(jù)結(jié)構(gòu)的時(shí)候,就對(duì)它存在的意義產(chǎn)生了很大的疑惑。因?yàn)槲矣X(jué)得,相比數(shù)組和鏈表,棧帶給我的只有限制,并沒(méi)有任何優(yōu)勢(shì)。那我直接使用數(shù)組或者鏈表不就好了嗎?為什么還要用這個(gè)“操作受限”的“?!蹦?

事實(shí)上,從功能上來(lái)說(shuō),數(shù)組或鏈表確實(shí)可以替代棧,但你要知道,特定的數(shù)據(jù)結(jié)構(gòu)是對(duì)特定場(chǎng)景的抽象,而且,數(shù)組或鏈表暴露了太多的操作接口,操作上的確靈活自由,但使用時(shí)就比較不可控,自然也就更容易出錯(cuò)。

當(dāng)某個(gè)數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù),并且滿足后進(jìn)先出、先進(jìn)后出的特性,我們就應(yīng)該首選“?!边@種數(shù)據(jù)結(jié)構(gòu)。

如何實(shí)現(xiàn)一個(gè)“?!?

從剛才棧的定義里,我們可以看出,棧主要包含兩個(gè)操作,入棧和出棧,也就是在棧頂插入一個(gè)數(shù)據(jù)和從棧頂刪除一個(gè)數(shù)據(jù)。理解了棧的定義之后,我們來(lái)看一看如何用代碼實(shí)現(xiàn)一個(gè)棧。

實(shí)際上,棧既可以用數(shù)組來(lái)實(shí)現(xiàn),也可以用鏈表來(lái)實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的棧,我們叫作順序棧,用鏈表實(shí)現(xiàn)的棧,我們叫作鏈?zhǔn)綏!?/p>

不管是順序棧還是鏈?zhǔn)綏?,我們存?chǔ)數(shù)據(jù)只需要一個(gè)大小為 n 的數(shù)組就夠了。在入棧和出棧過(guò)程中,只需要一兩個(gè)臨時(shí)變量存儲(chǔ)空間,所以空間復(fù)雜度是 O(1)。

注意,這里存儲(chǔ)數(shù)據(jù)需要一個(gè)大小為 n 的數(shù)組,并不是說(shuō)空間復(fù)雜度就是 O(n)。因?yàn)?,這 n 個(gè)空間是必須的,無(wú)法省掉。所以我們說(shuō)空間復(fù)雜度的時(shí)候,是指除了原本的數(shù)據(jù)存儲(chǔ)空間外,算法運(yùn)行還需要額外的存儲(chǔ)空間。

空間復(fù)雜度分析是不是很簡(jiǎn)單?時(shí)間復(fù)雜度也不難。不管是順序棧還是鏈?zhǔn)綏?,入棧、出棧只涉及棧頂個(gè)別數(shù)據(jù)的操作,所以時(shí)間復(fù)雜度都是 O(1)。

支持動(dòng)態(tài)擴(kuò)容的順序棧

如果要實(shí)現(xiàn)一個(gè)支持動(dòng)態(tài)擴(kuò)容的棧,我們只需要底層依賴一個(gè)支持動(dòng)態(tài)擴(kuò)容的數(shù)組就可以了。當(dāng)棧滿了之后,我們就申請(qǐng)一個(gè)更大的數(shù)組,將原來(lái)的數(shù)據(jù)搬移到新數(shù)組中。

實(shí)際上,支持動(dòng)態(tài)擴(kuò)容的順序棧,我們平時(shí)開(kāi)發(fā)中并不常用到。

入棧、出棧的時(shí)間復(fù)雜度:

對(duì)于出棧操作來(lái)說(shuō),我們不會(huì)涉及內(nèi)存的重新申請(qǐng)和數(shù)據(jù)的搬移,所以出棧的時(shí)間復(fù)雜度仍然是 O(1)。但是,對(duì)于入棧操作來(lái)說(shuō),情況就不一樣了。當(dāng)棧中有空閑空間時(shí),入棧操作的時(shí)間復(fù)雜度為 O(1)。但當(dāng)空間不夠時(shí),就需要重新申請(qǐng)內(nèi)存和數(shù)據(jù)搬移,所以時(shí)間復(fù)雜度就變成了 O(n)。

也就是說(shuō),對(duì)于入棧操作來(lái)說(shuō),最好情況時(shí)間復(fù)雜度是 O(1),最壞情況時(shí)間復(fù)雜度是 O(n)。那平均情況下的時(shí)間復(fù)雜度又是多少呢?

如果當(dāng)前棧大小為 K,并且已滿,當(dāng)再有新的數(shù)據(jù)要入棧時(shí),就需要重新申請(qǐng) 2 倍大小的內(nèi)存,并且做 K 個(gè)數(shù)據(jù)的搬移操作,然后再入棧。但是,接下來(lái)的 K-1 次入棧操作,我們都不需要再重新申請(qǐng)內(nèi)存和搬移數(shù)據(jù),所以這 K-1 次入棧操作都只需要一個(gè) simple-push 操作就可以完成。

你應(yīng)該可以看出來(lái),這 K 次入棧操作,總共涉及了 K 個(gè)數(shù)據(jù)的搬移,以及 K 次 simple-push 操作。將 K 個(gè)數(shù)據(jù)搬移均攤到 K 次入棧操作,那每個(gè)入棧操作只需要一個(gè)數(shù)據(jù)搬移和一個(gè) simple-push 操作。以此類推,入棧操作的均攤時(shí)間復(fù)雜度就為 O(1)。

通過(guò)這個(gè)例子的實(shí)戰(zhàn)分析,也印證了前面講到的,均攤時(shí)間復(fù)雜度一般都等于最好情況時(shí)間復(fù)雜度。因?yàn)樵诖蟛糠智闆r下,入棧操作的時(shí)間復(fù)雜度 O 都是 O(1),只有在個(gè)別時(shí)刻才會(huì)退化為 O(n),所以把耗時(shí)多的入棧操作的時(shí)間均攤到其他入棧操作上,平均情況下的耗時(shí)就接近 O(1)。

棧在括號(hào)匹配中的應(yīng)用

我們可以借助棧來(lái)檢查表達(dá)式中的括號(hào)是否匹配。

我們同樣簡(jiǎn)化一下背景。我們假設(shè)表達(dá)式中只包含三種括號(hào),圓括號(hào) ()、方括號(hào)[]和花括號(hào){},并且它們可以任意嵌套。比如,{[] ()[{}]}或[{()}([])]等都為合法格式,而{[}()]或[({)]為不合法的格式。那我現(xiàn)在給你一個(gè)包含三種括號(hào)的表達(dá)式字符串,如何檢查它是否合法呢?

這里也可以用棧來(lái)解決。我們用棧來(lái)保存未匹配的左括號(hào),從左到右依次掃描字符串。當(dāng)掃描到左括號(hào)時(shí),則將其壓入棧中;當(dāng)掃描到右括號(hào)時(shí),從棧頂取出一個(gè)左括號(hào)。如果能夠匹配,比如“(”跟“)”匹配,“[”跟“]”匹配,“{”跟“}”匹配,則繼續(xù)掃描剩下的字符串。如果掃描的過(guò)程中,遇到不能配對(duì)的右括號(hào),或者棧中沒(méi)有數(shù)據(jù),則說(shuō)明為非法格式。

當(dāng)所有的括號(hào)都掃描完成之后,如果棧為空,則說(shuō)明字符串為合法格式;否則,說(shuō)明有未匹配的左括號(hào),為非法格式。

內(nèi)容小結(jié)

棧是一種操作受限的數(shù)據(jù)結(jié)構(gòu),只支持入棧和出棧操作。后進(jìn)先出是它最大的特點(diǎn)。棧既可以通過(guò)數(shù)組實(shí)現(xiàn),也可以通過(guò)鏈表來(lái)實(shí)現(xiàn)。不管基于數(shù)組還是鏈表,入棧、出棧的時(shí)間復(fù)雜度都為 O(1)。除此之外,我們還講了一種支持動(dòng)態(tài)擴(kuò)容的順序棧。


猜你喜歡:

Python垃圾回收機(jī)制是什么? 

python反射以及應(yīng)用場(chǎng)景 

黑馬程序員Python培訓(xùn)課程

分享到:
在線咨詢 我要報(bào)名
和我們?cè)诰€交談!