国产成人精品三级麻豆,色综合天天综合高清网,亚洲精品夜夜夜,国产成人综合在线女婷五月99播放,色婷婷色综合激情国产日韩

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

棧的存儲(chǔ)

棧的存儲(chǔ)方式分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

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

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

typedef int data_t;

#define SIZE 100;

struct Stack 

{

data_t data[SIZE];

int top;

};

也可以使用動(dòng)態(tài)分配內(nèi)存的辦法描述棧：

struct Stack

{

data_t * pData;

int top;

int maxSize;

};

top=-1表示棧空。

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

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

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

typedef int data_t;

struct stackNode

{

data_t   data;

struct stackNode * pNext;

};

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

棧的應(yīng)用

簡(jiǎn)單應(yīng)用

1.輸入之后逆序輸出

2.語(yǔ)法檢查：括號(hào)匹配

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

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é)果的其中一個(gè)因子，注意先出來(lái)的因子是低位的數(shù)，可以考慮用棧來(lái)保存每次取余的結(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);//元素個(gè)數(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)算符號(hào)在數(shù)字中間的表達(dá)式。計(jì)算需要注意優(yōu)先級(jí)、括號(hào)這些問(wèn)題，和運(yùn)算符的實(shí)際運(yùn)算次序往往同它們?cè)诒磉_(dá)式中的先后次序不一致，所以波蘭科學(xué)家提出了后綴表達(dá)式，把運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象的后面。

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

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)換成對(duì)應(yīng)的后綴算術(shù)表達(dá)式的規(guī)則是：把每個(gè)運(yùn)算符都移到它的兩個(gè)運(yùn)算對(duì)象的后面，然后刪除掉所有的括號(hào)即可。

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

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

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

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

后綴表達(dá)式求值

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

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

以上是關(guān)于棧及棧的常見(jiàn)的應(yīng)用的一個(gè)總結(jié)。