棧及其應用
時間：2018-08-16 來源：未知
棧是限制在一端進行插入操作和刪除操作的線性表（俗稱堆棧），允許進行操作的一端稱為“棧頂”，另一固定端稱為“棧底”，當棧中沒有元素時稱為“空棧”。向一個棧內(nèi)插入元素稱為是進棧，push；從一個棧刪除元素稱為是出棧，pop。特點 ：后進先出（LIFO）。
棧的存儲
棧的存儲方式分為順序存儲和鏈式存儲。
棧的順序存儲結構需要使用連續(xù)的存儲空間，并且需要一個元素來確定它的棧頂。利用數(shù)組來順序存儲棧中的所有元素，利用整型變量存儲棧頂元素的下標位置，可以把這個變量稱為棧頂指針。
可以使用下面的結構體來描述棧：
typedef int data_t;
#define SIZE 100;
struct Stack
{
data_t data[SIZE];
int top;
};
也可以使用動態(tài)分配內(nèi)存的辦法描述棧：
struct Stack
{
data_t * pData;
int top;
int maxSize;
};
top=-1表示棧空。
棧的鏈式存儲結構
棧的鏈式存儲結構是通過由結點構成的單鏈表實現(xiàn)的。此時，表頭指針被稱為是棧頂指針，由棧頂指針指向的表頭結點被稱為是棧頂結點，整個單鏈表被稱為是鏈棧。對于鏈棧的入棧和出棧都是在表頭進行。
可以使用下面的數(shù)據(jù)結構來描述棧：
typedef int data_t;
struct stackNode
{
data_t data;
struct stackNode * pNext;
};
如果想要一個確定大結點數(shù)的鏈棧，可以將單鏈表的頭結點的數(shù)據(jù)域強轉(zhuǎn)為保存結點個數(shù)的值。頭結點指針域的值為NULL時，表示空棧。
棧的應用
簡單應用
1.輸入之后逆序輸出
2.語法檢查：括號匹配
每當掃描到大中小的括號后，令其進棧，當掃描到右括號時，則檢查棧頂是否為相應的左括號，若是，則出棧處理，若不是，則出現(xiàn)了語法錯誤。當掃描到文件結尾，若棧為空則表明沒有發(fā)現(xiàn)括號配對錯誤。
3.數(shù)制轉(zhuǎn)換
十進制轉(zhuǎn)八進制。例如(1348)十進制= (2504)八進制,它基于如下的原理:
N N/8 N%8
1348 168 4
168 21 0
21 2 5
2 0 2
所以很明顯，N不斷的除8，每次的余數(shù)就是結果的其中一個因子，注意先出來的因子是低位的數(shù)，可以考慮用棧來保存每次取余的結果，那么出棧的順序就是實際的結果順序。
代碼如下：
int decimalToOctonary(int decimalNumber)
{
double octNumber = 0;
int nCount = 0;
int nTemp = 0;
struct stack * pNumberStack;
//定義棧，pNumberStack并且初始化該棧 代碼略
pNumberStack = createStack();
while (decimalNumber)
{
nTemp = (int)decimalNumber%8;
//將nTemp入棧pNumberStack 代碼略
push(pNumberStack, nTemp);
decimalNumber = decimalNumber/8;
}
nCount = CountOfStack(numberStack);//元素個數(shù)也就是位數(shù)
while(!IsEmptyStack(numberStack))
{
//將棧numberStack中的元素出棧，并且賦值給nTemp 代碼略
pop(pNumberStack, &nTemp);
octNumber += (nTemp*pow(10.0, --nCount));
}
//銷毀棧numberStack
DestroyStack(&numberStack);
//返回轉(zhuǎn)換后的八進制數(shù)
return (int)octNumber;
}
中綴和后綴表達式的轉(zhuǎn)換及計算
1.兩種表達式
中綴表達式：人使用的類似于(2+3*5)，運算符號在數(shù)字中間的表達式。計算需要注意優(yōu)先級、括號這些問題，和運算符的實際運算次序往往同它們在表達式中的先后次序不一致，所以波蘭科學家提出了后綴表達式，把運算符放在兩個運算對象的后面。
在后綴表達式中看，不存在括號，也不存在運算符優(yōu)先級的差別，計算過程完全按照運算符出現(xiàn)的先后次序進行，整個計算過程僅需掃描一遍便可完成。
2.中綴表達式轉(zhuǎn)換成后綴表達式的轉(zhuǎn)化規(guī)則和思路
利用棧，可以實現(xiàn)中綴表達式轉(zhuǎn)化為后綴表達式。也可以實現(xiàn)后綴表達式的計算。這里主要實現(xiàn)難度較大的中綴表達式向后綴表達式的轉(zhuǎn)化。中綴算術表達式轉(zhuǎn)換成對應的后綴算術表達式的規(guī)則是：把每個運算符都移到它的兩個運算對象的后面，然后刪除掉所有的括號即可。
為了轉(zhuǎn)換正確，必須設定一個運算符棧，并在棧底存放一個特殊運算符，假定為’@’，讓它具有低的運算符優(yōu)先級，此棧用來保存掃描中綴表達式得到的暫不能放入后綴表達式中的運算符，等待它的兩個運算對象都放入到后綴表達式后，再令其出棧并寫入后綴表達式中。轉(zhuǎn)換的過程如下：
轉(zhuǎn)換過程如下：從頭到尾掃描中綴表達式，若遇到數(shù)字則直接寫入后綴表達式，若遇到運算符，則比較棧頂元素和該運算符的優(yōu)先級，當該運算符的優(yōu)先級大于棧頂元素的時候，表明該運算符的后一個運算對象還沒有進入后綴表達式，應該把該運算符暫存于運算符棧中，然后把它的后一個運算對象寫入到后綴表達式中，再令其出棧并寫入后綴表達式中；若遇到的運算符優(yōu)先級小于等于棧頂元素的優(yōu)先級，表明棧頂運算符的兩個運算對象已經(jīng)被寫入后綴表達式，應將棧頂元素出棧并寫入后綴表達式，對于新的棧頂元素仍進行比較和處理，直到棧頂元素的優(yōu)先級小于當前等待處理的運算符的優(yōu)先級為止，然后令該運算符進棧即可。
按照上述過程掃描到中綴表達式的末尾，把剩余的運算符依次出棧并寫入后綴表達式即可。
（對于左括號直接進棧，右括號則使左右兩個括號內(nèi)的運算符都出棧）。
后綴表達式求值
后綴表達式求值也需要一個棧，其元素類型為操作數(shù)的類型，此棧存儲后綴表達式中的操作數(shù)、計算過程的中間結果及后結果。
計算過程如下：掃描后綴表達式，若遇到操作數(shù)則進棧，若遇到操作符則彈出兩個操作數(shù)進行計算，然后將結果壓進棧，直到后掃描完畢，棧中應該保存著終結果。
以上是關于棧及棧的常見的應用的一個總結。
