文章目錄 如何了解“棧”？ python：棧的了解與應用 如何實作一個“棧”？ 棧在括号比對中的應用 内容小結 如何了解“棧”？ 關于“棧”，我有一個非常貼切的例子，就是一摞疊在一起的盤子。我們平時放盤子的時候，都是從下往上一個一個放；取的時候，我們也是從上往下一個一個地依次取，不能從中間任意抽出。後進者先出，先進者後出，這就是典型的“棧”結構。
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)。除此之外，我們還講了一種支援動态擴容的順序棧.