原本今天想給大家講講快速選擇算法的，但是發現一連寫了好幾篇排序相關了，所以臨時改了題目，今天聊點數據結構，來看看經典並且簡單的數據結構——棧。
棧這個結構我想大家應該都耳熟能詳，尤其是在很多地方將和堆並列在一起，稱作“堆棧”就更廣為人知了。但其實堆和棧本質上是兩種不同的數據結構，我們不能簡單地混為一談。讓我們先從比較簡單的棧開始。
棧和隊列的本質其實都是數組（嚴格地說是線性表）。只不過我們在數組上增加了一些限制，使得它滿足一定的條件而已，所以很多對數據結構畏首畏尾的同學可以放寬心，棧沒什麼特別的花樣，就是一種特殊的數組。
和其他廣義上的線性表數據結構比起來，棧的特殊性只有兩條，一條是先進後出，另一條是隻能從數組的一側讀寫。但本質上來說這兩條是一樣的，由於我們只能從一側讀寫元素，所以進的越早出的越晚，當然是先進後出。從下面這張圖應該很容易能看明白。
棧規定了我們只能從一側進行讀寫，常規上我們將能夠讀寫的一側稱作是棧頂。不能讀寫的另一側稱為是棧底。從上面的圖可以看到，只有棧頂的元素出棧了之後，才能訪問到棧底的元素。
我們用Python的數組來實現棧這個數據結構，去掉註釋真的只有30行不到，可以說是非常簡單，我們先來看代碼。
本質上來說，一般的棧實現只有以上這麼幾個方法，可能會更少。因為有些語言當中的棧，top和彈出是合併的。意味著訪問必須要彈出，不支持非彈出訪問。所以棧的實現邏輯是非常簡單的，甚至可以說是毫無技術含量，非常適合入門數據結構。
當然，從另一個方面也可以說棧的實現原理並不太重要，相比之下更重要的是棧一般會用在什麼地方。
棧的應用
棧最廣泛的應用就是在操作系統當中，比如在程序執行調用方法的時候，在編譯器內部，其實是記錄了一個當前調用的方法棧。舉個例子，比如當前調用到的方法是A，如果在A方法中又去調用了方法B，那麼計算機就會在系統方法棧當中存儲一個指向B方法的指針，如果B方法又調用到了C方法，那麼又會新增一個C的指針。當C方法執行結束，那麼C就會彈出，計算機會將C的結果帶入B，繼續執行之前的B，以此類推，直到棧空為止。
那麼，問題來了，如果一個方法A自己調用自己會怎麼樣？
答案是計算機會創建一個新的A的指針填入棧中，如果A繼續遞歸，那麼系統再創建一個新的指針入棧……
從上面這個過程，我們可以確定兩個事情。第一，我們寫程序時候的遞歸，在編譯器內部其實是以棧的形式執行的。第二，如果我們用一個死循環去不停地遞歸，由於棧存在大小限制，所以當棧的深度超過限制的時候，就會出現SystemStackExceed的錯誤。也就是說遞歸併不是無限的，因為除了操作系統對於運行內存的限制之外，編譯器還會有最大遞歸深度的限制，防止遞歸中死循環導致系統崩潰。雖然各個語言實現機制不完全一樣，但是有一點是肯定的，遞歸深度是有限的，我們不能無限制遞歸 。
那問題來了，如果我們系統就是會存在大規模的遞歸怎麼辦？難道還要手動給機器加內存嗎？
這是ACM玩家在賽場上經常遇到的問題之一，有經驗的選手在第一天的熱身賽時一定會做的事情除了配置vim或者其他IDE之外，就是會測試一下電腦的最大遞歸深度。在C++當中，是支持通過彙編語言強行打開遞歸深度限制的，但是即使如此也是有限的，並且據我所知只有C++可以這麼幹，對於其他語言，以及開大了遞歸深度還是不夠用的情況，就只有一種辦法，就是手動建棧模擬遞歸。
手動遞歸
許多同學可能覺得遞歸痛苦，但是如果他們試著手動建棧來模擬遞歸的話，會發現要更加痛苦。不僅要額外增加變量存儲中間狀態，並且對於編程也是一個巨大的挑戰。
我們來看一個例子：
這是一棵簡單的二叉樹，畫出來是這個樣子：
下面我們要通過棧在不使用遞歸的情況下來中序遍歷它，中序遍歷我們都知道，就是先遍歷左子樹，然後輸出當前節點，再遍歷右子樹。寫成遞歸非常方便，只有幾行：
大家想想，如果不使用遞歸應該怎麼辦？如果你真的試著去寫，就會發現看起來很簡單的問題好像變得非常複雜。我們很容易可以想到，我們把節點存儲在棧當中，但是存儲數據只是表象。本質問題是當我們從棧當中拿到了一個節點之後，我們怎麼判斷它究竟應該做什麼？應該遍歷左節點嗎，應該輸出嗎，還是應該遍歷右節點？
對這些問題仔細分析和思考，我們可以發現它們都和遞歸的回溯有關。
在遞歸當中，當我們遍歷完了當前節點的某棵子樹之後，隨著棧的彈出，還會回到這個節點。比如上面這棵樹當中，在遞歸過程當中，我們會兩次碰到1這個節點。第一次時它不會輸出1，而是先去遍歷了它的左子樹，也就是3，之後再次回到1，由於它的左子樹已經遍歷過，所以會輸出1。這個離開又回來的過程稱為
回溯。如果你把樹結構想象成瀑布的話，這個過程有點像是先順流而下，又逆流而上返回，backtracking翻譯成回溯還是蠻合理的。我們回到之前的問題，所有的搞不清楚的本質都來源於我們無法判斷當前遇到的節點究竟是初次見面，還是回溯之後的久別重逢。而這關係到我們要對它做什麼。原本在遞歸當中，由於程序會記錄遞歸時的狀態和代碼運行的位置，遞歸回溯之後會回到上次調用的位置，所以我們可以忽略這個問題。而現在我們由於不再使用遞歸，所以需要我們自己來判斷節點的狀態。
想通了其實很簡單，我們只需要在節點當中加一個狀態的字段，表示這個節點是否會發生回溯。顯然在一開始的時候，所有的節點狀態都是True。
我們在Node類中加一個flag作為記錄，初始化時我們默認它為True。接著就很簡單了，我們就按照左中右的順序遍歷節點，只要左子樹存在且還沒有回溯過就往左邊遍歷，在一路往左的過程中遇到的這些節點的flag全部置為False，因為它們的回溯已經開始，以後不會再發生回溯了。由於往右遍歷不會存在回溯的問題，所以可以忽略，想明白了，代碼也就順理成章。
這段代碼雖然短，但其實不簡單，想要完全看懂需要對遞歸和循環有深入的理解。屬於典型的看著簡單實際不容易的題，我個人比較喜歡這類問題，除了鍛鍊思維之外也很適合用來面試，候選人的思維能力、代碼駕馭能力基本上都一清二楚了。沒有看懂的同學也不用擔心，因為在實際場景當中並不會遇到這樣的場景，以後還會推出其他關於遞歸和搜索算法的文章，只要你堅持閱讀，我相信一定會看懂的。
今天的文章就是這些，如果覺得有所收穫，請順手點個關注或轉發吧，你們的舉手之勞對我來說很重要。
閱讀更多 承志的算法課堂 的文章
