順序棧及其運(yùn)算

1、順序棧    棧的順序存儲(chǔ)結(jié)構(gòu)簡稱為順序棧,它是運(yùn)算受限的順序表。1、 順序棧的類型定義  #define StackSize 100 /假定預(yù)分配的?？臻g最多為100個(gè)元素  typedef char DataType;/假定棧元素的數(shù)據(jù)類型為字符  typedef struct      DataType dataStackSize;      int top;     SeqStack; &

2、#160; 注意：    順序棧中元素用向量存放    棧底位置是固定不變的，可設(shè)置在向量兩端的任意一個(gè)端點(diǎn)    棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型量top（通常稱top為棧頂指針）來指示當(dāng)前棧頂位置2、 順序棧的基本操作   前提條件：    設(shè)S是SeqStack類型的指針變量。若棧底位置在向量的低端，即S-data0是棧底元素。（1） 進(jìn)棧操作    進(jìn)棧時(shí)，需要將S-top加1  注意： &#

3、160;  S-top=StackSize-1表示棧滿"上溢"現(xiàn)象-當(dāng)棧滿時(shí)，再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。      上溢是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。（2） 退棧操作    退棧時(shí)，需將S-top減1  注意：    S-top<0表示空棧    "下溢"現(xiàn)象當(dāng)?？諘r(shí)，做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象。      下溢是正?，F(xiàn)象，常用作程序控制轉(zhuǎn)

4、移的條件。順序棧在進(jìn)棧和退棧操作時(shí)的具體變化情況【參見動(dòng)畫演示】3、順序棧的基本運(yùn)算（1） 置棧空  void InitStack（SeqStack *S）    /將順序棧置空        S->top=-1;    （2） 判?？?#160; int StackEmpty（SeqStack *S）            return S->top=-1;

5、60;   （3） 判棧滿  int StackFull（SeqStack *SS）            return S->top=StackSize-1;     （4） 進(jìn)棧  void Push（S，x）            if (StackFull(S)   

6、0;         Error("Stack overflow"); /上溢，退出運(yùn)行       S->data+S->top=x;/棧頂指針加1后將x入棧     （5） 退棧  DataType Pop（S）          if(StackEmpty(S)  

7、60;        Error("Stack underflow"); /下溢，退出運(yùn)行      return S->dataS->top-;/棧頂元素返回后將棧頂指針減1    （6） 取棧頂元素  DataType StackTop（S）           if(StackEmpty(S) 

8、60;         Error("Stack is empty");       return S->dataS->top;     4、兩個(gè)棧共享同一存儲(chǔ)空間    當(dāng)程序中同時(shí)使用兩個(gè)棧時(shí)，可以將兩個(gè)棧的棧底設(shè)在向量空間的兩端，讓兩個(gè)棧各自向中間延伸。當(dāng)一個(gè)棧里的元素較多，超過向量空間的一半時(shí)，只要另一個(gè)棧的元素不多，那么前者就可以占用后者的部分存

9、儲(chǔ)空間。    只有當(dāng)整個(gè)向量空間被兩個(gè)棧占滿（即兩個(gè)棧頂相遇）時(shí)，才會(huì)發(fā)生上溢。因此，兩個(gè)棧共享一個(gè)長度為m的向量空間和兩個(gè)棧分別占用兩個(gè)長度為 m/2和m/2的向量空間比較，前者發(fā)生上溢的概率比后者要小得多。順序棧   與線性表類似棧也有兩種存儲(chǔ)結(jié)構(gòu)，即順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)。棧的順序存儲(chǔ)結(jié)構(gòu)亦稱為順序棧,它是運(yùn)算受限的順序表。1、 順序棧的類型定義  const int MAXSIZE=100; /假定預(yù)分配的棧空間最多為100個(gè)元素  typedef int ElemType;/假定棧元素的數(shù)據(jù)類型為整

10、型  struct SqStack ElemType elemMAXSIZE; /一維數(shù)組      int top;/指針top指向棧頂元素的當(dāng)前位置       注意：    SqStack就是棧的順序存儲(chǔ)結(jié)構(gòu)的類型標(biāo)識(shí)符。    順序棧中元素用向量存放    棧底位置是固定不變的，可設(shè)置在向量兩端的任意一個(gè)端點(diǎn)    棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)

11、整型量top（通常稱top為棧頂指針）來指示當(dāng)前棧頂位置 例:假設(shè)MAXSIZE取值為，圖.2展示了順序棧S中數(shù)據(jù)元素和棧頂指針的關(guān)系。為了與前文所述top=0為空棧相一致，圖中未畫出S.elem0。邏輯上可利用有效空間為S.elem1,.,S.elem5。2、 順序棧的基本操作   前提條件：    設(shè)S是SeqStack類型的指針變量。若棧底位置在向量的低端，即S.elem0是棧底元素。（1） 進(jìn)棧操作    進(jìn)棧時(shí)，需要將top加1  注意：   top=MAXSIZE-1表示棧

12、滿   "上溢"現(xiàn)象-當(dāng)棧滿時(shí)，再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。      上溢是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免?！舅惴?.1】void SqStack:push( ElemType e) if(top= =MAXSIZE-1)cout<<"棧滿溢出"<<endl;exit(1);else top+;elemtop=e;（2） 退棧操作    退棧時(shí)，需將top減1  注意：    top

13、<0表示空棧    "下溢"現(xiàn)象當(dāng)?？諘r(shí)，做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象。      下溢是正?，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。【算法3.2】ElemType SqStack:pop()ElemType x;if(top= =0) cout<< " 棧為空，不能出棧操作"<<endl; exit(1);else x=elemtop;top-;return x;順序棧在進(jìn)棧和退棧操作時(shí)的具體算法演示請(qǐng)點(diǎn)擊查看【算法演示】3、兩個(gè)棧共享同一存儲(chǔ)空間    順序存儲(chǔ)結(jié)構(gòu)條件下的多棧操作也是數(shù)據(jù)結(jié)構(gòu)課程所討論的內(nèi)容。在計(jì)算機(jī)系統(tǒng)軟件中，諸如各種高級(jí)語言的編譯軟件都離不開棧的操作，且往往是同時(shí)使用和管理多個(gè)棧。若讓多個(gè)棧共用一個(gè)向量，其管理和運(yùn)算都很復(fù)雜，這里僅介紹兩個(gè)棧共用一個(gè)向量的問題。兩個(gè)棧共用一個(gè)向量又有不同的分配方法。如圖3.3所示。圖3.3(a)的方法是將向量平均分配給兩個(gè)棧（設(shè)向量有n個(gè)元素），它們的棧底分別在下標(biāo)為0和下標(biāo)為