什么是棧？
時間：2018-09-26 來源：未知
當提及“棧”這個概念，很多初學者都會很迷茫。在C語言里，我們有一個內存區域叫做棧區。在單片機里，我們又常常聽到一個操作叫做壓棧。而在算法中，我們也有一個同名結構叫做棧。
我常常會問自己的學生“棧”這個字的意思到底是什么?大家想到的多是客棧。我們翻翻字典也不難發現，棧的第一個釋義是：儲存貨物或供旅客住宿的房屋。所以客棧的想法并沒有錯，但是這也未免太過抽象。
我們先來解釋一下在計算機領域什么是棧。
棧某種意義上講，它像是一個開口的盒子，先放進去的東西總是會被后放進去的東西壓在下面，那么如果想拿出被壓住的東西，必須要先取出頂部的東西，也就是后放進去的東西。換個說法就是先入后出。那它有點像什么呢?想象一下裝在盤子里的若干張油餅。
對，他們是摞在一起的。如果想拿下面的油餅是不是要先拿開上面的呢?或許，這就是棧的根源。但是，又和“棧”這個字有什么關系呢?單純的從釋義上看，好似找不出什么關聯性。但是當我們打開漢英詞典：
對計算機中提及的“棧”的英文愿意是stack!我們一定要記得，是一群說英語的人創造了計算機，也是他們研究了初的算法。那么stack又是什么意思?
注意箭頭指向的那一摞書們，和餅們的相處方式是不是很像!堆疊到一起。那個根源出來了，其實棧就是一種將數據依次“堆疊”的一種數據組織方式。
或者到這里，我們恍然大悟，哦，原來是這樣!棧還有堆疊的意思。但是，我個人更覺得這是一種初期程序員之間的交流翻譯吳繆。暫且放下這個不談，至少我們明白一件事情，在某些領域，如果一個詞匯很生澀，那么，不妨去查找一下他的英文愿意，或許你會有更深入的收獲。
我們在來探討下一個話題——“棧”stack，這種摞大餅大數據組織方式到底有什么用?
比如說，你有一些書，我們通常會這樣擺放：
而不是這樣：
為什么呢?當然是第二種擺放方式不方便拿其中的某一本書�？墒窃�“棧”(stack)結構里面，“書”就是這樣擺放的。那也就是說，“棧”(stack)不適合存放需要隨機查找的東西。那它能做什么呢?
首先說說CPU里的“堆棧”。我們可以這樣設想：一個CPU等同于一個完全沒有記憶力的人，他只知道按照一份很詳細的說明文檔(也就是程序)來一步一步做某件事情，并且，他永遠不會記得之前做過什么。我們在電影里常常會看到這樣的情節，失憶癥的人常常會隨身攜帶一些本子和照片，然后按順序把發生的事情記錄下來，方便自己查閱。CPU也有這樣的需求。
在CPU里，有一種機制叫做“中斷”interrupt，就是中途插一嘴的意思。怎么插呢?比方說，你正在玩兒一個單機游戲，在更要通關的時候，外面突然有人敲門。那么是不是要把你的游戲暫停一下?然后再去開門。然后正在你去開門的路上，廚房的煤氣報警器響起，是不是要趕緊去廚房看一下是不是誤報警?確認是誤報警后，我們是先去開門呢?還是繼續打游戲呢?對于CPU來說，也會有同樣的困惑。對于人，我們或許可以思考一下——哦，開門這件事器比較緊迫，應該先開門。但是對于CPU來說，又如何區分緊迫度呢?這就變成了一個很麻煩的問題。我們回頭再想想“棧”，他是如何組織數據的?先入后出。玩游戲是先發生的事情，那么打斷他的事情就是更緊迫的事情，開門雖然比游戲緊迫，但是他次于煤氣報警，所以，它才是緊迫的事情。不過到現在也應該注意到了。緊迫的事情往往在后產生，又要被優先處理。
在CPU的中斷機制里，每當cpu執行的一個任務被打斷時，cpu就需要備份當前的處理狀態，就像沒有記憶的人，總是要記筆記拍照。那么cpu怎么區分優先次序呢?就像你吃盤子里的餅!先拿上面的。而存儲數據的過程，就像你向盤子里放餅的過程。
再說說C語言分段里的“棧區”，我們都知道，局部自動變量分配到內存的“棧區”，棧區里的數據組織方式也類似摞餅，每當你調用了一個子函數，那么編譯器會將子函數里的局部變量分配到棧區的棧頂位置(與當前函數的空間相鄰)，當子函數在再調用另一個函數是，也是會做同樣處理。兒關于局部變量的釋放，其實本質就是講棧頂的一塊空間的使用權歸還回去，看起來就好像客棧一樣，來人的時候開房，走人的時候退房�；蛟S這也是stack會被翻譯成“棧”的原由。
后在來說“棧”，這種單純的邏輯結構。它和前兩者一樣，遵循類似先入后出的數據處理規則。
那這個“盒子“什么時候會用到呢?典型的例子，就是迷宮算法(具體細節可以自己搜索一下)，我們可以用棧來存放已經走過的有效路線。也或者利用棧來模擬局部變量分配，實現將遞歸算法轉換為非遞歸。也或者利用棧來優化，自己的程序處理邏輯，在實際問題解決中，如果你涉及到了臨時保存數據，那么你可以嘗試考慮一下使用棧，或許可以讓自己的程序在邏輯上變得更加清晰明了。
簡單的總結一下：所謂“棧”，其實就是一本 相互堆疊的便簽兒。我們可以逐次備份自己要保存的信息，然后在反向依次處理。
