傳智播客旗下品牌:|||||

全國咨詢/投訴熱線:400-618-4000

“棧”是什么?如何實現一個“棧”?

更新時間:2020年08月03日14時22分 來源:傳智播客 瀏覽次數:

如何理解“棧”?

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

python棧

從棧的操作特性上來看,棧是一種“操作受限”的線性表,只允許在一端插入和刪除數據

我第一次接觸這種數據結構的時候,就對它存在的意義產生了很大的疑惑。因為我覺得,相比數組和鏈表,棧帶給我的只有限制,并沒有任何優勢。那我直接使用數組或者鏈表不就好了嗎?為什么還要用這個“操作受限”的“棧”呢?

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

當某個數據集合只涉及在一端插入和刪除數據,并且滿足后進先出、先進后出的特性,我們就應該首選“棧”這種數據結構。

如何實現一個“棧”?

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

實際上,棧既可以用數組來實現,也可以用鏈表來實現。用數組實現的棧,我們叫作順序棧,用鏈表實現的棧,我們叫作鏈式棧。

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

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

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

支持動態擴容的順序棧

如果要實現一個支持動態擴容的棧,我們只需要底層依賴一個支持動態擴容的數組就可以了。當棧滿了之后,我們就申請一個更大的數組,將原來的數據搬移到新數組中。

實際上,支持動態擴容的順序棧,我們平時開發中并不常用到。

入棧、出棧的時間復雜度:

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

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

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

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

通過這個例子的實戰分析,也印證了前面講到的,均攤時間復雜度一般都等于最好情況時間復雜度。因為在大部分情況下,入棧操作的時間復雜度 O 都是 O(1),只有在個別時刻才會退化為 O(n),所以把耗時多的入棧操作的時間均攤到其他入棧操作上,平均情況下的耗時就接近 O(1)。

棧在括號匹配中的應用

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

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

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

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

內容小結

棧是一種操作受限的數據結構,只支持入棧和出棧操作。后進先出是它最大的特點。棧既可以通過數組實現,也可以通過鏈表來實現。不管基于數組還是鏈表,入棧、出棧的時間復雜度都為 O(1)。除此之外,我們還講了一種支持動態擴容的順序棧。


猜你喜歡:

Python垃圾回收機制是什么? 

python反射以及應用場景