棧和隊列 - 棧 - 順序棧

　　順序棧

　　棧的順序存儲結構簡稱為順序棧它是運算受限的順序表

　　 順序棧的類型定義

　　#define StackSize //假定預分配的棧空間最多為個元素

　　typedef char DataType;//假定棧元素的數據類型為字符

　　typedef struct{

　　DataType data[StackSize];

　　int top;

　　}SeqStack;

　　注意

　　①順序棧中元素用向量存放

　　②棧底位置是固定不變的可設置在向量兩端的任意一個端點

　　③棧頂位置是隨著進棧和退棧操作而變化的用一個整型量top(通常稱top為棧頂指針)來指示當前棧頂位置

　　 順序棧的基本操作

　　前提條件

　　設S是SeqStack類型的指針變量若棧底位置在向量的低端即S>data[]是棧底元素

　　() 進棧操作

　　進棧時需要將S>top加

　　注意

　　①S>top==StackSize表示棧滿

　　② 上溢 現象當棧滿時再做進棧運算產生空間溢出的現象

　　上溢是一種出錯狀態應設法避免

　　() 退棧操作

　　退棧時需將S>top減

　　注意

　　①S>top<表示空棧

　　② 下溢 現象——當棧空時做退棧運算產生的溢出現象

　　下溢是正常現象常用作程序控制轉移的條件

　　順序棧在進棧和退棧操作時的具體變化情況

　　順序棧的基本運算

　　() 置棧空

　　void InitStack(SeqStack *S)

　　{//將順序棧置空

　　S>top=;

　　}

　　() 判棧空

　　int StackEmpty(SeqStack *S)

　　{

　　return S>top==;

　　}

　　() 判棧滿

　　int StackFull(SeqStack *SS)

　　{

　　return S>top==StackSize;

　　}

　　() 進棧

　　void Push(Sx)

　　{

　　if (StackFull(S))

　　Error(Stack overflow); //上溢退出運行

　　S>data[++S>top]=x;//棧頂指針加後將x入棧

　　}

　　() 退棧

　　DataType Pop(S)

　　{

　　if(StackEmpty(S))

　　Error(Stack underflow); //下溢退出運行

　　return S>data[S>top];//棧頂元素返回後將棧頂指針減

　　}

　　() 取棧頂元素

　　DataType StackTop(S)

　　{

　　if(StackEmpty(S))

　　Error(Stack is empty);

　　return S>data[S>top];

　　}

　　兩個棧共享同一存儲空間

　　當程序中同時使用兩個棧時可以將兩個棧的棧底設在向量空間的兩端讓兩個棧各自向中間延伸當一個棧裡的元素較多超

　　過向量空間的一半時只要另一個棧的元素不多那麼前者就可以占用後者的部分存儲空間

　　只有當整個向量空間被兩個棧占滿(即兩個棧頂相遇)時才會發生上溢因此兩個棧共享一個長度為m的向量空間和兩個棧分別

　　占用兩個長度為 └ m/┘ 和┌m/┐的向量空間比較前者發生上溢的概率比後者要小得多

　　

From:http://tw.wingwit.com/Article/program/sjjg/201311/23931.html