最近晚上在家裡看Algorithems，4th Edition，我買的英文版，覺得這本書寫的比較淺顯易懂，而且“圖碼並茂”，趁著這次機會打算好好學習做做筆記，這樣也會印象深刻，這也是寫這一系列文章的原因。另外普林斯頓大學在Coursera 上也有這本書同步的公開課，還有另外一門算法分析課，這門課程的作者也是這本書的作者，兩門課都挺不錯的。
計算機程序離不開算法和數據結構，本文簡單介紹棧(Stack實現，典型應用等，希望能加深自己對這個簡單數據結構的理解。
基本概念
概念很簡單，棧 (Stack)是一種後進先出(last in first off，LIFO)的數據結構，如下圖：
對於Stack 我們希望至少要對外提供以下幾個方法：
要實現這些功能，我們有兩中方法，數組和鏈表，先看鏈表實現。
棧的鏈表實現
我們首先定義一個內部類來保存每個鏈表的節點，該節點包括當前的值以及指向下一個的值，然後建立一個節點保存位於棧頂的值以及記錄棧的元素個數;
現在來實現Push方法，即向棧頂壓入一個元素，首先保存原先的位於棧頂的元素，然後新建一個新的棧頂元素，然後將該元素的下一個指向原先的棧頂元素。整個Pop過程如下：
實現代碼如下：
Pop方法也很簡單，首先保存棧頂元素的值，然後將棧頂元素設置為下一個元素：
基於鏈表的Stack實現，在最壞的情況下只需要常量的時間來進行Push和Pop操作。
棧的數組實現
我們可以使用數組來存儲棧中的元素Push的時候，直接添加一個元素S[N]到數組中，Pop的時候直接返回S[N-1].
首先，我們定義一個數組，然後在構造函數中給定初始化大小，Push方法實現如下，就是集合裡添加一個元素：
Pop方法：
在Push和Pop方法中，為了節省內存空間，我們會對數組進行整理。Push的時候，當元素的個數達到數組的Capacity的時候，我們開闢2倍於當前元素的新數組，然後將原數組中的元素拷貝到新數組中。Pop的時候，當元素的個數小於當前容量的1/4的時候，我們將原數組的大小容量減少1/2。
Resize方法基本就是數組複製：
當我們縮小數組的時候，採用的是判斷1/4的情況，這樣效率要比1/2要高，因為可以有效避免在1/2附件插入，刪除，插入，刪除，從而頻繁的擴大和縮小數組的情況。下圖展示了在插入和刪除的情況下數組中的元素以及數組大小的變化情況：
分析：1. Pop和Push操作在最壞的情況下與元素個數成比例的N的時間，時間主要花費在擴大或者縮小數組的個數時，數組拷貝上;2. 元素在內存中分佈緊湊，密度高，便於利用內存的時間和空間局部性，便於CPU進行緩存，較LinkList內存佔用小，效率高。
棧的應用
Stack使用的一個最經典的例子就是算術表達式的求值了，這其中還包括前綴表達式和後綴表達式的求值。E. W. Dijkstra發明了使用兩個Stack，一個保存操作值，一個保存操作符的方法來實現表達式的求值，具體步驟如下：
1：當輸入的是值的時候Push到屬於值的棧中;
2：當輸入的是運算符的時候，Push到運算符的棧中;
3：當遇到左括號的時候，忽略;
4：當遇到右括號的時候，Pop一個運算符，Pop兩個值，然後將計算結果Push到值的棧中。
下面是在C#中的一個簡單的括號表達式的求值：
運行結果如下：
下圖演示了操作棧和數據棧的變化。
寫在最後
get最新最全的IT技能，免費領取各種編程資料（Java、python、前端、大數據、區塊鏈....）
閱讀更多 傳智播客博學谷 的文章
