棧及其(qi)應用
時(shi)間：2018-08-16 來源：未知
棧(zhan)(zhan)是限(xian)制在一(yi)(yi)端(duan)進(jin)行插(cha)入操作(zuo)和刪除操作(zuo)的(de)線(xian)性(xing)表（俗稱(cheng)堆棧(zhan)(zhan)），允許進(jin)行操作(zuo)的(de)一(yi)(yi)端(duan)稱(cheng)為(wei)“棧(zhan)(zhan)頂”，另一(yi)(yi)固(gu)定端(duan)稱(cheng)為(wei)“棧(zhan)(zhan)底(di)”，當棧(zhan)(zhan)中沒有元(yuan)素時稱(cheng)為(wei)“空棧(zhan)(zhan)”。向一(yi)(yi)個(ge)棧(zhan)(zhan)內(nei)插(cha)入元(yuan)素稱(cheng)為(wei)是進(jin)棧(zhan)(zhan)，push；從一(yi)(yi)個(ge)棧(zhan)(zhan)刪除元(yuan)素稱(cheng)為(wei)是出棧(zhan)(zhan)，pop。特點 ：后進(jin)先出（LIFO）。
棧的存儲
棧的存儲(chu)方式(shi)分為順序存儲(chu)和鏈式(shi)存儲(chu)。
棧(zhan)(zhan)的順序(xu)存儲結構需要使用連續的存儲空間，并且需要一(yi)個元素來(lai)確定(ding)它的棧(zhan)(zhan)頂(ding)(ding)。利用數組來(lai)順序(xu)存儲棧(zhan)(zhan)中的所有元素，利用整型變量(liang)存儲棧(zhan)(zhan)頂(ding)(ding)元素的下標位置，可以把這個變量(liang)稱為棧(zhan)(zhan)頂(ding)(ding)指針。
可以(yi)使用(yong)下面的結(jie)構體來(lai)描述棧：
typedef int data_t;
#define SIZE 100;
struct Stack
{
data_t data[SIZE];
int top;
};
也可以(yi)使用(yong)動態分配(pei)內存的辦法描述(shu)棧：
struct Stack
{
data_t * pData;
int top;
int maxSize;
};
top=-1表示棧空(kong)。
棧的鏈(lian)式存(cun)儲結構
棧的(de)鏈(lian)式存儲(chu)結構(gou)(gou)是(shi)通過由(you)結點(dian)構(gou)(gou)成的(de)單鏈(lian)表(biao)(biao)實現(xian)的(de)。此時，表(biao)(biao)頭(tou)指針被稱(cheng)為(wei)是(shi)棧頂(ding)指針，由(you)棧頂(ding)指針指向的(de)表(biao)(biao)頭(tou)結點(dian)被稱(cheng)為(wei)是(shi)棧頂(ding)結點(dian)，整(zheng)個單鏈(lian)表(biao)(biao)被稱(cheng)為(wei)是(shi)鏈(lian)棧。對于鏈(lian)棧的(de)入棧和出棧都是(shi)在表(biao)(biao)頭(tou)進行。
可以(yi)使用下面的數據結構來描述棧：
typedef int data_t;
struct stackNode
{
data_t data;
struct stackNode * pNext;
};
如果想要一個確(que)定大結(jie)(jie)點(dian)數(shu)的(de)(de)(de)鏈棧(zhan)，可以(yi)將單鏈表(biao)的(de)(de)(de)頭結(jie)(jie)點(dian)的(de)(de)(de)數(shu)據域強(qiang)轉為保存(cun)結(jie)(jie)點(dian)個數(shu)的(de)(de)(de)值。頭結(jie)(jie)點(dian)指針域的(de)(de)(de)值為NULL時，表(biao)示空棧(zhan)。
棧的應用
簡單應用
1.輸入之(zhi)后逆序輸出
2.語法檢查：括號匹配(pei)
每當掃描到大中小的(de)括(kuo)號后(hou)，令其進棧，當掃描到右括(kuo)號時，則(ze)檢查棧頂是否(fou)為(wei)相(xiang)應的(de)左括(kuo)號，若是，則(ze)出棧處(chu)理，若不是，則(ze)出現了語法錯誤。當掃描到文件結尾，若棧為(wei)空則(ze)表明(ming)沒(mei)有發現括(kuo)號配對(dui)錯誤。
3.數制轉換
十進制(zhi)(zhi)轉八(ba)進制(zhi)(zhi)。例如(1348)十進制(zhi)(zhi)= (2504)八(ba)進制(zhi)(zhi),它基于(yu)如下的原理:
N N/8 N%8
1348 168 4
168 21 0
21 2 5
2 0 2
所以很明(ming)顯，N不(bu)斷的除(chu)8，每次的余數(shu)就是(shi)結(jie)果的其中(zhong)一個因子(zi)，注(zhu)意先出來(lai)的因子(zi)是(shi)低(di)位的數(shu)，可以考慮用棧來(lai)保存每次取余的結(jie)果，那么出棧的順(shun)序就是(shi)實(shi)際的結(jie)果順(shun)序。
代碼如下：
int decimalToOctonary(int decimalNumber)
{
double octNumber = 0;
int nCount = 0;
int nTemp = 0;
struct stack * pNumberStack;
//定(ding)義(yi)棧，pNumberStack并(bing)且初(chu)始化該棧 代碼略
pNumberStack = createStack();
while (decimalNumber)
{
nTemp = (int)decimalNumber%8;
//將nTemp入棧pNumberStack 代碼略
push(pNumberStack, nTemp);
decimalNumber = decimalNumber/8;
}
nCount = CountOfStack(numberStack);//元素個數(shu)也就是(shi)位數(shu)
while(!IsEmptyStack(numberStack)) ;
{
//將棧numberStack中的元素出棧，并(bing)且賦(fu)值給nTemp 代碼略
pop(pNumberStack, &nTemp);
; octNumber += (nTemp*pow(10.0, --nCount));
}
//銷毀棧(zhan)numberStack
DestroyStack(&numberStack);
//返回轉換后的(de)八進(jin)制數
return (int)octNumber;
}
中綴和后綴表達式的(de)轉換(huan)及計算(suan)
1.兩種表達式
中(zhong)綴(zhui)表達(da)式：人使用的(de)類(lei)似于(2+3*5)，運(yun)(yun)算(suan)(suan)符號在(zai)數字(zi)中(zhong)間的(de)表達(da)式。計(ji)算(suan)(suan)需要注意優(you)先級、括號這些問題(ti)，和(he)運(yun)(yun)算(suan)(suan)符的(de)實(shi)際運(yun)(yun)算(suan)(suan)次(ci)序往往同它們在(zai)表達(da)式中(zhong)的(de)先后(hou)次(ci)序不一致，所以波蘭科學家提出了后(hou)綴(zhui)表達(da)式，把(ba)運(yun)(yun)算(suan)(suan)符放(fang)在(zai)兩個運(yun)(yun)算(suan)(suan)對象的(de)后(hou)面。
在(zai)后(hou)綴表達式中看，不存(cun)(cun)在(zai)括號，也不存(cun)(cun)在(zai)運(yun)算(suan)符優先級(ji)的(de)差別(bie)，計算(suan)過(guo)程完全(quan)按照運(yun)算(suan)符出現的(de)先后(hou)次序進行，整個計算(suan)過(guo)程僅需掃描一遍便可完成。
2.中綴(zhui)表達式(shi)轉換(huan)成后綴(zhui)表達式(shi)的轉化規則和(he)思路
利用棧，可(ke)以(yi)實現中綴表(biao)達式(shi)轉化(hua)(hua)為(wei)后(hou)綴表(biao)達式(shi)。也(ye)可(ke)以(yi)實現后(hou)綴表(biao)達式(shi)的(de)(de)(de)計算。這里主要(yao)實現難度較大(da)的(de)(de)(de)中綴表(biao)達式(shi)向后(hou)綴表(biao)達式(shi)的(de)(de)(de)轉化(hua)(hua)。中綴算術(shu)表(biao)達式(shi)轉換成對應的(de)(de)(de)后(hou)綴算術(shu)表(biao)達式(shi)的(de)(de)(de)規則是：把每個運算符都移到它的(de)(de)(de)兩個運算對象(xiang)的(de)(de)(de)后(hou)面，然(ran)后(hou)刪(shan)除掉(diao)所有的(de)(de)(de)括號即可(ke)。
為了轉換正確，必須設定一(yi)個(ge)運(yun)算(suan)符棧，并在棧底存(cun)放(fang)一(yi)個(ge)特殊運(yun)算(suan)符，假定為’@’，讓它(ta)具(ju)有低的(de)運(yun)算(suan)符優先(xian)級，此(ci)棧用(yong)來保存(cun)掃描中綴(zhui)表(biao)(biao)達式得(de)到的(de)暫不(bu)能(neng)放(fang)入后(hou)(hou)綴(zhui)表(biao)(biao)達式中的(de)運(yun)算(suan)符，等待(dai)它(ta)的(de)兩個(ge)運(yun)算(suan)對象都放(fang)入到后(hou)(hou)綴(zhui)表(biao)(biao)達式后(hou)(hou)，再令其出棧并寫入后(hou)(hou)綴(zhui)表(biao)(biao)達式中。轉換的(de)過程如(ru)下：
轉換過程如下：從頭到尾(wei)掃描中(zhong)綴表(biao)(biao)達(da)式(shi)(shi)(shi)，若遇(yu)到數字則直接寫(xie)(xie)入(ru)(ru)后(hou)(hou)綴表(biao)(biao)達(da)式(shi)(shi)(shi)，若遇(yu)到運(yun)(yun)算(suan)(suan)符(fu)(fu)(fu)，則比(bi)較(jiao)棧(zhan)(zhan)頂(ding)(ding)(ding)元素(su)和該(gai)運(yun)(yun)算(suan)(suan)符(fu)(fu)(fu)的(de)(de)(de)優(you)(you)先級(ji)(ji)，當該(gai)運(yun)(yun)算(suan)(suan)符(fu)(fu)(fu)的(de)(de)(de)優(you)(you)先級(ji)(ji)大(da)于(yu)棧(zhan)(zhan)頂(ding)(ding)(ding)元素(su)的(de)(de)(de)時候，表(biao)(biao)明該(gai)運(yun)(yun)算(suan)(suan)符(fu)(fu)(fu)的(de)(de)(de)后(hou)(hou)一個運(yun)(yun)算(suan)(suan)對象(xiang)還沒有進入(ru)(ru)后(hou)(hou)綴表(biao)(biao)達(da)式(shi)(shi)(shi)，應該(gai)把(ba)該(gai)運(yun)(yun)算(suan)(suan)符(fu)(fu)(fu)暫存于(yu)運(yun)(yun)算(suan)(suan)符(fu)(fu)(fu)棧(zhan)(zhan)中(zhong)，然后(hou)(hou)把(ba)它的(de)(de)(de)后(hou)(hou)一個運(yun)(yun)算(suan)(suan)對象(xiang)寫(xie)(xie)入(ru)(ru)到后(hou)(hou)綴表(biao)(biao)達(da)式(shi)(shi)(shi)中(zhong)，再令其出(chu)棧(zhan)(zhan)并寫(xie)(xie)入(ru)(ru)后(hou)(hou)綴表(biao)(biao)達(da)式(shi)(shi)(shi)中(zhong)；若遇(yu)到的(de)(de)(de)運(yun)(yun)算(suan)(suan)符(fu)(fu)(fu)優(you)(you)先級(ji)(ji)小于(yu)等(deng)于(yu)棧(zhan)(zhan)頂(ding)(ding)(ding)元素(su)的(de)(de)(de)優(you)(you)先級(ji)(ji)，表(biao)(biao)明棧(zhan)(zhan)頂(ding)(ding)(ding)運(yun)(yun)算(suan)(suan)符(fu)(fu)(fu)的(de)(de)(de)兩個運(yun)(yun)算(suan)(suan)對象(xiang)已經被寫(xie)(xie)入(ru)(ru)后(hou)(hou)綴表(biao)(biao)達(da)式(shi)(shi)(shi)，應將棧(zhan)(zhan)頂(ding)(ding)(ding)元素(su)出(chu)棧(zhan)(zhan)并寫(xie)(xie)入(ru)(ru)后(hou)(hou)綴表(biao)(biao)達(da)式(shi)(shi)(shi)，對于(yu)新的(de)(de)(de)棧(zhan)(zhan)頂(ding)(ding)(ding)元素(su)仍進行(xing)比(bi)較(jiao)和處理，直到棧(zhan)(zhan)頂(ding)(ding)(ding)元素(su)的(de)(de)(de)優(you)(you)先級(ji)(ji)小于(yu)當前等(deng)待處理的(de)(de)(de)運(yun)(yun)算(suan)(suan)符(fu)(fu)(fu)的(de)(de)(de)優(you)(you)先級(ji)(ji)為(wei)止，然后(hou)(hou)令該(gai)運(yun)(yun)算(suan)(suan)符(fu)(fu)(fu)進棧(zhan)(zhan)即可。
按(an)照上述過程掃描到中(zhong)綴(zhui)表(biao)(biao)達式的末尾，把剩余的運算符(fu)依次出棧(zhan)并寫入(ru)后綴(zhui)表(biao)(biao)達式即可。
（對于左括號(hao)直接進棧(zhan)，右括號(hao)則(ze)使(shi)左右兩個括號(hao)內的運算符都出(chu)棧(zhan)）。
后綴表達(da)式(shi)求值(zhi)
后綴(zhui)表達式(shi)求值也需要一個棧，其元素(su)類型為(wei)操作數(shu)的類型，此棧存儲(chu)后綴(zhui)表達式(shi)中(zhong)(zhong)的操作數(shu)、計算過程的中(zhong)(zhong)間結(jie)果及后結(jie)果。
計(ji)算過程如下：掃描后(hou)綴表達式，若遇到操作數(shu)則進棧，若遇到操作符(fu)則彈出兩(liang)個操作數(shu)進行計(ji)算，然后(hou)將結果(guo)壓進棧，直到后(hou)掃描完畢，棧中應(ying)該保存著終結果(guo)。
以上(shang)是關于棧(zhan)及棧(zhan)的(de)常(chang)見的(de)應用的(de)一個總結。
