From百度百科（修改）：棧，是一種運算受限的線性表。僅允許在表的一端（棧頂）進行插入和刪除運算，另一端稱為棧底。 運算：Push：向棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素。 Pop：從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
如下圖為模型圖： 
類似于鏈表的指針實現(xiàn)，棧的鏈表形式實現(xiàn)也差不多，思路比較清晰。
// _Stack_H.h#ifndef _Stack_Hstruct Node;typedef struct Node * PtrToNode;typedef PtrToNode Stack;int Isempty(Stack S);Stack CreateStack(void);// void DisposeStack(void);void MakeEmpty(Stack S);int Push(ElementType X,Stack S); /*新元素進棧操作*/ElementType Top(Stack S); /*返回棧頂元素*/int Pop(Stack S); /*棧頂元素出棧*/#endif/*Implementation of Functions*/#include <stdio.h>#include <stdlib.h>#include '_Stack_H.h'struct Node{ ElementType Element; PtrToNode Next; /* data */};/*測試棧是否為空*/int Isempty(Stack S){ return S->Next==NULL;}/*創(chuàng)建一個空棧，即棧初始化*/void MakeEmpty(Stack S){ if(S==NULL) { 3、棧的數(shù)組實現(xiàn)數(shù)組實現(xiàn)時，感覺相對指針的有點不習(xí)慣。聲明結(jié)構(gòu)體時，鏈表的是以包括一個元素和一個指針的節(jié)點實現(xiàn)的；而數(shù)組的是包括三個量：棧的容量（自定），TopOfStack（棧頂狀態(tài)）以及一個數(shù)組指針（儲存棧中的數(shù)據(jù)）。以下為區(qū)別：
//鏈表實現(xiàn)的結(jié)構(gòu)體聲明struct Node{ ElementType Element; PtrToNode Next;};//另一個不同點：設(shè)置空棧條件&棧容量最小值#define EmptyTOS (-1)#define MinStackSize (5)//數(shù)組實現(xiàn)的結(jié)構(gòu)體聲明struct StackRecord{ int capacity; int TopOfStack; ElementType * Array;}其中TOS（TopOfStack)為棧頂在數(shù)組中的位置，且-1時表示空棧（棧下溢），如TOS=N-1（N為容量）,則表示棧滿了；TOS=0，表示棧只有一個元素（棧底元素）。 數(shù)組編號從棧底為0開始編號。 因此，此時處理棧就不像鏈表那樣對節(jié)點進行處理（其實，鏈表中的節(jié)點等同于把Array數(shù)組每個元素分開處理），而是對整個棧（Array） 進行處理。則有如下算法規(guī)則： 
截圖來源于百度百科
即有： Push：先判斷是否棧滿。若不滿，則TOS加1，令Stack[TOS]=X。若棧滿，則報錯。 Pop：先判斷是否棧空。若不空，先彈出棧頂元素Stack（TOS），令Temp=Stack（TOS），再有TOS減1。若空，則報錯。
1.平衡符號 如下為原書原話： 
舉個例子，對“ [ ( ] ) “進行判斷。讀入”[“和”（“時，為開放符號，入棧。讀入”]“(右方括號)，為封閉符號，此時棧不空，將棧頂”（“（左圓括號）彈出，發(fā)現(xiàn)不匹配，報錯。 還有就是，如果讀取到文件尾，棧非空也報錯。
2.后綴表達式 后綴記法，也被稱為逆波蘭記法。一般標(biāo)準(zhǔn)表達式，如
（1）后綴表達式的計算 以
（2）中綴到后綴的轉(zhuǎn)換 對于中綴到后綴的轉(zhuǎn)換，比較復(fù)雜。書中只討論有+*（） 四種運算符的情況（加號，乘號，左圓括號，右圓括號）。有如下轉(zhuǎn)換原則： 首先，假設(shè)中綴表達式是合法的，即正確的。 運算符優(yōu)先級有從低到高是：+*（）
初始化一個空棧，讀取時從左到右讀取字符（因為涉及的都是從左到右運算的運算符，若像取冪運算符，則不行）當(dāng)遇到數(shù)字時，不壓入棧，直接輸出當(dāng)棧為空時，讀到的第一個運算符直接壓棧。（因為假設(shè)原表達式合法，即不存在右圓括號在前，左的在后的情況）當(dāng)棧非空（即有運算符在里面），讀到運算符A時，從棧中彈出棧元素直到發(fā)現(xiàn)優(yōu)先級比A更低為止。左右圓括號為例外。即（要直到遇到）才出棧 其實，還是例子生動，詳細例子見網(wǎng)站：http://www.nowamagic.net/librarys/veda/detail/2307
這個例子較好。
新聞熱點
疑難解答
