第三章棧和隊列13.1棧的類型定義3.2棧的應用舉例3.3棧類型的實現3.4隊列的類型定義3.5隊列類型的實現2通常稱，棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。線性表棧隊列ListInsert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1ListDelete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和隊列是兩種常用的數據類型33.1棧的類型定義ADTStack

{

數據對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數據關系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}約定an端為棧頂，a1端為棧底。基本操作：

}ADTStack4InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())5

InitStack(&S)

操作結果：構造一個空棧S。

DestroyStack(&S)

初始條件：棧S已存在。

操作結果：棧S被銷毀。6

StackEmpty(S)

初始條件：棧S已存在。

操作結果：若棧S為空棧，

則返回TRUE，否則FALE。7

StackLength(S)

初始條件：棧S已存在。

操作結果：返回S的元素個數， 即棧的長度。8

GetTop(S,&e)

初始條件：棧S已存在且非空。

操作結果：用e返回S的棧頂元素。a1a2an……9

ClearStack(&S)

初始條件：棧S已存在。

操作結果：將S清為空棧。10Push(&S,e)

初始條件：棧S已存在。

操作結果：插入元素e為新的棧 頂元素。a1a2ane……11Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結果：刪除S的棧頂元素， 并用e返回其值。a1a2anan-1

……123.2棧的應用舉例例一、數制轉換例二、括號匹配的檢驗例三、行編輯程序問題例四、表達式求值例五、實現遞歸13

例一、數制轉換

算法基于原理：

N=(Ndivd)×d+Nmodd

14例如：（1348)10=(2504)8，其運算過程如下：

NNdiv8Nmod8

13481684

168210

2125

202計算順序輸出順序15voidconversion(){InitStack(S);

scanf("%d",N);

while(N){

Push(S,N%8);N=N/8;

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversion16例二、括號匹配的檢驗則檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。假設在表達式中（［］（））或［（［］［］）］等為正確的格式。例如：考慮下列括號序列：[([][])]1234567817分析可能出現的不匹配的情況:到來的右括弧非是所“期待”的;到來的是“不速之客”;直到結束，也沒有到來所“期待”的括弧;［（］）或(()])或（［（））均為不正確的格式。18算法的設計思想：1）凡出現左括弧，則進棧；2）凡出現右括弧，首先檢查棧是否空若棧空，則表明該“右括弧”多余否則和棧頂元素比較，若相匹配，則“左括弧出棧”否則表明不匹配3）表達式檢驗結束時，若棧空，則表明表達式中匹配正確否則表明“左括弧”有余19Statusmatching(string&exp){

intstate=1;

while(i<=Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...20例三、行編輯程序問題如何實現？“每接受一個字符即存入存儲器”?

并不恰當！21設立一個輸入緩沖區，用以接受用戶輸入的一行字符，然后逐行存入用戶數據區;并約定“#”為退格符，“@”為退行符。在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發現有誤時可以及時更正。合理的作法是：22假設從終端接受了這樣兩行字符：

whli##ilr#e（s#*s)則實際有效的是：

while(*s)outcha@putchar(*s=#++);putchar(*s++);23

while(ch!=EOF&&ch!='\n'){

switch(ch){

case'#':Pop(S,c);break;

case'@':ClearStack(S);break;//重置S為空棧

default

:Push(S,ch);break;

}ch=getchar();//從終端接收下一個字符

}ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();while(ch!=EOF){//EOF為全文結束符將從棧底到棧頂的字符傳送至調用過程的數據區；24限于二元運算符的表達式定義:

表達式::=(操作數)+(運算符)+(操作數)操作數::=簡單變量|表達式簡單變量::=標識符|無符號整數例四、表達式求值25

表達式的三種標識方法：設

Exp=S1+

OP

+S2則稱

OP

+S1+S2為前綴表示法

S1+

OP

+S2為中綴表示法

S1+S2+

OP為后綴表示法

26例如:Exp=ab

+

(cd/e)f前綴式:+

ab

c/def中綴式:ab

+

cd/ef后綴式:ab

cde/f

+結論:1）操作數之間的相對次序不變;2）運算符的相對次序不同;3）中綴式丟失了括弧信息，致使運算的次序不確定;4)前綴式的運算規則為:連續出現的兩個操作數和在它們之前且緊靠它們的運算符構成一個最小表達式;5)后綴式的運算規則為:

運算符在式中出現的順序恰為表達式的運算順序;每個運算符和在它之前出現

且緊靠它的兩個操作數構成一個最小表達式;27如何從后綴式求值？先找運算符，再找操作數例如：abcde/f+abd/ec-d/e(c-d/e)f28abc×d－ef/+×abbaa×bcdeedd/ed/ecc-d/effc-d/e（c-d/e）×f如何從后綴式求值？29如何從原表達式求得后綴式？

每個運算符的運算次序要由它之后的一個運算符來定，在后綴式中,優先數高的運算符領先于優先數低的運算符。分析“原表達式”和“后綴式”中的運算符:原表達式:a+b

cd/e

f后綴式:abc+de/f

30a×b+(－c/d×e)f后綴式棧#×+(－/×ab×cde/－f#×+31從原表達式求得后綴式的規律為：1)設立暫存運算符的棧;2)設表達式的結束符為“#”,

預設運算符棧的棧底為“#”3)若當前字符是操作數，則直接發送給后綴式;324)若當前運算符的優先數高于棧頂運算符，則進棧;5)否則，退出棧頂運算符發送給后綴式;

6)“(”對它之前后的運算符起隔離作用，“)”可視為自相應左括弧開始的表達式的結束符。從原表達式求得后綴式的規律為：33voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,#);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}

if(ch!=#){p++;ch=*p;}else{Pop(S,ch);Pass(Suffix,ch);}

}//while}//CrtExptree……34switch(ch){

case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

()

{Pass(Suffix,c);Pop(S,c)}

break;

defult:while(Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=

#)Push(S,ch);

break;

}

//switch35例六、實現遞歸將所有的實在參數、返回地址等信息傳遞給被調用函數保存;為被調用函數的局部變量分配存儲區;將控制轉移到被調用函數的入口。當在一個函數的運行期間調用另一個函數時，在運行該被調用函數之前，

需先完成三項任務：36保存被調函數的計算結果;釋放被調函數的數據區;依照被調函數保存的返回地址將控制轉移到調用函數。從被調用函數返回調用函數之前，應該完成下列三項任務：37多個函數嵌套調用的規則是:此時的內存管理實行“棧式管理”后調用先返回！例如：voidmain(){voida(…){voidb(…){

………a(…);b(…);

……}//main}//a}//bMain的數據區函數a的數據區函數b的數據區38遞歸工作棧：遞歸過程執行過程中占用的數據區。遞歸工作記錄：每一層的遞歸參數合成一個記錄。當前活動記錄：棧頂記錄指示當前層的執行情況。當前環境指針：遞歸工作棧的棧頂指針。遞歸函數執行的過程可視為同一函數進行嵌套調用。39voidhanoi(intn,charx,chary,charz){//將塔座x上按直徑由小到大且至上而下編號為1至n//的n個圓盤按規則搬到塔座z上，y可用作輔助塔座。1if(n==1)2move(x,1,z);//將編號為１的圓盤從x移到z3else{4hanoi(n-1,x,z,y);//將x上編號為１至n-1的//圓盤移到y,z作輔助塔5move(x,n,z);//將編號為n的圓盤從x移到z6hanoi(n-1,y,x,z);//將y上編號為１至n-1的//圓盤移到z,x作輔助塔7}8}P55403.2棧的應用舉例例一、數制轉換例二、括號匹配的檢驗例三、行編輯程序問題例四、表達式求值例五、實現遞歸413.3 棧類型的實現順序棧鏈棧42//-----棧的順序存儲表示-----

#defineSTACK_INIT_SIZE100;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;類似于線性表的順序映象實現，指向表尾的指針可以作為棧頂指針。43baseStacksizetopTop=base空棧atopbctop棧top44

StatusInitStack(SqStack&S,intmaxsize){

//構造一個最大空間為maxsize的空順序棧SS.base=new

ElemType[maxsize];

if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base;S.stacksize=maxsize;

returnOK;}45

StatusPush(SqStack&S,SElemTypee){//若棧不滿，則將e插入棧頂if(S.top-S.base>=S.stacksize)

//棧滿

returnOVERFLOW;*S.top++=e;

returnOK;}46StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，//用e返回其值，并返回OK；//否則返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}47棧頂指針鏈棧∧a1an注意:鏈棧中指針的方向an-1棧底元素48

習題設將整數1、2、3、4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下有問題：（1）若入棧出棧次序為push(1)，pop()，push(2)，push(3)，pop()，pop()，push(4)，pop()，則出棧的數字序列為什么？（2）請分析1、2、3、4的24種排列中，哪些序列可以通過相應的入出棧得到。49ADTQueue{

數據對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數據關系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}約定其中a1端為隊列頭，an端為隊列尾基本操作：3.4隊列的類型定義}

ADTQueue50隊列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)51InitQueue(&Q)

操作結果：構造一個空隊列Q。

DestroyQueue(&Q)

初始條件：隊列Q已存在。

操作結果：隊列Q被銷毀，

不再存在。52QueueEmpty(Q)

初始條件：隊列Q已存在。

操作結果：若Q為空隊列，則 返回TRUE，否則 返回FALSE。53

QueueLength(Q)

初始條件：隊列Q已存在。

操作結果：返回Q的元素個數， 即隊列的長度。54

GetHead(Q,&e)

初始條件：Q為非空隊列。

操作結果：用e返回Q的隊 頭元素。a1a2an……55

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結果：刪除Q的隊頭元素，并用e返回其值。a1a2an……

56

EnQueue(&Q,e)

初始條件：隊列Q已存在。

操作結果：插入元素e為Q的新的隊尾元素。a1a2ane……57

ClearQueue(&Q)

初始條件：隊列Q已存在。

操作結果：將Q清為空隊列。583.5隊列類型的實現鏈隊列——鏈式映象循環隊列——順序映象59

typedefstructQNode{//結點類型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;鏈隊列——鏈式映象60typedefstruct{

//鏈隊列類型

QueuePtrfront;//隊頭指針

QueuePtrrear;//隊尾指針}LinkQueue;a1∧an…Q.frontQ.frontQ.rear∧空隊列Q.rear隊頭元素61

StatusInitQueue(LinkQueue&Q){//構造一個空隊列Q

Q.front=Q.rear=

newQNode;

if(!Q.front)exit(OVERFLOW);//存儲分配失敗

Q.front->next=NULL;

returnOK;}62

StatusEnQueue(LinkQueue&Q,QElemTypee){

//插入元素e為Q的新的隊尾元素

p=newQNode;

if(!p)exit(OVERFLOW);//存儲分配失敗p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

returnOK;}Q.frontQ.rear∧epa1∧an…63

StatusDeQueue(LinkQueue&Q,QElemType&e){//若隊列不空，則刪除Q的隊頭元素，//用e返回其值，并返回OK；否則返回ERROR

if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;

Q.front->next=p->next;delete(p);

returnOK;}if(Q.rear==p)Q.rear=Q.front;64Q.frontQ.reara1∧注意：出隊列操作的特殊情況∧if(Q.rear==p)Q.rear=Q.front;65#defineMAXQSIZE100//最大隊列長度typedefstruct{QElemType*base;//動態分配存儲空間

intfront;//頭指針，若隊列不空，//指向隊列頭元素intrear;//尾指針，若隊列不空，指向//隊列尾元素的下一個位置

intqueuesize;}SqQueue;循環隊列——順序映象66注意：順序隊列的幾種情況：abcQ.frontQ.rear1、一般情況：100Q.frontQ.rear02、初始化：67abcQ.frontQ.rearabQ.front注意：順序隊列的幾種情況：3、特殊情況：cQ.reardQ.rearQ.frontdQ.rearQ.rear6