“?！笔鞘裁?？如何實(shí)現(xiàn)一個“?！?

如何理解“棧”?

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

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

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

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

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

如何實(shí)現(xiàn)一個“棧”?

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

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

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

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

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

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

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

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

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

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

也就是說，對于入棧操作來說，最好情況時間復(fù)雜度是 O(1)，最壞情況時間復(fù)雜度是 O(n)。那平均情況下的時間復(fù)雜度又是多少呢?

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

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

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

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

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

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

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

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

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

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


猜你喜歡：

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

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

傳智播客Python培訓(xùn)課程