棧是限制在一端進(jìn)行插入操作和刪除操作的線性表（俗稱堆棧），允許進(jìn)行操作的一端稱為“棧頂”，另一固定端稱為“棧底”，當(dāng)棧中沒有元素時稱為“空?！薄Ｏ蛞粋€棧內(nèi)插入元素稱為是進(jìn)棧，push；從一個棧刪除元素稱為是出棧，pop。特點(diǎn) ：后進(jìn)先出（LIFO）。

a

棧的存儲

 

棧的存儲方式分為順序存儲和鏈?zhǔn)酱鎯Α?/span>

 

棧的順序存儲結(jié)構(gòu)需要使用連續(xù)的存儲空間，并且需要一個元素來確定它的棧頂。利用數(shù)組來順序存儲棧中的所有元素，利用整型變量存儲棧頂元素的下標(biāo)位置，可以把這個變量稱為棧頂指針。

 

可以使用下面的結(jié)構(gòu)體來描述棧：

 

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表示棧空。

 

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

 

棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過由結(jié)點(diǎn)構(gòu)成的單鏈表實(shí)現(xiàn)的。此時，表頭指針被稱為是棧頂指針，由棧頂指針指向的表頭結(jié)點(diǎn)被稱為是棧頂結(jié)點(diǎn)，整個單鏈表被稱為是鏈棧。對于鏈棧的入棧和出棧都是在表頭進(jìn)行。

 

可以使用下面的數(shù)據(jù)結(jié)構(gòu)來描述棧：

 

typedef int data_t;

 

struct stackNode

 

{

 

data_t   data;

 

struct stackNode * pNext;

 

};

 

如果想要一個確定大結(jié)點(diǎn)數(shù)的鏈棧，可以將單鏈表的頭結(jié)點(diǎn)的數(shù)據(jù)域強(qiáng)轉(zhuǎn)為保存結(jié)點(diǎn)個數(shù)的值。頭結(jié)點(diǎn)指針域的值為NULL時，表示空棧。

 

棧的應(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)制轉(zhuǎn)八進(jìn)制。例如(1348)十進(jìn)制= (2504)八進(jìn)制,它基于如下的原理:

 

   N             N/8                N%8

 

 1348            168                   4

 

  168             21                   0

 

   21              2                   5

 

    2              0                   2

 

 

 

所以很明顯，N不斷的除8，每次的余數(shù)就是結(jié)果的其中一個因子，注意先出來的因子是低位的數(shù)，可以考慮用棧來保存每次取余的結(jié)果，那么出棧的順序就是實(shí)際的結(jié)果順序。

 

代碼如下：

 

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)換后的八進(jìn)制數(shù)

 

return (int)octNumber;  

 

}

 

中綴和后綴表達(dá)式的轉(zhuǎn)換及計(jì)算

 

1.兩種表達(dá)式

 

中綴表達(dá)式：人使用的類似于(2+3*5)，運(yùn)算符號在數(shù)字中間的表達(dá)式。計(jì)算需要注意優(yōu)先級、括號這些問題，和運(yùn)算符的實(shí)際運(yùn)算次序往往同它們在表達(dá)式中的先后次序不一致，所以波蘭科學(xué)家提出了后綴表達(dá)式，把運(yùn)算符放在兩個運(yùn)算對象的后面。

 

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

 

2.中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的轉(zhuǎn)化規(guī)則和思路

 

利用棧，可以實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式。也可以實(shí)現(xiàn)后綴表達(dá)式的計(jì)算。這里主要實(shí)現(xiàn)難度較大的中綴表達(dá)式向后綴表達(dá)式的轉(zhuǎn)化。中綴算術(shù)表達(dá)式轉(zhuǎn)換成對應(yīng)的后綴算術(shù)表達(dá)式的規(guī)則是：把每個運(yùn)算符都移到它的兩個運(yùn)算對象的后面，然后刪除掉所有的括號即可。

 

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

 

轉(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ù)、計(jì)算過程的中間結(jié)果及后結(jié)果。

 

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

信盈達(dá)2008年在深圳特區(qū)南山高新科技園成立。自成立至今近九年來專注為企業(yè)和個人提供高端方案設(shè)計(jì)、高端嵌入式/Android培訓(xùn)等服務(wù)。公司下設(shè)信盈達(dá)實(shí)訓(xùn)學(xué)院、信盈達(dá)研發(fā)中心、信盈達(dá)教學(xué)儀器三大業(yè)務(wù)板塊。九年來公司堅(jiān)持"技術(shù)領(lǐng)先、服務(wù)領(lǐng)先"，以雄厚的實(shí)力和專業(yè)的品質(zhì)成為國內(nèi)唯一有實(shí)力從產(chǎn)品最底層研發(fā)到系統(tǒng)層開發(fā)的嵌入式實(shí)訓(xùn)、產(chǎn)品解決方案提供商。為中國IT行業(yè)提供最具價值的職業(yè)教育服務(wù)。專業(yè)培訓(xùn)嵌入式、物聯(lián)網(wǎng)、人工智能、Java、單片機(jī)等課程，想了解更多信息點(diǎn)擊立馬咨詢