第三章棧和隊(duì)列3.1棧3.2隊(duì)列3.3例題解析13.1棧3.1.1棧的基本概念棧：操作受限的一種特殊線性表，限定插入、刪除元素只能在表的一端進(jìn)行，有后進(jìn)先出(LIFO)性。棧頂：元素進(jìn)棧、出棧的一端。棧底：不允許元素進(jìn)出的表的一端?？諚＃簵Ｖ性貍€(gè)數(shù)為0。棧中元素個(gè)數(shù)不能是無(wú)窮多個(gè)。棧中元素的類型必須相同且元素長(zhǎng)度相同。a1a2an棧頂（表尾）棧底bottomtop2[定義在棧結(jié)構(gòu)上的基本運(yùn)算]生成空棧inistack(s)判棧空否函數(shù)empty(s)元素入棧push(s,x)元素出棧函數(shù)pop(s)取棧頂元素函數(shù)gettop(s)33.1.2棧的順序存儲(chǔ)結(jié)構(gòu)以及操作的實(shí)現(xiàn)（1）一個(gè)棧獨(dú)占一組地址連續(xù)的存儲(chǔ)單元[類型定義]數(shù)組(?？臻g)+棧頂指示

CONSTarrmax={棧的最大允許容量}；TYPEsqstktp=RECORDelem:ARRAY[1..arrmax]OFelemtp;top:0..arrmaxEND;

?？諚l件：S.top=0(此時(shí)退棧則下溢)棧滿條件：S.top=arrmax(此時(shí)進(jìn)棧則上溢)topSa1a2…ai12iarrmax4（2）兩個(gè)棧共享一組地址連續(xù)的存儲(chǔ)單元

[類型定義]數(shù)組(?？臻g)+兩個(gè)棧頂指示CONSTm={兩棧的總允許容量}；TYPEdustktp=RECORDelem:ARRAY[1..m]OFelemtp;top:ARRAY[0..1]OF0..m+1END;12mtop[0]top[1]共享區(qū)域53.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以及操作的實(shí)現(xiàn)[類型定義]棧頂指針(鏈?zhǔn)字羔?TYPEpointer=^nodetype;nodetype=RECORDdata:elemtp;next:pointerEND;

linked_stack=pointer;top^?？諚l件：top=nil（不帶頭結(jié)點(diǎn)）top^.next=nil（帶頭結(jié)點(diǎn)）63.1.4棧的應(yīng)用表達(dá)式求值

5+3*(7-2)+11#設(shè)置運(yùn)算符棧和運(yùn)算數(shù)棧數(shù)制轉(zhuǎn)換24510=382+681+580=3658

第一位：Nmod8245mod8=5第二位：245/8=30,30mod8=6

第三位：30/8=3,3mod8=3

第四位：3/8=0,結(jié)束OPTROPND#53(7-2+*51520+11317括號(hào)匹配((2+4)*5-(36/8)#左括號(hào)入棧，右括號(hào)退棧搜索問(wèn)題迷宮探路記錄已走過(guò)的路徑，無(wú)法向下搜索時(shí)，退后一步，搜索向下的其他可能路徑遞歸問(wèn)題83.1.5棧與遞歸過(guò)程[遞歸的含義]

函數(shù)、過(guò)程或者數(shù)據(jù)結(jié)構(gòu)的內(nèi)部又直接或者間接地由自身定義。[遞歸算法的特點(diǎn)]遞歸算法簡(jiǎn)單明了，直觀易懂時(shí)間效率低，空間開(kāi)銷大，算法不易優(yōu)化[適合于應(yīng)用遞歸的場(chǎng)合]規(guī)模較大的問(wèn)題可以化解為規(guī)模較小的問(wèn)題，且二者處理(或定義)的方式一致；當(dāng)問(wèn)題規(guī)模降低到一定程度時(shí)是可以直接求解的(終止條件)例如：階乘函數(shù)，廣義表、二叉樹(shù)操作9[寫(xiě)遞歸算法應(yīng)注意的問(wèn)題]遞歸算法本身不可以作為獨(dú)立的程序運(yùn)行，需在其它的程序中設(shè)置調(diào)用初值，進(jìn)行調(diào)用；遞歸算法應(yīng)有出口(終止條件)例1.求n！n!=1n=0n(n-1)!n>0

FUNCFactorial(n:integer):integer;IFn=0THENreturn(1)ELSEreturn(n*Factorial(n-1))ENDF;{Factorial}

[……Factorial（4）；……]10[遞歸算法的實(shí)現(xiàn)原理]利用棧，棧中每個(gè)元素稱為工作記錄，分成三個(gè)部分：

返回地址實(shí)在參數(shù)表(變參和值參)局部變量發(fā)生調(diào)用時(shí)，保護(hù)現(xiàn)場(chǎng)，即當(dāng)前的工作記錄入棧，然后轉(zhuǎn)入被調(diào)用的過(guò)程一個(gè)調(diào)用結(jié)束時(shí)，恢復(fù)現(xiàn)場(chǎng)，即若棧不空，則退棧，從退出的返回地址處繼續(xù)執(zhí)行下去123s12311[遞歸轉(zhuǎn)換為非遞歸的方法]1）采用迭代算法遞歸—從頂?shù)降椎獜牡椎巾?/p>

例：求n！FUNCfact(n:integer):integer;m:=1;FORi:=1TOnDOm:=m*i;RETURN(m);ENDF;{fact}12[遞歸轉(zhuǎn)換為非遞歸的方法]2）消除尾遞歸例：順序輸出單鏈表中的結(jié)點(diǎn)數(shù)據(jù)PROClinklist_output(p:pointer);IFp<>nilTHEN[write(p^.data);

linklist_output(p^.next)]ENDP;{linklist_output}使用循環(huán)語(yǔ)句：PROClinklist_output2(p:pointer);WHILEp<>nilDO[write(p^.data);p:=p^.next;]ENDP;{linklist_output2}13[遞歸轉(zhuǎn)換為非遞歸的方法]3）利用棧模擬遞歸——通用方法如果是遞歸函數(shù)，需改寫(xiě)為遞歸過(guò)程自設(shè)棧模擬系統(tǒng)工作棧改寫(xiě)算法在程序開(kāi)頭增加棧的初始化語(yǔ)句改寫(xiě)遞歸調(diào)用語(yǔ)句入棧處理；確定調(diào)用的參數(shù)值；轉(zhuǎn)至調(diào)用的開(kāi)始語(yǔ)句改寫(xiě)所有遞歸出口退棧還原參數(shù)；轉(zhuǎn)至返回地址處盡量?jī)?yōu)化14示例求n!PROCfact(n:integer;VARf:integer);0:IFn=0THEN

f:=1ELSE[1:fact(n-1,f);

2:f:=n*f]ENDP;{fact}棧定義：CONSTarrmax=…;TYPEsnode=RECORDrd,n,f:inntegerEND;VARs:ARRAY[1..arrmax]OFsnodeinit_stack(s);IFtop0THEN[s[top].f:=f;{還原本層變參值}top:=top-1;n:=s[top+1].n;f:=s[top+1].f;gotos[top+1].rd]top:=top+1;s[top].rd:=2;

s[top].n:=n;s[top].f:=f;n:=n-1;goto0srdnftop15PROCfact(n:integer;VARf:integer);init_stack(s);0:IFn=0THENf:=1ELSE[1:

top:=top+1;s[top].rd:=2;s[top].n:=n;

s[top].f:=f;n:=n-1;goto0

2:f:=n*f]IFtop0THEN[s[top].f:=f;top:=top-1;n:=s[top+1].n;

f:=s[top+1].f;

gotos[top+1].rd]ENDP;{fact}PROCfact(n:integer;VARf:integer);init_stack(s);WHILEn0DO[top:=top+1;s[top].n:=n;n:=n-1]f:=1;WHILEtop0DO[top:=top-1;n:=s[top+1].n;f:=n*f]ENDP;{fact}注：此時(shí)可確定棧中只存放n值即可。163.2隊(duì)列3.2.1隊(duì)列的基本概念隊(duì)列：操作受限的一種特殊線性表，限定插入、刪除元素分別在表的兩端進(jìn)行，有先進(jìn)先出(LIFO)性。隊(duì)頭：表中元素出隊(duì)的一端。隊(duì)尾：表中元素入隊(duì)的一端?？贞?duì)列：隊(duì)列中元素個(gè)數(shù)為0。隊(duì)列中元素個(gè)數(shù)不能是無(wú)窮多個(gè)。隊(duì)列中元素的類型必須相同，且元素長(zhǎng)度相同。a1a2…ai…an

隊(duì)頭f隊(duì)尾r出隊(duì)列入隊(duì)列17[定義在隊(duì)列結(jié)構(gòu)上的基本運(yùn)算]構(gòu)造空隊(duì)列iniqueue(q)判隊(duì)空否函數(shù)empty(q)元素入隊(duì)enqueue(q,x)元素出隊(duì)函數(shù)dlqueue(q)取隊(duì)頭元素函數(shù)gethead(q)求隊(duì)長(zhǎng)函數(shù)current_size(q)183.2.2隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以及操作的實(shí)現(xiàn)[類型定義]隊(duì)頭指針+隊(duì)尾指針

TYPEqueueptr=^queuenode;queuenode=RECORDdata:elemtp;next:queueptrEND;

linkedquetp=RECORDf,r:queueptrEND;datanext^q.fq.r隊(duì)頭隊(duì)尾隊(duì)空條件：q.f=q.r193.2.3循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)以及操作的實(shí)現(xiàn)[一般用法的順序存儲(chǔ)結(jié)構(gòu)之缺陷]

出隊(duì)列操作后大量移動(dòng)數(shù)據(jù)或存在“假上溢”現(xiàn)象。[解決方法]

循環(huán)隊(duì)列[類型定義]數(shù)組(隊(duì)列空間)+頭指針+尾指針CONSTm={隊(duì)列的最大容量};TYPEcyclicquetp=RECORDelem:ARRAY[1..m]OFelemtp;r,f:0..mEND;

1

mfr20

隊(duì)列控制方法：規(guī)定f指向隊(duì)頭元素的前一位置，并且該單元不使用。隊(duì)空條件：f=r隊(duì)滿條件：(rmodm)+1=f

指針后移時(shí)的取值：i=(imodm)+112mm-1fr21[循環(huán)隊(duì)列的其它控制方法]另設(shè)置標(biāo)志信號(hào)flag，flag=0表示空，flag=1表示滿。只使用一個(gè)指針f和元素個(gè)數(shù)size，則可用size的值來(lái)判斷隊(duì)列的滿和空。223.3例題解析選擇題1.一個(gè)棧的入棧序列是a,b,c,d,e，則不可能的輸出序列是（）。AedcbaBdecbaCdceabDabcde2.若已知一個(gè)棧的入棧序列是1,2,3,...,n，若其輸出序列的第一個(gè)值是n，則輸出序列的第i個(gè)值是（）。AiBn-i

Cn-i+1D不確定3.隊(duì)列結(jié)構(gòu)的元素個(gè)數(shù)是（）。A不變的B可變的C任意的D04.判定一個(gè)循環(huán)隊(duì)列Q(最多元素為m)為滿隊(duì)列的條件是（）。AQ.f=Q.rBQ.fQ.rCQ.f=(Q.r+1)MODmDQ.f=(Q.rMODm)+1

少用一個(gè)空間方案（若空間從0起？C）23填空題1.已知順序棧s，在進(jìn)棧操作前要判斷（棧滿否），出棧操作前要判斷（?？辗瘢?。2.對(duì)于帶頭結(jié)點(diǎn)的鏈棧ls，指向棧頂元素的指針是（ls^.next）。3.鏈棧的棧頂元素安排在鏈表的首元結(jié)點(diǎn)，原因是（進(jìn)棧、出棧方便）。4.設(shè)a是含有n個(gè)分量的整數(shù)數(shù)組，寫(xiě)出一個(gè)求n個(gè)整數(shù)的平均值的遞歸定義（）。

f(n)=a[1]n=1遞歸出口((n-1)*f(n-1)+a[n])/nn>1遞歸體

f(n)=(a[1]+a[2]+...+a[n])/n24判斷題1.消除遞歸必須使用棧。2.(北郵2002)棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到一些限制。25應(yīng)用題1.(北郵2001)試推導(dǎo)出總盤(pán)數(shù)為n時(shí)的Hanoi塔的移動(dòng)次數(shù)。[解]M(n)=2M(n-1)+1=4M(n-2)+3=8M(n-3)+7=2iM(n-i)+2i-1=2n-126算法題1.假設(shè)用一個(gè)循環(huán)單鏈表表示隊(duì)列，該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針r，不設(shè)隊(duì)首指針，完成下列算法：（1）初始化（2）插入（3）刪除（4）求隊(duì)長(zhǎng)2.借助棧將輸入的任意一個(gè)非負(fù)的十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制。PROCcoversion();init_stack(s);read(n);WHILE(n0)DO[push(s,nMOD8);n:=n/8]WHILE(NOT(empty_stack(s))DO[x:=pop(s);write(x)]ENDP;{coversion}273.利用兩個(gè)棧s1和s2模擬一個(gè)隊(duì)列，實(shí)現(xiàn)隊(duì)列的下述算法：（1）初始化（2）插入（3）刪除（4）判空[分析]以s1存儲(chǔ)隊(duì)列元素（1）初始化：s1.top:=0;s2^.top:=0;（2）插入：相當(dāng)于s1的入棧（3）刪除：將s1的元素逐個(gè)出棧并進(jìn)s2棧，出隊(duì)即s2出棧，再將s2的元素逐個(gè)出棧并進(jìn)s1棧；（4）判空：相當(dāng)于判斷棧s1空否284.假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間，見(jiàn)圖，其類型Queue2定義如下：

typeQueue2=RECORDdata:ARRAY[1..MaxSize]OFdatatp;front,rear:ARRAY[0..1]OFintegerEND;請(qǐng)對(duì)以下算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。

FUNCEnQueue(VARQ:Queue2,i:integer,x:datatp):integer;if(i<0ORi>1)return(0);if(Q^.rear[i]==Q^.front[(i+1)mod2])return0;Q^.data[Q^.rear[i]]=x;Q^.rear[i]=(Q^.rear[i]modMaxSize)+1;return(1);ENDF;