第三章 棧的相關(guān)內(nèi)容(常州大學(xué))

1、3.1 棧 ( Stack )3.1.1 棧的定義及運算假設(shè)棧S=(a1，a2，a3，an)，則棧底元素?棧頂元素?棧中元素按a1，a2，a3，an的次序進棧，退棧的第一個元素？ 只允許在一端插入和刪除的順序表 允許插入和刪除 的一端稱為棧頂 (top)， 另一端稱為棧底(bottom) 特點 后進先出 (LIFO)棧的示意圖出棧進棧棧頂棧底ana2a1例：對于一個棧，給出輸入項A、B、C，如果輸入項序列由A B C組成，試給出所有可能的輸出序列。A進 A出 B進 B出 C進 C出 ABCA進 A出 B進 C進 C出 B出 ACBA進 B進 B出 A出 C進 C出 BACA進 B進 B出 C進

2、 C出 A出 BCAA進 B進 C進 C出 B出 A出 CBA不可能產(chǎn)生輸出序列CAB棧的順序存儲結(jié)構(gòu)順序棧的定義typedef int DataType;#define maxsize 64typedef struct DataType datamaxsize; int top;SeqStack; 設(shè)s是SeqStack類型的指針變量。 sdata0是棧底元素 進棧時需將stop加1，退棧時需將stop 減1相關(guān)概念:空棧和棧滿 因此： stoptop =stacksize-1 表示棧滿。 當(dāng)棧滿時再做進棧運算必定產(chǎn)生空間溢出，簡稱“上溢” 當(dāng)?？諘r再做退棧運算也將產(chǎn)生溢出，簡稱“下溢”。相

3、關(guān)概念:上溢和下溢進出棧示例toptoptopAABCDEAB空棧 A進棧 B C D E 進棧E D C 出棧toptop-1約定棧頂指針指向棧頂元素的位置注意：棧的基本操作1、初始化2、判棧是否非空3、進棧4、退棧5、取棧頂元素（1）InitStack(&s) 初始化：初始化一個新的棧。（2）StackEmpty(s) 棧空判斷：若棧s空，則返回TRUE；（3）Push(&s,x) 入棧：在棧s的頂部插入元素x，若棧滿，則返回FALSE；（4）Pop(&s) 出棧：若棧s不空，則返回棧頂元素，并從棧頂中刪除該元素；否則，返回空元素NULL。（5）GetTop(s,x

4、) 取棧元素：若棧s不空，則返回棧頂元素；棧的基本操作void InitStack(SeqStack *s) s-top-1; 置空棧void ClearStack(SeqStack *s) s-top-1; 棧的基本運算判?？読nt StackEmpty(SeqStack *s) if (s-top=0) return 0; else return 1;int Push(SeqStack *s,DataType x) s-top+; s-datas-topx; return 1; if (s-top=maxsize-1) printf(“overflown”); return 0; else

5、進棧DataType Pop(SeqStack *s) DataType x x= s-datas-top; s-top-; return(x); if (StackEmpty(s) printf(“underflown”); return 0; else出棧DataType GetTop(SeqStack *s, DataType x) x= s-datas-top; return(x); if (StackEmpty(s) printf(“underflown”); return 0; else 取棧頂元素3.2 棧的應(yīng)用舉例 由于棧結(jié)構(gòu)具有的后進先出的固有特性，致使棧成為程序設(shè)計中常用的

6、工具。以下是幾個棧應(yīng)用的例子。 3.2.1 數(shù)制轉(zhuǎn)換 十進制N和其它進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題,其解決方法很多。 原理: N=(N div d)*d+ N mod d ( 其中:div為整除運算,mod為求余運算) n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算順序輸出順序(2504)8(1348)10數(shù)制轉(zhuǎn)換算法：void conversion( ) InitStack(s); /建空棧 scanf(“%d”,&x); /輸入一個非負十進制整數(shù) while(x!=0) / x不等于零 循環(huán) push(s, x% 8

7、); / x/8第一個余數(shù)進棧 x=x/8; /整除運算 while(! StackEmpty(s) ) x=pop(s); printf(“%d”,x); /依次輸出棧頂元素 3.2.4中綴表達式求值表達式由操作數(shù)（operand）、運算符（operator）和界限符組成的。 在處理表達式前，首先設(shè)置兩個棧：（1）操作數(shù)棧（OPND）：存放操作數(shù)（2）運算符棧（OPTR）：存放運算符。 在運算符棧中先壓入結(jié)束符“#”。運算符可以是算術(shù)運算符、關(guān)系運算符和邏輯符；界限符為左右括號和標(biāo)識表達式結(jié)束的結(jié)束符。算符優(yōu)先關(guān)系表 表達式中任何相鄰運算符c1、c2的優(yōu)先關(guān)系有： c1c2：c1的優(yōu)先級高于

8、c2+ c2 c1 -*/()#+ - * / ( ) # = 算符間的優(yōu)先關(guān)系表注： c1 c2是相鄰算符， c1在左， c2在右讀出一個符號后，作如下處理：（1）是操作數(shù):將其壓入操作數(shù)棧，讀下一個符號。中綴表達式求值算法 （2）是運算符：1）比棧頂高：壓入運算符棧，并讀下一個符號。與棧頂運算符的優(yōu)先級比較2）比棧頂?shù)停簞t從操作數(shù)棧連續(xù)退出兩個操作數(shù)從運算符棧中退出一個運算符，然后作相應(yīng)的運算，并將運算結(jié)果壓入操作數(shù)棧。此時讀出的運算符下次重新考慮3）假如讀出的是“）”，則：A）若運算符棧棧頂不是“（”，連續(xù)退出兩操作數(shù)，退出一個運算符，作相應(yīng)的運算，將結(jié)果壓操作數(shù)棧，然后繼續(xù)執(zhí)行AB）若

9、運算符棧棧頂為“（”，則消去括號，依次讀下一個符號 int express ( ) /運算數(shù)棧，OP為運算符集合。 InitStack(OPTR); Push (OPTR, # ); InitStack(OPND); c=getchar( ); 在算法中，建立了兩個工作棧。一個是OPTR棧，用以保存運算符一個是OPND棧，用以保存操作數(shù)或運算結(jié)果。 while(c!= # | GetTop(OPTR)!=#) if(! In(c,OP) / In(c, OP)判斷c是否 是運算符的函數(shù) Push(OPND,c); /不是運算符則進棧 c=getchar(); else續(xù) switch (Pre

10、cede(GetTop(OPTR), c) case : /棧頂算符優(yōu)先權(quán)高,出棧并將運算結(jié)果入棧OPND op=Pop(OPTR); b=Pop(OPND); a= Pop(OPND); Push(OPND,Operate(a, op, b); break; return GetTop(OPND);char Precede (char sym1,char sym2) /*比較兩操作符優(yōu)先級*/int i; char chl2; int ind2;char re77=, , , , ,=; chl0=sym1; chl1=sym2; for(i=0;i2;i+) switch(chli) case +:indi=0;break; case -:indi=1;break; case *:indi=2;break; case /:indi=3;break; case (:indi=4;break; case ):indi=5;break; case #:indi=6;break; defaul:printf(Error!n);return(0); return(reind0ind1);double Operate(double a,char sym,doubl