算法與數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列

第三章棧和隊(duì)列陳守孔講授開始學(xué)習(xí)本章前要掌握：從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列仍屬于線性結(jié)構(gòu)，具有線性結(jié)構(gòu)的共同特征；學(xué)習(xí)本章時(shí)，要注意到棧和隊(duì)列所具有的線性結(jié)構(gòu)的共性，更要掌握其個(gè)性；棧和隊(duì)列是操作受限的線性結(jié)構(gòu)；本章具體內(nèi)容見本章目錄。本章目錄3.1棧

3.1.1棧的類型定義3.1.2棧的表示和實(shí)現(xiàn)

3.2棧的應(yīng)用舉例3.3棧與遞歸3.3.1如何實(shí)現(xiàn)遞歸3.3.2采用遞歸算法解決的問(wèn)題

3.3.3將遞歸轉(zhuǎn)換為非遞歸3.4隊(duì)列

3.4.1隊(duì)列的類型定義3.4.2循環(huán)隊(duì)列－隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

3.4.3鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)*3.5算法設(shè)計(jì)舉例主要內(nèi)容知識(shí)點(diǎn)棧與隊(duì)列的特征棧與遞歸循環(huán)隊(duì)列重點(diǎn)難點(diǎn)棧的操作遞歸循環(huán)隊(duì)列棧與隊(duì)列的綜合應(yīng)用?！睸tatck〕的定義棧是操作受限制的線性表定義：僅在表尾進(jìn)行插入或刪除操作的線性表；概念：棧頂：在棧頂操作，是表尾，通常用top表示；棧底：bottom，是表頭；空棧:空表；通常棧底固定，棧頂移動(dòng)。棧示意圖a1a2a3an…棧頂top棧底bottom表頭表尾操作原那么：后進(jìn)先出〔LastInFirstOut〕,LIFO舉例：餐館的盤子

棧的抽象數(shù)據(jù)類型定義ADTStack{數(shù)據(jù)對(duì)象：D={ai|aiElemSet,i=1,2,...,n，n>=0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,aiD,i=2,...,n}根本操作:棧初始化：StackInit()判?？眨篠tackEmpty(S)入棧：Push(S，x)出棧：Pop(S)取棧頂元素：StackGetTop(S)清空棧：StackClear(S)求棧長(zhǎng)：StackLength(S)}ADTStack棧的表示和實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)：順序棧；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈棧；

順序棧利用一組地址連續(xù)的存儲(chǔ)單元依次自棧底到棧頂存放棧的數(shù)據(jù)元素。在數(shù)組上實(shí)現(xiàn)時(shí)，棧底位置可以設(shè)置在數(shù)組的任一個(gè)端點(diǎn)，而棧頂是隨著插入和刪除而變化的，可以用一個(gè)整形變量top存放棧頂?shù)闹羔?，?shù)據(jù)入棧或出棧時(shí)使整形變量top分別加1或減1。

順序棧的類型定義#defineMAXSIZE1024typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack；用順序棧實(shí)現(xiàn)棧的運(yùn)算(1)SeqStackSeqStackInit(){//構(gòu)造一個(gè)空棧SSeqStackS；S.top=-1;returnS;}初始化用順序棧實(shí)現(xiàn)棧的運(yùn)算(2)intSeqStackEmpty(SeqStackS){//判斷棧S是否為空if(S.top==-1)returnTRUE;elsereturnFALSE;}判?？?/p>

用順序棧實(shí)現(xiàn)棧的運(yùn)算(3)voidSeqStackPush(SeqStackS,ElemTypex){//插入元素x為新的棧頂元素if(S.top==MAXSIZE-1) {printf(“Overflow〞);exit(0);}//棧滿，退出運(yùn)行S.top++; S.data[S.top]=x;}入棧

用順序棧實(shí)現(xiàn)棧的運(yùn)算(4)ElemTypeSeqStackPop(SeqStackS){//假設(shè)棧S不空，刪除S的棧頂元素，并返回其值if(S.top==-1)//棧已空，退出運(yùn)行{printf(“Empty\n〞);exit(0);}x=S.data[S.top];S.top--;returnx;}出棧

用順序棧實(shí)現(xiàn)棧的運(yùn)算(5)ElemTypeSeqStackGetTop(SeqStackS){if(S.top==-1){printf(“?？?\n〞);exit(0);}elsereturn(S.data[S.top]);}取棧頂元素

雙向棧棧1底棧2底棧1棧2…兩個(gè)棧共享一個(gè)向量空間，棧底分別設(shè)在兩端，寫出進(jìn)棧和退棧操作雙向棧的類型定義#definem64typedefstruct{ElemTypedata[m];inttop[2];//top[0],top[1]分別是兩個(gè)棧的棧頂指針}TStack;初始化時(shí)，top[0]=-1和top[1]=m表示?？眨瑮ｍ斚嘤鰰r(shí)表示棧滿，入棧時(shí)棧頂指針相向移動(dòng)。鏈棧用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧稱為鏈棧。通常鏈?？捎脝捂湵肀硎?，因此其結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同。

鏈棧結(jié)點(diǎn)的類型描述：typedefstructStackNode{ElemTypedata;structStackNode*next;}StackNode，*LinkedStack;由于棧只在棧頂操作，因此，通常不設(shè)頭結(jié)點(diǎn)。鏈棧圖示top

∧

用鏈棧實(shí)現(xiàn)棧的運(yùn)算(1)LinkedStackLinkedStackInit〔〕{//構(gòu)造一個(gè)空棧，棧頂指針為topLinkedStacktop;top=NULL;returntop;}鏈棧的初始化用鏈棧實(shí)現(xiàn)棧的運(yùn)算(2)intLinkedStackEmpty(LinkedStacktop〕{//判定棧S是否是空棧if〔top==NULL〕returnTRUE;elsereturnFALSE;}判?？沼面湕?shí)現(xiàn)棧的運(yùn)算(3)LinkedStackPush(LinkedStacktop,ElemTypex〕//插入元素x為新的棧頂元素，鏈棧用棧頂指針top表示{s=(LinkedStack)malloc(sizeof(StackNode));//創(chuàng)立一個(gè)新結(jié)點(diǎn)s->data=x; //設(shè)置新結(jié)點(diǎn)的數(shù)據(jù)域s->next=top; //設(shè)置新結(jié)點(diǎn)的指針域top=s; //設(shè)置新棧頂指針returntop;}入棧

用鏈棧實(shí)現(xiàn)棧的運(yùn)算(4)ElemTypePop(LinkedStacktop){//假設(shè)棧S不空，那么刪除S的棧頂元素，并返回其值if〔top！=NULL〕{x=top->data; p=top;top=top->next;free(p);returnx;}else{printf(“棧空\(chéng)n〞);exit(0);}}退棧

自測(cè)題設(shè)棧的輸入序列是1，2，3，4,那么〔〕不可能是其出棧序列。A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，2E.3，2，1，4，【煙臺(tái)大學(xué)2007一.4(2分)】D自測(cè)題設(shè)輸入元素為1、2、3、P和A，輸入次序?yàn)?23PA，如圖〔編者略〕。元素經(jīng)過(guò)棧后達(dá)輸出序列，當(dāng)所有元素均到達(dá)輸出序列后，有哪些序列可以作為高級(jí)語(yǔ)言的變量名?！局猩酱髮W(xué)1997】PA321P3A21P32A1P321AAP321自測(cè)題1．假設(shè)元素a，b，c，d，e，f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧操作，那么不可能得到的出棧序列是A.d,c,e,b,f,aB.c,b,d,a,e,fC.b,c,a,e,f,dD.a,f,e,d,c,b【2010年全國(guó)碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)根底綜合】D棧的應(yīng)用棧與過(guò)程調(diào)用表達(dá)式求值棧與遞歸過(guò)程棧與過(guò)程調(diào)用過(guò)程的嵌套調(diào)用圖示：算法舉例3.1棧的應(yīng)用:數(shù)制轉(zhuǎn)換把十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)。N=(N/d)*d+Nmodd;例如:(1348)10=(2504)81348/8=168, 1348%8=4 最低位168/8=21, 168%8=021/8=2, 21%8=52/8=0, 2%8=2 最高位(1348)10=1*103+3*102+4*101+8*100;(2504)8=2*83+5*82+0*81+4*80;數(shù)制轉(zhuǎn)換的非遞歸算法voidconversion(){//把十進(jìn)制轉(zhuǎn)換為八進(jìn)制 InitStack(S); scanf(“%d〞,&N); while(N) {Push(S,N%8); N=N/8;} while(!StackEmpty(S)) {Pop(S,e);printf(“%d〞,e); }}數(shù)制轉(zhuǎn)換的遞歸算法voidConvert(intn){//把十進(jìn)制n轉(zhuǎn)換為八進(jìn)制if(n!=0) {Convert(n/8);printf(“%d〞,n%8); }}算法舉例3.2:中綴表達(dá)式的求值算術(shù)表達(dá)式中運(yùn)算符(+,-,*,/等)的優(yōu)先規(guī)那么設(shè)置兩個(gè)工作棧：運(yùn)算符棧S1和操作數(shù)棧S2。S2存放表達(dá)式的運(yùn)算結(jié)果。算法思想：1首先置操作數(shù)棧S2為空棧，置運(yùn)算符棧的棧底為表達(dá)式的起始符#(優(yōu)先級(jí)最低)。2依次讀入表達(dá)式的每個(gè)字符ch,直至表達(dá)式結(jié)束：假設(shè)ch是操作數(shù),那么進(jìn)S2棧；假設(shè)ch是運(yùn)算符，假設(shè)其優(yōu)先級(jí)不高于棧頂運(yùn)算符的優(yōu)先級(jí)時(shí)，那么取出棧S2的棧頂和次棧頂?shù)膬蓚€(gè)元素以及棧S1的棧頂運(yùn)算符，進(jìn)行相應(yīng)的運(yùn)算，并將結(jié)果放入棧S2中；如此下去，直至ch的優(yōu)先級(jí)高于棧頂運(yùn)算符的優(yōu)先級(jí)，將ch入S1棧。舉例:3*(5-2)步驟optr棧S1opnd棧S2輸入字符主要操作

－－－－－－－－－－－－－－－－－－－－－－－－－－1#3*(5-2)#push(s2,’3’)2#3*(5-2)#push(s1,’*’)3#*3(5-2)#push(s1,’(’)4#*(35-2)#push(s2,’5’)5#*(35-2)#push(s1,’-’)6#*(-352)#push(s2,’2’)7#*(-352)#operate(‘5’,’-’,’2’)8#*(33)#pop(s1){消除一對(duì)括號(hào)}9#*33#operate(‘3’,’*’,’3’)10#9#return(gettop(s2))中綴表達(dá)式求值算法ElemTypeEvalExpression(){charch,opnd[maxch],optr[maxch];//opnd是運(yùn)算數(shù)棧,optr是運(yùn)算符棧init(optr);push(optr,‘#’);init(opnd);ch=getchar();while(ch!=‘#’||gettop(optr)!=‘#’)if(!in(ch,op)){push(opnd,ch);ch=getchar();}//不是運(yùn)算符就進(jìn)棧elseswitch(precede(gettop(optr),ch)){case‘<’://棧頂元素優(yōu)先級(jí)低push(optr,ch);ch=getchar();break;case‘=’://脫括號(hào)并接收下一字符pop(optr,x);ch=getchar();break;case‘>’://退棧并將運(yùn)算結(jié)果入棧pop(optr,theta);pop(opnd,b);pop(opnd,a);push(opnd,operate(a,theta,b));break;}//switchreturngettop(opnd);}中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式概念：前綴表達(dá)式，中綴表達(dá)式，后綴表達(dá)式+ab,a+b,ab+〔1〕中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式設(shè)中綴表達(dá)式和后綴表達(dá)式分別在向量IFX和PFX申，用棧S實(shí)現(xiàn)中綴式轉(zhuǎn)為后綴式，對(duì)IFX中表達(dá)式從左到右掃描，設(shè)TOKEN是掃描讀到的符號(hào)，轉(zhuǎn)換算法可描述如下：棧初始化從左到右掃描向量IFX，重復(fù)下述兩步操作，直到表達(dá)式尾：①?gòu)腎PX中取出下個(gè)TOKEN(數(shù)字、運(yùn)算符、左括號(hào)、右括號(hào))；②CASETOKENOF‘(’：將TOKEN壓入棧S;‘)’：退棧并將退棧元素送PFX，直到碰到左括號(hào)，左括號(hào)退棧不送PFX。操作數(shù)：將操作數(shù)直接送入PFX;操作符：如?？栈騎OKEN比棧頂元素優(yōu)先級(jí)高，將TOKEN進(jìn)棧；否那么，退棧并將退棧元素送入PFX，然后再將TOKEN與新棧頂元素比較之;當(dāng)遇到中綴表達(dá)式結(jié)束符號(hào)，連續(xù)退棧并送退棧元素到PFX，直至?？?。舉例：將中綴表達(dá)式

8-(3+5)*(5-6/2〕

轉(zhuǎn)為后綴表達(dá)式表達(dá)式轉(zhuǎn)換的簡(jiǎn)單方法中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式有三步：〔1〕加括號(hào)：將中綴表達(dá)式中所有的子表達(dá)式按計(jì)算規(guī)那么用嵌套括號(hào)括起來(lái)；〔2〕移運(yùn)算符：順序?qū)⒚繉?duì)括號(hào)中的運(yùn)算符移到相應(yīng)括號(hào)的后面；〔3〕刪括號(hào)：刪除所有括號(hào)。例如，將中綴表達(dá)式8-(3+5)*(5-6/2〕轉(zhuǎn)為后綴表達(dá)式。按如上步驟：執(zhí)行完上面第一步后為：(8-((3+5)*(5-(6/2))))；執(zhí)行完上面第二步后為：(8((35)+(5(62)/)-)*)-；執(zhí)行完上面第三步后為：835+562/-*-?？捎妙愃品椒▽⒅芯Y表達(dá)式轉(zhuǎn)為前綴表達(dá)式。后綴表達(dá)式求值〔2〕對(duì)后綴表達(dá)式求值用實(shí)型數(shù)棧S存放計(jì)算后綴式的中間及最終結(jié)果，求值算法可描述如下。棧初始化。從左到右掃描向量PFX，重復(fù)下述兩步操作，直到表達(dá)式尾。①?gòu)腜FX中取出下個(gè)TOKEN(操作數(shù)、運(yùn)算符)②CASETOKENOF操作數(shù)：將操作數(shù)直接送入棧S1;操作符：出棧兩個(gè)操作數(shù)，對(duì)其進(jìn)行TOKEN操作，結(jié)果壓人棧S1當(dāng)遇到后綴表達(dá)式結(jié)束符號(hào)，棧頂?shù)闹稻褪墙Y(jié)果(應(yīng)是棧中唯一元素)。后綴表達(dá)式求值舉例中綴表達(dá)式：8-(3+5)*(5-6/2〕后綴表達(dá)式：835+562/-*-對(duì)后綴表達(dá)式求值835+562/-*-

算法舉例3.3后綴表達(dá)式求值

詳見教材算法3.31－－3.34自測(cè)題中綴表達(dá)式〔A+B〕*〔C-D〕/(E-F*G)的后綴表達(dá)式是_____；A.A+B*C-D/E-F*GB.AB+CD-*EFG*-/C.AB+C*D-E/F-G*D.ABCDEFG+*-/-*【北京郵電大學(xué)2005一.2(2分)】B棧與遞歸過(guò)程遞歸：假設(shè)在一個(gè)函數(shù)、過(guò)程或者數(shù)據(jù)結(jié)構(gòu)定義的內(nèi)部，直接〔或間接〕出現(xiàn)定義本身的應(yīng)用，那么稱它們是遞歸的，或者是遞歸定義的。遞歸過(guò)程的應(yīng)用：?jiǎn)栴}的定義是遞歸的：f(n)=n*f(n-1)數(shù)據(jù)結(jié)構(gòu)是遞歸的：鏈表問(wèn)題的解法是遞歸的：Hanoi塔問(wèn)題“遞歸工作棧〞——棧頂為“工作記錄〞，包括參數(shù)、局部變量以及上一層的返回地址遞歸過(guò)程的應(yīng)用〔1〕〔1〕問(wèn)題的定義是遞歸的：求n的階乘n!longFact(intn){if(n==0)return(1);elsereturn(n*Fact(n-1));}求階乘(n!)過(guò)程的模擬n=3fac(3)n=2F=3*fac(2)n=1F=2*fac(1)n=0F=1*fac(0)fac(0)returnfac(3)=3*2*1returnfac(2)=2*1returnfac(1)=1*1returnfac(0)=1遞歸過(guò)程的應(yīng)用〔2〕〔2〕數(shù)據(jù)結(jié)構(gòu)是遞歸的：逆序打印無(wú)頭結(jié)點(diǎn)單鏈表中各結(jié)點(diǎn)的值。voidprint(LinkedListhead){if(head!=null){print(head->next);printf(“%d〞,head->data);//設(shè)元素為整型}}遞歸過(guò)程的應(yīng)用〔3〕(3)問(wèn)題的解法是遞歸的：Hanoi塔問(wèn)題遞歸過(guò)程的應(yīng)用〔3〕n階Hanoi塔問(wèn)題：假設(shè)有三個(gè)分別命名為X,Y,Z的塔座，在X塔座上插有n個(gè)直徑大小各不相同，依小到大編號(hào)為1，2，…,n的圓盤，要求：把X上的n個(gè)圓盤移到Z上，排列順序相同，移動(dòng)規(guī)那么為：每次只能移動(dòng)一個(gè)園盤；園盤可以在任一塔上做屢次移動(dòng)；在任何時(shí)刻，大盤不能壓在小盤的上面。XYZ用遞歸實(shí)現(xiàn)Hanoi的算法思想使用數(shù)學(xué)歸納法：n=1,OK;設(shè)n=k時(shí)，假設(shè)可以以Y為輔助塔，把k個(gè)盤從X移動(dòng)到Z;當(dāng)n=k+1時(shí)，方法：把X中k個(gè)盤，以Z為輔助塔，移動(dòng)到Y(jié);把X中第k+1個(gè)盤，移動(dòng)到Z;把Y中k個(gè)盤，以X為輔助塔，移動(dòng)到Z;用遞歸實(shí)現(xiàn)Hanoi的算法voidHanoi(intn,charx,chary,charz){ if(n==1) move(x,1,z); //把1號(hào)盤，從x移到z else {Hanoi(n–1,x,z,y);//把n-1個(gè)盤從x移到y(tǒng)，z為輔助塔 move(x,n,z); //把n號(hào)盤，從x移到z Hanoi(n–1,y,x,z);//把n-1個(gè)盤從y移到z，x為輔助塔 }}Hanoi塔算法的模擬H(3,a,b,c)H(1,c,a,b)H(2,a,c,b)H(1,a,b,c)a

ca

bc

ba

cH(2,b,a,c)H(1,b,c,a)b

ab

cH(1,a,b,c)a

cn=1n=2n=3遞歸算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：遞歸過(guò)程結(jié)構(gòu)清晰程序易讀正確性容易證明

缺點(diǎn)：時(shí)間效率低空間開銷大算法不容易優(yōu)化對(duì)于頻繁使用的算法，或不具備遞歸功能的程序設(shè)計(jì)語(yǔ)言，需要把遞歸算法轉(zhuǎn)換為非遞歸算法。遞歸算法轉(zhuǎn)換為非遞歸算法有如下方法：采用迭代算法尾遞歸的消除利用棧消除任何遞歸將遞歸轉(zhuǎn)換為非遞歸

采用迭代算法longFact2(intn){∥用迭代算法求n!x=1;for(i=1;i<=n;i++)x*=i;returnx;}∥Fact2遞歸從頂?shù)降譶!(n-1)!(n-2)!...2!1!0!迭代從底到頂

將遞歸轉(zhuǎn)換成迭代使用尾遞歸的算法遞歸算法voidOutput1(LinkedListL){∥順序輸出單鏈表結(jié)點(diǎn)數(shù)據(jù)的遞歸算法if(L){printf(L->data);∥輸出結(jié)點(diǎn)的值

Output1(L->next);∥尾遞歸調(diào)用}}∥Output1尾遞歸的消除〔1〕非遞歸算法voidOutput2(LinkedListL){∥順序輸出單鏈表結(jié)點(diǎn)數(shù)據(jù)的非遞歸算法一p=L;∥設(shè)局部變量p=LLbl:∥在第一個(gè)可執(zhí)行語(yǔ)句前設(shè)標(biāo)號(hào)if(p){printf(p->data);∥輸出結(jié)點(diǎn)的值p=p->next;∥修改變量值gotoLb1;∥轉(zhuǎn)到第一個(gè)可執(zhí)行語(yǔ)句}}∥Output2尾遞歸的消除〔2〕voidOutput3(LinkedListL){∥順序輸出單鏈表結(jié)點(diǎn)數(shù)據(jù)的非遞歸算法二p=L;∥設(shè)局部變量p=Lwhile(p){printf(p->data);∥輸出結(jié)點(diǎn)的值p=p->next;∥向里一層修改變量值}}∥Output3非遞歸算法利用棧消除任何遞歸〔1〕利用棧可以將任何遞歸函數(shù)轉(zhuǎn)換成非遞歸的形式，其步驟大致如下：入棧處理設(shè)一個(gè)工作棧代替遞歸函數(shù)中的棧，棧中每個(gè)記錄包括函數(shù)的所有參數(shù)：函數(shù)名、局部變量和返回地址。所有遞歸調(diào)用語(yǔ)句處，改寫成把形參、局部變量和返回地址入棧的語(yǔ)句。修改確定本次遞歸調(diào)用時(shí)的實(shí)在參數(shù)之新值。轉(zhuǎn)到函數(shù)的第一個(gè)語(yǔ)句?！厕D(zhuǎn)下頁(yè)〕利用棧消除任何遞歸〔2〕〔接上頁(yè)〕退棧處理假設(shè)?？?，算法結(jié)束，執(zhí)行正常返回。假設(shè)棧不空，從棧中退出參變量賦給原來(lái)入棧時(shí)相對(duì)應(yīng)的參變量，并退出返回地址。轉(zhuǎn)到執(zhí)行返回地址處的語(yǔ)句，繼續(xù)執(zhí)行。算法舉例3.4棧的應(yīng)用回文指正讀和反讀都相同的字符序列，寫一算法判斷含給定的字符串是否是回文。intsympthy(charstr[],chars[]){inti=0,j,n;while(str[i]!=‘\0’)i++;//查字符個(gè)數(shù)n=i;for(i=0;i<n/2;i++)s[i]=str[i];//前一半字符入棧j=i-1;if(n%2==1)i++;//n為奇數(shù)時(shí)中間字符不用比較while(i<n&&str[i]==s[j])//比較字符串是否是回文{i++;j--;}if(i==n)printf(“字符串是回文\n〞)；elseprintf(“字符串不是回文\n〞)；}隊(duì)列(Queue)定義和概念隊(duì)列：隊(duì)列是一種只允許在表的一端插入，在另一端刪除的存取受限的線性表。

概念：隊(duì)尾rear：插入端，線性表的表尾。隊(duì)頭front：刪除端，線性表的表頭。隊(duì)列(Queue)圖示FIFO〔FirstInFirstOut〕〔先進(jìn)先出表〕a1a2a3an-1出隊(duì)列入隊(duì)列隊(duì)頭隊(duì)尾……隊(duì)列的抽象數(shù)據(jù)類型ADTQueue{數(shù)據(jù)對(duì)象：D={ai|aiElemSet，i=1，2，...，n，n>=0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,aiD,i=2,...,n}根本操作：隊(duì)列初始化：QueueInit()入隊(duì)：QueueIn(Q,x)出隊(duì)：QueueOut(Q)讀隊(duì)頭元素： QueueGetHead(Q)判隊(duì)空：QueueEmpty(Q)求隊(duì)列長(zhǎng)：QueueLength(Q)}ADTQueue隊(duì)列的表示和實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)：循環(huán)隊(duì)列；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈隊(duì)列；隊(duì)列的順序表示和實(shí)現(xiàn)frontJ1J2J3J4frontrearJ1J2J3J4frontrearfrontrearJ1frontrear問(wèn)題：如何解決“假上溢〞現(xiàn)象?J1J2J3J4J6J5rear543210543210約定隊(duì)頭指針指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針指向隊(duì)尾元素隊(duì)列的順序表示和實(shí)現(xiàn)循環(huán)隊(duì)列：循環(huán)隊(duì)列操作示意圖循環(huán)隊(duì)列空隊(duì)列條件：Q.rear=Q.front;滿隊(duì)列條件：Q.rear=Q.front;問(wèn)題：如何區(qū)別隊(duì)空和隊(duì)滿有三種方法1.犧牲一個(gè)存儲(chǔ)空間2.引入一個(gè)標(biāo)志變量區(qū)別空和不空3.使用計(jì)數(shù)器循環(huán)隊(duì)列類型定義#defineMAXSIZE256typedefstruct{ElemTypedata[MAXSIZE];//

數(shù)據(jù)的存儲(chǔ)區(qū)intfront,rear;//隊(duì)頭隊(duì)尾指針}SeQueue;//循環(huán)隊(duì)循環(huán)隊(duì)列的初始化SeQueueSeQueueInit(){SeQueueQ;

Q.front=Q.rear=0;returnQ;}

循環(huán)隊(duì)列的入隊(duì)voidSeQueueIn(SeQueueQ,ElemTypex){if((Q.rear+1)%MAXSIZE==Q.front) {printf(“Full\n〞);exit(0); //隊(duì)列滿,退出運(yùn)行 }Q.rear=(Q.rear+1)%MAXSIZE;Q.data[Q.rear]=x;}循環(huán)隊(duì)列的出隊(duì)ElemTypeSeQueueOut(SeQueueQ){if(Q.front==Q.rear){printf(“Empty\n〞);exit(0); //隊(duì)已空,退出運(yùn)行 }Q.front=(Q.front+1)%MAXSIZE;x=Q.data[Q.front];//讀出隊(duì)頭元素returnx;//出隊(duì)完成}循環(huán)隊(duì)列的判空intSeQueueEmpty(SeQueueQ){if(Q.front==Q.rear)returntrue;elsereturnfalse;}求隊(duì)中元素個(gè)數(shù)intSeQueueLength(SeQueueQ){∥返回隊(duì)列Q的元素個(gè)數(shù)

return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;}鏈隊(duì)列用鏈表表示的隊(duì)列簡(jiǎn)稱為鏈隊(duì)列。為便于操作，一個(gè)鏈隊(duì)列需要分別指示隊(duì)頭和隊(duì)尾的兩個(gè)指針。

…a2rearfronta1an∧鏈隊(duì)示意圖(a)非空隊(duì)frontreara1an∧

…a2Q(b)空隊(duì)rearfrontQ

∧

(c)鏈隊(duì)中只有一個(gè)元素結(jié)點(diǎn)frontrearQa1∧

鏈隊(duì)列的類型描述

typedefstructLQNode{ElemTypedata;structLQNode*next;}LQNode,*LinkedQNode;//鏈隊(duì)結(jié)點(diǎn)的類型及指針

typedefstruct{StructLQNode*front,*rear;}LQueue,*LinkedQueue;//將頭尾指針?lè)庋b在一起的鏈隊(duì)鏈隊(duì)列的初始化創(chuàng)立一個(gè)帶頭結(jié)點(diǎn)的空隊(duì)LinkedQueueLinkedQueueInit(){Q=(LinkedQueue)malloc(sizeof(LQueue));//申請(qǐng)頭尾指針結(jié)點(diǎn)p=(LinkedQNode)malloc(sizeof(LQNode));

//申請(qǐng)鏈隊(duì)頭結(jié)點(diǎn)p->next=NULL;Q->front=Q->rear=p;returnQ;}

鏈隊(duì)列的入隊(duì)voidLinkedQueueIn(LinkedQueueQ,ElemTypex){p=(LinkedQNode)malloc(sizeof(LQNode));p->data=x;p->next=Q->rear->next;//或p->next=NULL;Q->rear->next=p;Q->rear=p;}鏈隊(duì)列的判空intLinkedQueueEmpty(LinkedQueueQ){if(Q->front==Q->rear)returntrue;elsereturnfalse;}

鏈隊(duì)列的出隊(duì)出隊(duì)

LinkedQueueOut(LinkedQueueQ){if(!LinkedQueueEmpty(Q)){p=Q->front->next;//隊(duì)列帶頭結(jié)點(diǎn)Q->front->next=p->next;x=p->data;//隊(duì)頭元素放x中

if(p==Q->rear)Q->rear=Q->front;

//只有一個(gè)元素時(shí)，出隊(duì)后隊(duì)空，此時(shí)還要修改隊(duì)尾指針free(p);returnx;}}

算法舉例3.5假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，不設(shè)頭指針，試設(shè)計(jì)相應(yīng)的入隊(duì)列和出隊(duì)列的算法

typedefstructLqueue{ElemTypedata;structLqueue*next;}Lqueue,*Queueptr;

voidQueueIn(Queueptrrear,ElemTypex){//入隊(duì)列s=(Queueptr)malloc(sizeof(LQueue));s->data=x;s->next=rear->next;//元素插入隊(duì)尾rear->next=s;rear=s;//求得新的隊(duì)尾}

ElemTypeQueueOut(Queueptrrear){//出隊(duì)列if(rear->next==rear)printf("隊(duì)列為空");else{p=rear->next;q=p->next;

p->next=q->next;x=q->data;if(q==rear)rear=p;free(q);//刪除隊(duì)頭元素return(x);

}}

算法舉例3.6要求完全利用循環(huán)隊(duì)列中的元素空間，設(shè)置一個(gè)標(biāo)志域tag，并以tag的值是0或１來(lái)區(qū)分尾指針和頭指針相同時(shí)的隊(duì)列狀態(tài)是“空〞還是“不空〞。請(qǐng)編寫與此結(jié)構(gòu)相對(duì)應(yīng)的入隊(duì)和出隊(duì)的算法。類型定義：typedefstruct{ElemTypedata[m];intrear,front;//隊(duì)尾和隊(duì)頭指針inttag;//標(biāo)記,0為空,1為非空}CycQueue;

只設(shè)標(biāo)志的循環(huán)隊(duì)列的入隊(duì)voidQueueIn(CycQueuecq,ElemTypex){if(cq.tag==1&&cq.front==cq.rear){printf(“隊(duì)滿\n〞);exit(0);}else{cq.rear=(cq.rear+1)%m;cq.data[cq.rear]=x;if(cq.tag==0)cq.tag=1;//由空變不空標(biāo)記}}只設(shè)標(biāo)志的循環(huán)隊(duì)列的出隊(duì)voidQueueOut(CycQueuecq);{if(cq.tag==0){printf(“隊(duì)空\(chéng)n〞);exit(0);}else{cq.front=(cq.front+1)%m;if(cq.front==cq.rear)cq.tag=0;//隊(duì)列由不空變空}}算法舉例3.7用棧模擬隊(duì)列請(qǐng)利用兩個(gè)棧S1和S2來(lái)模擬一個(gè)隊(duì)列。棧的三個(gè)運(yùn)算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：判ST棧是否為空。那么如何利用棧的運(yùn)算來(lái)實(shí)現(xiàn)該隊(duì)列的三個(gè)運(yùn)算：enqueue:插入一個(gè)元素入隊(duì)列；dequeue:刪除一個(gè)元素出隊(duì)列；queue_empty：判隊(duì)列為空?！旧虾＝煌ù髮W(xué)1999二(12分)】【廈門大學(xué)2005六(15分)】算法舉例3.7棧模擬隊(duì)列－－入隊(duì)inttop1;∥top1是棧s1的棧頂指針，是全局變量intenqueue(stacks1,ElemTypex)∥用入棧模擬入隊(duì){