轉(zhuǎn)自：http://www.cnblogs.com/mengdd/archive/2012/11/07/2759483.html

棧 Stack

　　棧又稱堆棧，是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。

　　把對棧進(jìn)行運(yùn)算的一端稱為棧頂，另一端稱為棧底。

　　向一個棧插入新元素稱為入棧或進(jìn)棧，Push；從一個棧刪除元素稱為退棧或出棧，Pop。

　　因為后進(jìn)棧的元素必定先出棧，所以又把棧稱為后進(jìn)先出表（Last In First Out, LIFO）。

棧的順序存儲結(jié)構(gòu)

　　棧的順序存儲結(jié)構(gòu)需要使用一個數(shù)組和一個整型變量來實現(xiàn)。利用數(shù)組來順序存儲棧中的所有元素，利用整型變量來存儲棧頂元素的下標(biāo)位置，可這個變量稱為棧頂指針。

　　可以定義如下：

const int MaxSize = 50; struct Stack {ElemType stack[MaxSize];int top; };

?

若要對存儲棧的數(shù)組空間采用動態(tài)分配，則可定義如下：

struct Stack {ElemType *stack;int top;int MaxSize; };

top的值為-1表示棧空。

?

棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)

　　棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過由結(jié)點構(gòu)成的單鏈表實現(xiàn)的，此時表頭指針被稱為棧頂指針，由棧頂指針指向的表頭結(jié)點被稱為棧頂結(jié)點，整個單鏈表被稱為鏈棧。

　　對鏈棧的插入和刪除操作是在單鏈表的表頭進(jìn)行的。

　　當(dāng)向一個鏈棧插入元素時，是把該元素插入到棧頂，即，使該元素結(jié)點的指針域指向原來的棧頂結(jié)點，而棧頂指針則修改為指向該元素結(jié)點，使該結(jié)點成為新的棧頂結(jié)點。

棧的應(yīng)用

簡單應(yīng)用

　　1.輸入，之后逆序輸出。

　　2.語法檢查：括號匹配。

　　每當(dāng)掃描到大中小的左括號后，令其進(jìn)棧，當(dāng)掃描到右括號時，則檢查棧頂是否為相應(yīng)的左括號，若是則退棧處理，若不是則出現(xiàn)了語法錯誤。當(dāng)掃描到文件結(jié)尾，若棧為空則表明沒有發(fā)現(xiàn)括號配對錯誤。

　　3.數(shù)制轉(zhuǎn)換：把十進(jìn)制的整數(shù)轉(zhuǎn)換為二至九之間的任一進(jìn)制數(shù)輸出。

　　轉(zhuǎn)換方法：要轉(zhuǎn)換為r進(jìn)制，則原來的數(shù)逐次除以基數(shù)r（除完之后用商再除），直到商為0，得到的一系列余數(shù)的逆序就是轉(zhuǎn)換結(jié)果。

算術(shù)表達(dá)式的計算

　　在中綴表達(dá)式（就是我們?nèi)祟愅ǔ懙乃阈g(shù)表達(dá)式）中，計算需要注意優(yōu)先級、括號這些問題，和運(yùn)算符的實際運(yùn)算次序往往同它們在表達(dá)式中的先后次序不一致，所以波蘭科學(xué)家提出了后綴表達(dá)式，把運(yùn)算符放在兩個運(yùn)算對象的后面。

　　在后綴表達(dá)式中看，不存在括號，也不存在運(yùn)算符優(yōu)先級的差別，計算過程完全按照運(yùn)算符出現(xiàn)的先后次序進(jìn)行，整個計算過程僅需掃描一遍便可完成。

?

中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式：

　　中綴算術(shù)表達(dá)式轉(zhuǎn)換成對應(yīng)的后綴算術(shù)表達(dá)式的規(guī)則是：把每個運(yùn)算符都移到它的兩個運(yùn)算對象的后面，然后刪除掉所有的括號即可。

　　為了轉(zhuǎn)換正確，必須設(shè)定一個運(yùn)算符棧，并在棧底放入一個特殊算符，假定為@，讓它具有最低的運(yùn)算符優(yōu)先級，此棧用來保存掃描中綴表達(dá)式得到的暫不能放入后綴表達(dá)式中的運(yùn)算符，待它的兩個運(yùn)算對象都放入到后綴表達(dá)式之后，再令其出棧并寫入到后綴表達(dá)式中。

　　轉(zhuǎn)換過程如下：從頭到尾掃描中綴表達(dá)式，若遇到數(shù)字則直接寫入后綴表達(dá)式，若遇到運(yùn)算符，則比較棧頂元素和該運(yùn)算符的優(yōu)先級，當(dāng)該運(yùn)算符的優(yōu)先級大于棧頂元素的時候，表明該運(yùn)算符的后一個運(yùn)算對象還沒有進(jìn)入后綴表達(dá)式，應(yīng)該把該運(yùn)算符暫存于運(yùn)算符棧中，然后把它的后一個運(yùn)算對象寫入到后綴表達(dá)式中，再令其出棧并寫入后綴表達(dá)式中；若遇到的運(yùn)算符優(yōu)先級小于等于棧頂元素的優(yōu)先級，表明棧頂運(yùn)算符的兩個運(yùn)算對象已經(jīng)被寫入后綴表達(dá)式，應(yīng)將棧頂元素出棧并寫入后綴表達(dá)式，對于新的棧頂元素仍進(jìn)行比較和處理，直到棧頂元素的優(yōu)先級小于當(dāng)前等待處理的運(yùn)算符的優(yōu)先級為止，然后令該運(yùn)算符進(jìn)棧即可。

　　按照上述過程掃描到中綴表達(dá)式的末尾，把剩余的運(yùn)算符依次出棧并寫入后綴表達(dá)式即可。

　　（對于左括號直接進(jìn)棧，右括號則使左右兩個括號內(nèi)的運(yùn)算符都出棧）。

后綴表達(dá)式求值

　　后綴表達(dá)式求值也需要一個棧，其元素類型為操作數(shù)的類型，此棧存儲后綴表達(dá)式中的操作數(shù)、計算過程的中間結(jié)果及最后結(jié)果。

　　計算過程如下：掃描后綴表達(dá)式，若遇到操作數(shù)則進(jìn)棧，若遇到操作符則彈出兩個操作數(shù)進(jìn)行計算，然后將結(jié)果壓進(jìn)棧，直到最后掃描完畢，棧中應(yīng)該保存著最終結(jié)果。

棧與遞歸

　　在計算機(jī)系統(tǒng)內(nèi)，執(zhí)行遞歸函數(shù)是通過自動使用棧來實現(xiàn)的，棧中的每個元素包含有遞歸函數(shù)的參數(shù)域、每個局部變量域和調(diào)用后的返回地址域，其中引用參數(shù)域只保存?zhèn)魉蛠淼膶崊⒌牡刂贰?/span>每次進(jìn)行函數(shù)調(diào)用，都把相應(yīng)的值壓入棧，每次調(diào)用結(jié)束，都按照本次返回地址返回到指定位置執(zhí)行，并且自動做一次退棧操作。

　　關(guān)于遞歸的應(yīng)用就又是一個大話題了，此處就不多說了。

轉(zhuǎn)載于:https://www.cnblogs.com/Ivyli4258/p/7838040.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的栈及其应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。