第3章棧和隊(duì)列主講教師:***時(shí)間:2025.07.01目錄CONTENTS01棧02棧的應(yīng)用舉例03隊(duì)列目錄CONTENTS棧3.13.1棧的概念及ADT定義棧是一種只能在一端進(jìn)行插入或刪除操作的線性表。端點(diǎn)1端點(diǎn)2棧只能選取同一個(gè)端點(diǎn)進(jìn)行插入和刪除操作線性表3.1棧的概念及ADT定義允許進(jìn)行插入、刪除操作的一端稱為棧頂。表的另一端稱為棧底。當(dāng)棧中沒(méi)有數(shù)據(jù)元素時(shí)，稱為空棧。棧的插入操作通常稱為進(jìn)?；蛉霔！５膭h除操作通常稱為退?；虺鰲?。棧頂棧底棧示意圖進(jìn)棧出棧棧的幾個(gè)概念3.1棧的概念及ADT定義棧的主要特點(diǎn)是“后進(jìn)先出”，即后進(jìn)棧的元素先出棧。棧也稱為后進(jìn)先出表。走進(jìn)死胡同的5人要按相反次序退出假設(shè)死胡同的寬度恰好只夠正一個(gè)人死胡同就是一個(gè)棧！例如：3.1棧的概念及ADT定義有3個(gè)元素A，B，C，入棧順序是A，B，C，則出棧順序有幾種可能？

CAB出棧順序可能出現(xiàn)CAB的情況嗎？ABCABCCBAAABBCCAABCCBABBACCABBCCA3.1棧的概念及ADT定義設(shè)一個(gè)棧的輸入序列為a，b，c，d，則借助一個(gè)棧所得到的輸出序列不可能是（）。

A.c，d，b，a B.d，c，b，a

C.a，c，d，b D.d，a，b，c

棧示例abcd答案為D選項(xiàng)D是不可能的？3.1棧的概念及ADT定義示例

一個(gè)棧的入棧序列為1，2，3，…，n，其出棧序列是p1，p2，p3，…，pn。若p2=3，則p3可能取值的個(gè)數(shù)是（）多少？(全國(guó)考研題)A.n-3B.n-2C.n-1D.無(wú)法確定p3可以取1：1進(jìn)，2進(jìn)，2出，3進(jìn)，3出，1出，…。p3可以取2：1進(jìn)，1出，2進(jìn)，3進(jìn)，3出，2出，…。p3可以取4：1進(jìn)，1出，2進(jìn)，3進(jìn)，3出，4進(jìn)，4出，…。p3可以取5：1進(jìn)，1出，2進(jìn)，3進(jìn)，3出，4進(jìn)，5進(jìn)，5出，…。…p3可以取除了3外的任何值,共有n-1種可能。答案為C。3?n

…321不可能是3解3.1棧的概念及ADT定義棧的幾種基本運(yùn)算如下:

InitStack(&s)：初始化棧。構(gòu)造一個(gè)空棧s。

StackEmpty(S)：判斷棧是否為空:若棧s為空，則返回真；否則返回假。

Push(&S，x)：入棧。將元素e插入到棧s中作為棧頂元素。

Pop(&s，&e)：出棧。從棧s中退出棧頂元素，并將其值賦給e。

GetTop(s，&e)：取棧頂元素。返回當(dāng)前的棧頂元素，并將其值賦給e。DestroyStack(&s)：撤銷棧。釋放棧s占用的存儲(chǔ)空間。

棧抽象數(shù)據(jù)類型＝邏輯結(jié)構(gòu)＋基本運(yùn)算（運(yùn)算描述）3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)棧中元素邏輯關(guān)系與線性表的相同，棧可以采用與線性表相同的存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)棧順序表鏈表順序棧鏈棧

1．棧的生成方式（1）向下生成的棧。棧頂在高地址端，棧底在低地址端。如圖(a)所示。入棧時(shí)top++；出棧時(shí)top--。（2）向上生成的棧。棧頂在低地址端，棧底在高地址端。如圖(b)所示。入棧時(shí)top--；出棧時(shí)top++。3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)

2．棧頂指針的兩種指示方式。棧頂指針指向什么位置，對(duì)入棧和出棧時(shí)的操作語(yǔ)句有直接影響。通常有兩種指示方式：（1）棧頂指針指向第一個(gè)空單元。使用這種指示方式，入棧時(shí)，先寫元素，后修改棧頂指針；出棧時(shí)先修改棧頂指針，后讀元素。（2）棧頂指針指向棧頂處的元素。使用這種指示方式，入棧時(shí)，先修改棧頂指針，后寫元素；出棧時(shí)先讀元素，后修改棧頂指針。3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧3．順序棧的存儲(chǔ)結(jié)構(gòu)（1）靜態(tài)順序棧假設(shè)棧的元素個(gè)數(shù)最大不超過(guò)正整數(shù)MaxSize，所有的元素都具有同一數(shù)據(jù)類型SElemType，則可用下列方式來(lái)聲明靜態(tài)順序棧類型SqStack:typedefstructstatic_sq_stack{SElemTypedata[MaxSize]；

inttop； //棧頂指針}SStack；3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧3．順序棧的存儲(chǔ)結(jié)構(gòu)（2）動(dòng)態(tài)順序棧類似于順序表的定義，用一塊連續(xù)的存儲(chǔ)區(qū)域順序存放棧的數(shù)據(jù)元素。則可用下列方式來(lái)聲明動(dòng)態(tài)順序棧類型SqStack:typedefstruct{SElemType*base;SElemType*top;intStackSize;}SqStack;3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序?？諚ase==top

是?？諛?biāo)志Stacksize=4topAbasebasetopABABCtopbasebasetop3120top指示真正的棧頂元素之上的下標(biāo)地址。棧滿時(shí)的處理方法：1.報(bào)錯(cuò)，返回操作系統(tǒng)。2.分配更大的空間，作為棧的存儲(chǔ)空間,將原棧的內(nèi)容移入新棧。3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧例如：MaxSize=543210top（a）空棧4321a0top（b）a進(jìn)棧e4d3c2b1a0top（c）b、c、d、e進(jìn)棧4d3c2b1a0top（d）出棧一次總結(jié)：

約定top總是指向棧頂元素的下一個(gè)位置，初始值為0當(dāng)top=MaxSize時(shí)不能再進(jìn)棧－棧滿進(jìn)棧時(shí)top增1，出棧時(shí)top減1basebasebasebase3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧順序棧4要素：

?？諚l件：top=base

棧滿條件：top=MaxSize

進(jìn)棧操作：將e放在top處;top++

退棧操作：top--;從top處取出元素e;43210top（a）空棧4321a0top（b）a進(jìn)棧e4d3c2b1a0top（c）b、c、d、e進(jìn)棧4d3c2b1a0top（d）出棧一次順序棧的各種狀態(tài)basebasebasebase3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧3．順序棧的存儲(chǔ)結(jié)構(gòu)（3）雙棧為了共享存儲(chǔ)空間，有時(shí)將兩個(gè)棧用一塊存儲(chǔ)空間存放，兩棧的棧頂相對(duì)。優(yōu)點(diǎn)：互相調(diào)劑，靈活性強(qiáng)，減少溢出機(jī)會(huì)。

3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧3．順序棧的存儲(chǔ)結(jié)構(gòu)（4）多棧與雙棧類似，將多個(gè)棧存放在一塊連續(xù)區(qū)域內(nèi)，多個(gè)?？梢缘乳L(zhǎng)，也可以不等長(zhǎng)。3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧順序棧-初始化棧構(gòu)造一個(gè)空棧；步驟：(1)分配空間并檢查空間是否分配失敗，若失敗則返回錯(cuò)誤；basestacksizetops(2)設(shè)置棧底和棧頂指針；

S.top=S.base;(3)設(shè)置棧大小。3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧StatusInitStack(SqStack&S){

S.base=(SElemType*)malloc(sizeof(SElemType)*MaxSize)

if(!S.base) returnOVERFLOW;

S.top=S.base; S.stackSize=MAXSIZE; returnOK;}（1）初始化棧InitStack(&s)3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧StatusDestroyStack(SqStack&S){inti,len=s->StackSize;for(i=0;i<len;i++){free(S->base);S->base++;}

S.base=S.top=NULL;S.stacksize=0; }returnOK;}（2）銷毀棧DestroyStack(&s)3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧（3）判斷棧是否為空StackEmpty(s)boolStackEmpty(SqStackS){ return(S.top==S.base);}basetop31203.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧（4）進(jìn)棧Push(&s，e)(1)判斷是否棧滿，若滿則重新申請(qǐng)；(2)元素e壓入棧頂；(3)棧頂指針加1。StatusPush(SqStack&S,SElemTypee){if(S.top–S.base>=S.stacksize))//棧滿{S.base=(SElemType*)realloc(S.base,sizeof(SElemType)*(S.StackSize+STACKINCREMET));if(!S.base)exit(OVERFLOW);//申請(qǐng)失敗做溢出處理

S.top=S.Stacksize+S.base;//修改棧頂指針

S.stacksize+=STACKINCREMET;//修改棧的大小

}

*S.top++=e; returnOK;}*S.top=e;S.top++;ABCtopbase3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧（5）出棧Pop(&s，&e)(1)判斷是否棧空，若空則出錯(cuò)；(2)獲取棧頂元素e；(3)棧頂指針減1。StatusPop(SqStack&S,SElemType&e){ if(S.top==S.base)//?？?/p>

returnERROR;

e＝*--S.top; returnOK;}--S.top;e=*S.top;ABCtopbase3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧（6）取棧頂元素GetTop(s，&e)判斷是否空棧，若空則返回錯(cuò)誤否則通過(guò)棧頂指針獲取棧頂元素StatusGetTop(SqStackS,SElemType&e){ if(S.top==S.base) returnERROR; //?？?/p>

e=*(S.top–1); returnOK;}

e=*(S.top--);ABCtopbase3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-順序棧（7）求棧長(zhǎng)StackLength(s)intStackLength(SqStackS){ returnS.top–S.base;}basetopAB3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-鏈棧運(yùn)算是受限的單鏈表，只能在鏈表頭部進(jìn)行操作，故沒(méi)有必要附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針typedefstructSNode{SElemTypedata;structSNode*next;}SNode,*LinkStack;LinkStackS;

datanext棧頂棧底∧S3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-鏈棧voidInitStack(LinkStack&top){

top=NULL;}∧top(1)初始化棧InitStack（&top）3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-鏈棧StatusStackEmpty(LinkStacktop)

{

if(top==NULL)returnTRUE;

elsereturn

FALSE;

}

(2)判斷鏈棧是否為空StackEmpty（top）3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-鏈棧boolPush(LinkStack&top,SElemTypee)

{

SNode*s;s=(SNode*)malloc（sizeof（SNode））;//生成新結(jié)點(diǎn)pif(!s)exit(OVERFLOW);

s->data=e;s->next=top;top=s;

returntrue;}es∧top(3)入棧Push（top,e）top3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-鏈棧(4)出棧Pop(&top,&e)∧topAe=‘A’BoolPop(LinkStack&top,SElemType&e){LinkStackp;if（!top）returnfalse;else{e=top->data;p=top;top=top->next;free(p);returntrue;}ptop3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-鏈棧(5)求棧長(zhǎng)（元素個(gè)數(shù)）StackLength(top)intStackLength(LinkStacktop){LinkStackp;intn=0;p=top;while(p)//每移動(dòng)一個(gè)結(jié)點(diǎn)，個(gè)數(shù)n加1{n++;p=p->next;}returnn;}3.1.2棧的存儲(chǔ)結(jié)構(gòu)與算法實(shí)現(xiàn)-鏈棧(6)取鏈棧棧頂元素GetTop(LinkStacktop)SElemTypeGetTop(LinkStacktop){if(top==NULL)exit(1)；

elsereturntop–>data;}棧的應(yīng)用舉例3.23.2棧的應(yīng)用舉例例3.1數(shù)制轉(zhuǎn)換問(wèn)題十進(jìn)制二進(jìn)制：n=10102510%2=025%2=12221202%2=01%2=1低位高位用棧保存3.2棧的應(yīng)用舉例01初始化一個(gè)空棧S。02當(dāng)十進(jìn)制數(shù)N非零時(shí)，循環(huán)執(zhí)行以下操作：把N與2求余得到的八進(jìn)制數(shù)壓入棧S；N更新為N與2的商。03當(dāng)棧S非空時(shí)，循環(huán)執(zhí)行以下操作：彈出棧頂元素e；輸出e。3.2棧的應(yīng)用舉例#defineLength15voidconversion(intN，intr){intS[Length],top;//定義一個(gè)順序棧

intx;top=0;//初始化棧

while(N){S[top++]=N%r;//余數(shù)入棧

N=N/r;//商作為被除數(shù)繼續(xù)

}while(top!=-1)//出棧輸出

{x=S[--top];printf(“%d”,x);}}3.2棧的應(yīng)用舉例例3.2表達(dá)式語(yǔ)法檢查問(wèn)題。檢查一個(gè)表達(dá)式中的括號(hào)是否配對(duì)。

一個(gè)表達(dá)式中的左右括號(hào)是按最近位置配對(duì)的。所以利用一個(gè)棧來(lái)進(jìn)行求解。采用順序?；蜴湕?。算法設(shè)計(jì)思路3.2棧的應(yīng)用舉例例3.2表達(dá)式語(yǔ)法檢查問(wèn)題。檢查一個(gè)表達(dá)式中的括號(hào)是否配對(duì)。

例如：exp=“(()))”②‘(‘進(jìn)棧(⑤遇到’)’，棧為空，返回false表達(dá)式括號(hào)不配對(duì)情況的演示①‘(‘進(jìn)棧(③遇到’)’，棧頂為’(‘，退棧④遇到’)’，棧頂為’(‘，退棧3.2棧的應(yīng)用舉例例3.2表達(dá)式語(yǔ)法檢查問(wèn)題。檢查一個(gè)表達(dá)式中的括號(hào)是否配對(duì)。

例如：exp=“(())”②‘(‘進(jìn)棧((①‘(‘進(jìn)棧③遇到’)’，棧頂為’(‘，退棧④遇到’)’，棧頂為’(‘，退棧?？涨襡xp掃描完，返回true表達(dá)式括號(hào)配對(duì)情況的演示3.2棧的應(yīng)用舉例01初始化一個(gè)空棧S。02字符ch賦初值‘#’，當(dāng)ch!=”\n”時(shí)，循環(huán)執(zhí)行以下操作：凡是左括號(hào)壓入棧S；凡是右括號(hào)出棧S，配對(duì)

。03當(dāng)棧S空時(shí)，返回正確信息，非空，返回錯(cuò)誤。3.2棧的應(yīng)用舉例#defineSTRLEN255boolcheak(){charS[STRLEN];//初始化字符棧

inttop=-1;charch=’#’;while(ch!=’\n’)//重復(fù)從鍵盤讀字符，直到讀到回車換行符{scanf(“%c”,&ch);switch(ch)//根據(jù)讀入字符的不同情況分別處理

{case’(’:case’[’://ch是’(’或’[’時(shí)，入棧{S[++top=ch;break;}3.2棧的應(yīng)用舉例case’)’://處理ch=’)’時(shí)的情況{if(S[top]==’(’)top--;elseif(S[top]==’[’)returnERROR;break;}case’]’://處理ch=’]’時(shí)的情況{if(S[top]==’[’)top--;elseif(S[top]==’(’)returnERROR;break;}}if(top<0)returnTRUE;//?？諘r(shí)返回真，否則返回假

elsereturnfalse;

}3.2棧的應(yīng)用舉例例3.3表達(dá)式求值問(wèn)題。限于二元運(yùn)算符的表達(dá)式定義:

表達(dá)式::=(操作數(shù))(運(yùn)算符)(操作數(shù))

操作數(shù)::=簡(jiǎn)單變量|表達(dá)式簡(jiǎn)單變量::=標(biāo)識(shí)符|無(wú)符號(hào)整數(shù)

表達(dá)式的三種標(biāo)識(shí)方法：設(shè)

Exp=S1

OP

S2則稱OP

S1

S2

為前綴表示法

S1

S2

OP

為后綴表示法

S1

OP

S2

為中綴表示法

例如:Exp=a

b

+

(c

d/e)

f前綴式:

+

ab

c/def中綴式:

a

b

+(c

d/e)

f后綴式:

ab

cde/

f

+結(jié)論:1)操作數(shù)之間的相對(duì)次序不變;2)運(yùn)算符的相對(duì)次序不同;4)前綴式的運(yùn)算規(guī)則為:

連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;5)后綴式的運(yùn)算規(guī)則為:運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;

每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式;3)中綴表達(dá)式求值要考慮算符優(yōu)先級(jí);3.2棧的應(yīng)用舉例1.中綴表達(dá)式求值運(yùn)算規(guī)則先乘除，后加減；從左算到右；先括號(hào)內(nèi)，后括號(hào)外；例：求表達(dá)式4+23-10/5

的值。

計(jì)算順序?yàn)椋?+23-10/5=4+6-10/5=10-10/5=10-2=8

操作數(shù)或結(jié)果運(yùn)算符#4+2

3

610-10/5823.2棧的應(yīng)用舉例OperandTypeExpressionEvaluate()//從鍵盤輸入中綴表達(dá)式，計(jì)算其值

{InitStack(OPTR);Push(OPTR,‘#’);//初始化運(yùn)算符棧

InitStack(OPND);//初始化操作數(shù)棧

ch=getchar();while(ch!=‘#‘&&GetTop(OPTR)!=‘#‘)//逐個(gè)讀字符ch且不等于#{if(!in(ch,OP))Push(OPND,ch);//不是運(yùn)算符入操作數(shù)棧else{switch(Preced（ch,GetTop(OPTR)）)//是運(yùn)算符時(shí)分別做不同處理

{case‘>’://ch的優(yōu)先級(jí)低于棧頂運(yùn)算符的優(yōu)先級(jí){Push(OPTR,ch);break;}3.2棧的應(yīng)用舉例OperandTypeExpressionEvaluate()//從鍵盤輸入中綴表達(dá)式，計(jì)算其值

{InitStack(OPTR);Push(OPTR,‘#’);//初始化運(yùn)算符棧

InitStack(OPND);//初始化操作數(shù)棧

ch=getchar();while(ch!=‘#‘&&GetTop(OPTR)!=‘#‘)//逐個(gè)讀字符ch且不等于#{if(!in(ch,OP))Push(OPND,ch);//不是運(yùn)算符入操作數(shù)棧else{switch(Preced（ch,GetTop(OPTR)）)//是運(yùn)算符時(shí)分別做不同處理

{case‘>’://ch的優(yōu)先級(jí)低于棧頂運(yùn)算符的優(yōu)先級(jí){Push(OPTR,ch);break;}3.2棧的應(yīng)用舉例2.后綴表達(dá)式求值后綴表達(dá)式求值優(yōu)點(diǎn)：

1）無(wú)界限符；

2）求值時(shí)無(wú)需考慮操作符的優(yōu)先級(jí)。因此用后綴表達(dá)式求值計(jì)算簡(jiǎn)便，在編譯程序中常用。

利用棧很容易計(jì)算后綴表達(dá)式的值。為了方便算法的實(shí)現(xiàn)，在后綴表達(dá)式的后面，通常會(huì)加上1個(gè)后綴表達(dá)式的結(jié)束符“?！?。3.2棧的應(yīng)用舉例2.后綴表達(dá)式求值51如何從后綴式求值？先找運(yùn)算符，再找操作數(shù)例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

fa*b+(c-d/e)

f3.2棧的應(yīng)用舉例2.后綴表達(dá)式求值后綴表達(dá)式求值算法:

（1）從左往右順序掃描后綴表達(dá)式；（2）遇到操作數(shù)就進(jìn)棧；（3）遇到操作符就從棧中彈出兩個(gè)操作數(shù)，并執(zhí)行該操作符規(guī)定的運(yùn)算；并將結(jié)果進(jìn)棧；（4）重復(fù)上述操作，直到表達(dá)式結(jié)束。彈出棧頂元素即為結(jié)果。3.2棧的應(yīng)用舉例OperandTypeexprEvaluatel(charA[]){InitStack(S);ch=*A++;while(ch!=’#’){if(!In(ch,OP)Push(S,ch);//讀入的字符是操作數(shù)時(shí)入棧

else//是運(yùn)算符，取出兩個(gè)操作數(shù)

{Pop(S,x);Pop(S,y);switch(ch)//對(duì)兩個(gè)操作數(shù)進(jìn)行相應(yīng)計(jì)算

{case’+’：c=a+b;break;case’-’：c=a-b;break;case’*’：c=a*b;break;case’/’：c=a/b;break;case’%’：c=a%b;break;}Push(S,c);//計(jì)算結(jié)果入棧

}ch=*A++;//讀下一個(gè)字符

}Pop(S,c);returnc;//返回結(jié)果}//算法結(jié)束3.2棧的應(yīng)用舉例3．中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式a+b*c+(d*e+f)*gde*f+bc*de*f+g*abc*+abc*+de*f+g*+abc*+de*f+g*+中綴=>后綴操作數(shù)的順序不變3.2棧的應(yīng)用舉例3．中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式a+b*c+(d*e+f)*g*a+b

后綴表達(dá)式:

c*+##①若當(dāng)前字符是操作數(shù)：則直接發(fā)送給后綴式②若當(dāng)前字符是運(yùn)算符：若運(yùn)算符的優(yōu)先級(jí)高于棧頂運(yùn)算符，則進(jìn)棧轉(zhuǎn)換算法步驟：依次讀入中綴表達(dá)式字符+(de**+f+*g*+#abc*+de*f+g*+3.2棧的應(yīng)用舉例3．中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式和前述對(duì)中綴表達(dá)式求值的方法類似，但只需要運(yùn)算符棧，遇到操作數(shù)時(shí)直接放入后綴表達(dá)式存儲(chǔ)區(qū)。假設(shè)中綴表達(dá)式本身合法且在字符數(shù)組A中，轉(zhuǎn)換后的后綴表達(dá)式存儲(chǔ)在字符數(shù)組B中。算法思想：當(dāng)讀到操作數(shù)時(shí)，向后綴表達(dá)式數(shù)組B中順序存放，而讀到運(yùn)算符時(shí)，類似于中綴表達(dá)式求值時(shí)對(duì)運(yùn)算符的處理過(guò)程，但運(yùn)算符出棧后不是進(jìn)行相應(yīng)的運(yùn)算，而是存放到后綴表達(dá)式數(shù)組B中。（算法見(jiàn)課本）3.2棧的應(yīng)用舉例例3.4利用棧實(shí)現(xiàn)遞歸函數(shù)計(jì)算。

longfact(longn){if(n==0)return1;

elsereturnn*fact(n-1);}遞歸的定義

若一個(gè)對(duì)象部分地包含它自己，

或用它自己給自己定義,則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過(guò)程直接地或間接地調(diào)用自己，則稱這個(gè)過(guò)程是遞歸的過(guò)程。3.2棧的應(yīng)用舉例當(dāng)多個(gè)函數(shù)構(gòu)成嵌套調(diào)用時(shí),遵循后調(diào)用先返回棧例3.4利用棧實(shí)現(xiàn)遞歸函數(shù)計(jì)算。

3.2棧的應(yīng)用舉例例3.4利用棧實(shí)現(xiàn)遞歸函數(shù)計(jì)算。

以下三種情況常常用到遞歸方法：遞歸定義的數(shù)學(xué)函數(shù)可遞歸求解的問(wèn)題具有遞歸特性的數(shù)據(jù)結(jié)構(gòu)3.2棧的應(yīng)用舉例例3.4利用棧實(shí)現(xiàn)遞歸函數(shù)計(jì)算。

1.遞歸定義的數(shù)學(xué)函數(shù)階乘函數(shù):2階Fibonaci數(shù)列:3.2棧的應(yīng)用舉例例3.4利用棧實(shí)現(xiàn)遞歸函數(shù)計(jì)算。

樹

2.具有遞歸特性的數(shù)據(jù)結(jié)構(gòu)RootLchildRchild廣義表A=(a,A)3.可遞歸求解的問(wèn)題迷宮問(wèn)題Hanoi塔問(wèn)題3.2棧的應(yīng)用舉例當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三件事：將實(shí)參等傳遞給被調(diào)用函數(shù)，保存返回地址（入棧）；為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)；將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成：保存被調(diào)函數(shù)的計(jì)算結(jié)果；釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；按被調(diào)函數(shù)保存的返回地址（出棧）將控制轉(zhuǎn)移到調(diào)用函數(shù)。多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：后調(diào)用先返回。此時(shí)的內(nèi)存管理實(shí)行“棧式管理”。

3.2棧的應(yīng)用舉例floatfact(intn){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}遞歸調(diào)用執(zhí)行過(guò)程：主函數(shù)main()Printf(fact(5))第一層調(diào)用n=5s=5*fact(4)第二層調(diào)用n=4s=4*fact(3)第三層調(diào)用n=3s=3*fact(2)第四層調(diào)用n=2s=2*fact(1)第五層調(diào)用n=1s=1*fact(0)fact(5)=120輸出s=120.00第六層調(diào)用n=0s=1fact(4)=24fact(3)=6fact(2)=2fact(1)=1fact(0)=1主a

5a4a3a2a1aprintf(“5!=%f\n”,fact(5));basefloatfact(intn){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(intn){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(intn){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(intn){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}floatfact(intn){floats;if(n==0)

s=1;else

s=n*fact(n-1);return(s);}n=5n=4n=3n=2n=1n=03.2棧的應(yīng)用舉例例3.5漢諾塔問(wèn)題。

在印度圣廟里，一塊黃銅板上插著三根寶石針。主神梵天在創(chuàng)造世界時(shí)，在其中一根針上穿好了由大到小的64片金片，這就是漢諾塔。僧侶不停移動(dòng)這些金片，一次只移動(dòng)一片，小片必在大片上面。當(dāng)所有的金片都移到另外一個(gè)針上時(shí)，世界將會(huì)滅亡。

漢諾塔3.2棧的應(yīng)用舉例例3.5漢諾塔問(wèn)題。

規(guī)則(1)每次只能移動(dòng)一個(gè)圓盤。(2)圓盤可以插在A，B和C中的任一塔座上。(3)任何時(shí)刻不可將較大圓盤壓在較小圓盤之上。ABC3.2棧的應(yīng)用舉例例3.5漢諾塔問(wèn)題。

n=1，則直接從A移到C。否則：

(1)用

C柱做過(guò)渡，將

A的(n-1)個(gè)移到

B；(2)將

A最后一個(gè)直接移到

C；(3)用

A做過(guò)渡，將

B的

(n-1)個(gè)移到

C。3.2棧的應(yīng)用舉例例3.5漢諾塔問(wèn)題。

voidhanoi(intn,charx,chary,charz)//將x柱上的個(gè)盤子借助y柱移動(dòng)到z柱上

{if(n==1)move(x,1,z);//將x柱上編號(hào)為1的盤子移動(dòng)到z柱上

else{hanio(n-1,x,z,y);//將x柱上的n-1個(gè)盤子移動(dòng)到y(tǒng)柱上

move(x,n,z);//將x柱上編號(hào)為n的盤子移動(dòng)到z上

hanio(n-1,y,x,z);//將y柱上的n-1個(gè)盤子移動(dòng)到z柱上

}}3.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題

問(wèn)題描述給定一個(gè)m×n的迷宮圖、入口與出口、行走規(guī)則。求一條從指定入口到出口的路徑。

所求路徑必須是簡(jiǎn)單路徑，即路徑不重復(fù)。3.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題

行走規(guī)則：上、下、左、右相鄰方塊行走。其中（x，y）表示一個(gè)方塊方位0方位2方位1方位3x，yx-1，yx，y+1x，y-1x+1，y3.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題0123456789入口出口

例如，m=8，n=8，圖中的每個(gè)方塊，用空白表示通道，用陰影表示障礙物。為了算法方便，一般在迷宮外圍加上了一條圍墻。一條迷宮路徑012

3

45

67893.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題設(shè)置一個(gè)迷宮數(shù)組maze[m][n]，其中每個(gè)元素表示一個(gè)方塊的狀態(tài)，為0時(shí)表示對(duì)應(yīng)方塊是通道，為1時(shí)表示對(duì)應(yīng)方塊不可走。

數(shù)據(jù)組織3.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題intmaze[m+2][n+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};01234567890123456789m×n3.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題在算法中用到的棧采用順序棧存儲(chǔ)結(jié)構(gòu)，即將棧聲明為：typedefstruct{intx; //當(dāng)前方塊的行號(hào)inty; //當(dāng)前方塊的列號(hào)intd; //d是下一可走相鄰方位的方位號(hào)}SelemType; typedefstruct//定義move數(shù)組{intx，y;}move[4]; //聲明順序棧類型x，yi，jd3.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題試探順序：從方位0開始，順時(shí)針?lè)较蚍轿?方位2方位1方位3x，yx-1，yx，y+1x，y-1x+1，y

算法設(shè)計(jì)用棧求解迷宮問(wèn)題3.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題x，yxydxy-1棧將（x，y，-1）進(jìn)棧初始時(shí)，入口（x，y）作為當(dāng)前方塊。所有走過(guò)的方塊都會(huì)進(jìn)棧！3.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題如果一個(gè)當(dāng)前方塊（x，y）找到一個(gè)相鄰可走方塊（i，j），就繼續(xù)從（i，j）走下去。x，yi，j方位dxydxyd棧將（i，j，-1）進(jìn)棧ij-13.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題如果一個(gè)當(dāng)前方塊（x，y）沒(méi)有找到任何相鄰可走方塊，表示此時(shí)無(wú)路可走，將其退棧。i，j××××xydixyd棧將（x，y，d）退棧

3.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題求解迷宮路徑的過(guò)程：前一方塊××當(dāng)前方塊回溯找其他可能的相鄰方塊所有相鄰方塊都不能走3.2棧的應(yīng)用舉例例3.6迷宮問(wèn)題①棧初始化;②將入口點(diǎn)坐標(biāo)及到達(dá)該點(diǎn)的方向（設(shè)為－１）入棧③while(棧不空){棧頂元素彈出到（x,y,d）出棧;求出下一個(gè)要試探的方向d++;while（還有剩余試探方向時(shí)）

{if（d方向可走）則{（x,y,d）入棧;

求新點(diǎn)坐標(biāo)(i,j);將新點(diǎn)（i,j）切換為當(dāng)前點(diǎn)（x,y）;if((x,ｙ)==(ｍ,n))結(jié)束;else重置d=0;}elsed++;}}隊(duì)列3.33.3.1隊(duì)列的定義及ADT定義

隊(duì)列簡(jiǎn)稱隊(duì)，它也是一種運(yùn)算受限的線性表。隊(duì)列只能選取一個(gè)端點(diǎn)進(jìn)行插入操作，另一個(gè)端點(diǎn)進(jìn)行刪除操作端點(diǎn)1端點(diǎn)2線性表3.3.1隊(duì)列的定義及ADT定義進(jìn)行插入的一端稱做隊(duì)尾（rear）。進(jìn)行刪除的一端稱做隊(duì)首或隊(duì)頭（front）。向隊(duì)列中插入新元素稱為進(jìn)隊(duì)或入隊(duì)，新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素。從隊(duì)列中刪除元素稱為出隊(duì)或離隊(duì)，元素出隊(duì)后，其后繼元素就成為隊(duì)首元素。隊(duì)尾隊(duì)頭隊(duì)列示意圖出隊(duì)進(jìn)隊(duì)隊(duì)列的幾個(gè)概念3.3.1隊(duì)列的定義及ADT定義隊(duì)列的主要特點(diǎn)是先進(jìn)先出，所以又把隊(duì)列稱為先進(jìn)先出表。假如5個(gè)人過(guò)獨(dú)木橋只能按上橋的次序過(guò)橋這里獨(dú)木橋就是一個(gè)隊(duì)列例如：3.3.1隊(duì)列的定義及ADT定義隊(duì)列的基本運(yùn)算如下：

InitQueue(&Q)：初始化隊(duì)列。構(gòu)造一個(gè)空隊(duì)列q。

DestroyQueue(&Q)：銷毀隊(duì)列。釋放隊(duì)列q占用的存儲(chǔ)空間。

QueueEmpty(Q)：判斷隊(duì)列是否為空。若隊(duì)列q為空，則返回真；否則返回假。

enQueue(&Q，e)：進(jìn)隊(duì)列。將元素e進(jìn)隊(duì)作為隊(duì)尾元素。

deQueue(&Q，&e)：出隊(duì)列。從隊(duì)列q中出隊(duì)一個(gè)元素，并將其值賦給e。隊(duì)列抽象數(shù)據(jù)類型＝邏輯結(jié)構(gòu)＋基本運(yùn)算（運(yùn)算描述）3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)隊(duì)列中元素邏輯關(guān)系與線性表的相同，隊(duì)列可以采用與線性表相同的存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)隊(duì)列順序表鏈表順序隊(duì)鏈隊(duì)3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列采用鏈表存儲(chǔ)的隊(duì)列稱為鏈隊(duì)，可以采用帶頭結(jié)點(diǎn)或不帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)。...datnext隊(duì)頭隊(duì)尾Q.reardatanext隊(duì)頭隊(duì)尾Q.front3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列鏈隊(duì)列存儲(chǔ)結(jié)構(gòu)的定義typedefstructQNode{QElemTypedata;structQNode*next;}Qnode,*QueuePointer;typedefstruct{QueuePtrPointer;//隊(duì)頭指針

QueuePtrPointer;//隊(duì)尾指針}LinkQueue;

3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列(a)空隊(duì)列(b)元素x入隊(duì)列(d)元素x出隊(duì)列(c)元素y入隊(duì)列3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列(1)初始化隊(duì)列InitQueue(LinkQueue&Q)StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QNode*)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);

Q.front->next=NULL;returnOK;}3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列(2)入隊(duì)EnQueue(LinkQueue*&Q,QElemTypee)StatusEnQueue(LinkQueue&Q,QElemTypee){p=(QNode*)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}p3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列(3)出隊(duì)DeQueue(LinkQueue&Q,QElemType&e)StatusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;

p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}p3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列(4)判隊(duì)空QueueEmpty(LinkQueueQ)StatusQueueEmpty(LinkQueueQ){return(Q.front==Q.rear);}3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列(5)求隊(duì)列長(zhǎng)度QueueLength(LinkQueueQ)intQueueLength(LinkQueue*Q)//求隊(duì)長(zhǎng)

{p=Q.front;i=0;while(p->next)//訪問(wèn)每個(gè)結(jié)點(diǎn){p=p->next;i++;}//，每經(jīng)過(guò)一個(gè)結(jié)點(diǎn)，計(jì)數(shù)器加1returni;}3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列(6)取隊(duì)首結(jié)點(diǎn)數(shù)據(jù)StatusGetHead(LinkQueueQ,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.front->next->data;returnOK;}3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列(7)清空隊(duì)列ClearQueue(LinkQueue&Q)StatusClearQueue(LinkQueue&Q){p=Q.front->next;//p指向第一結(jié)點(diǎn)

while(p)//逐個(gè)釋放結(jié)點(diǎn)，保留頭結(jié)點(diǎn)

{q=p；p=p->next;free(q);}Q.rear=Q.front;//尾指針指向頭結(jié)點(diǎn)

returnOK;}3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列(8)撤消隊(duì)列DestroyQueue(LinkQueue&Q)StatusDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-鏈隊(duì)列(9)遍歷隊(duì)列QueueTraverse(LinkQueueQ,visit(QElemType))StatusQueueTraverse(LinkQueue*Q,visit(QElemType)

{p=Q.front->next;while(p)//訪問(wèn)每個(gè)結(jié)點(diǎn)

{visit(p->data);p=p->next;}returnOK;}3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-順序隊(duì)列typedefstruct{QElemType*base；

intfront，rear；//隊(duì)首和隊(duì)尾指針}SqQueue;順序隊(duì)類型SqQueue聲明如下：因?yàn)殛?duì)列兩端都在變化，所以需要兩個(gè)指針來(lái)標(biāo)識(shí)隊(duì)列的狀態(tài)。3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-順序隊(duì)列Q.front012345Q.rearQ.frontQ.rearJ1J2J3Q.frontQ.rearJ3Q.frontQ.rearJ5J6front=rear=-1入隊(duì)：base[rear++]=x;出隊(duì)：x=base[++front];3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-順序隊(duì)列Q.frontQ.rearJ5J6Q.front012345J5J6J1J2J3J4設(shè)大小為Mfront=-1rear=M-1時(shí)再入隊(duì)—真溢出front≠-1rear=M-1時(shí)再入隊(duì)—假溢出Q.rear3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-順序隊(duì)列把數(shù)組的前端和后端連接起來(lái)，形成一個(gè)環(huán)形的順序表，即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán)，稱為環(huán)形隊(duì)列或循環(huán)隊(duì)列。01234frontabcrear解決方案3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-順序隊(duì)列01234frontabcdrear實(shí)際上內(nèi)存地址一定是連續(xù)的，不可能是環(huán)形的，這里是通過(guò)邏輯方式實(shí)現(xiàn)環(huán)形隊(duì)列，也就是將rear++和front++改為：rear=(rear+1)%MaxSizefront=(front+1)%MaxSize環(huán)形隊(duì)列（循環(huán)隊(duì)列）：3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-順序隊(duì)列01234frontrear（a）空隊(duì)01234frontabcrear（b）a、b、c進(jìn)隊(duì)01234frontbcrear（c）出隊(duì)一次01234frontrear（d）出隊(duì)2次3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-順序隊(duì)列現(xiàn)在約定rear=front為隊(duì)空，以下三種情況都滿足該條件：01234frontrear01234frontrear初始狀態(tài)進(jìn)隊(duì)的所有元素均出隊(duì)那么如何設(shè)置隊(duì)滿的條件呢？解決方案：1.另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿。2.少用一個(gè)元素空間：隊(duì)空：front==rear

隊(duì)滿：(rear+1)%M==front01234frontrear隊(duì)滿狀態(tài)abcde3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-順序隊(duì)列

隊(duì)空條件：front=rear

隊(duì)滿條件：(rear+1)%MaxSize=front

進(jìn)隊(duì)e操作：rear=(rear+1)%MaxSize;將e放在rear處

出隊(duì)操作：front=(front+1)%MaxSize;取出front處元素e;環(huán)形隊(duì)列的4要素：

在環(huán)形隊(duì)列中，實(shí)現(xiàn)隊(duì)列的基本運(yùn)算算法與非環(huán)形隊(duì)列類似，只是改為上述4要素即可。3.3.1隊(duì)列存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)-順序隊(duì)列循環(huán)隊(duì)列的類型定義#defineMAXQSIZE1024//最大長(zhǎng)度Typedefstruct{QElemType*base;//初始化的動(dòng)態(tài)分配存儲(chǔ)空間

intfront;