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

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

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

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

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

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

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

棧的抽象數(shù)據(jù)類型定義ADTStack{數(shù)據(jù)對象：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)求棧長：StackLength(S)}ADTStack棧的表示和實現(xiàn)順序存儲結(jié)構(gòu)：順序棧；鏈式存儲結(jié)構(gòu)：鏈棧；

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

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

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

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

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

雙向棧棧1底棧2底棧1棧2…兩個棧共享一個向量空間，棧底分別設在兩端，寫出進棧和退棧操作雙向棧的類型定義#definem64typedefstruct{ElemTypedata[m];inttop[2];//top[0],top[1]分別是兩個棧的棧頂指針}TStack;初始化時，top[0]=-1和top[1]=m表示?？?，棧頂相遇時表示棧滿，入棧時棧頂指針相向移動。鏈棧用鏈式存儲結(jié)構(gòu)實現(xiàn)的棧稱為鏈棧。通常鏈棧可用單鏈表表示，因此其結(jié)點結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同。

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

∧

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

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

自測題設棧的輸入序列是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，【煙臺大學2007一.4(2分)】D自測題設輸入元素為1、2、3、P和A，輸入次序為123PA，如圖〔編者略〕。元素經(jīng)過棧后達輸出序列，當所有元素均到達輸出序列后，有哪些序列可以作為高級語言的變量名?！局猩酱髮W1997】PA321P3A21P32A1P321AAP321自測題1．假設元素a，b，c，d，e，f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，那么不可能得到的出棧序列是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年全國碩士研究生入學統(tǒng)一考試計算機學科專業(yè)根底綜合】D棧的應用棧與過程調(diào)用表達式求值棧與遞歸過程棧與過程調(diào)用過程的嵌套調(diào)用圖示：算法舉例3.1棧的應用:數(shù)制轉(zhuǎn)換把十進制數(shù)轉(zhuǎ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(){//把十進制轉(zhuǎ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){//把十進制n轉(zhuǎn)換為八進制if(n!=0) {Convert(n/8);printf(“%d〞,n%8); }}算法舉例3.2:中綴表達式的求值算術(shù)表達式中運算符(+,-,*,/等)的優(yōu)先規(guī)那么設置兩個工作棧：運算符棧S1和操作數(shù)棧S2。S2存放表達式的運算結(jié)果。算法思想：1首先置操作數(shù)棧S2為空棧，置運算符棧的棧底為表達式的起始符#(優(yōu)先級最低)。2依次讀入表達式的每個字符ch,直至表達式結(jié)束：假設ch是操作數(shù),那么進S2棧；假設ch是運算符，假設其優(yōu)先級不高于棧頂運算符的優(yōu)先級時，那么取出棧S2的棧頂和次棧頂?shù)膬蓚€元素以及棧S1的棧頂運算符，進行相應的運算，并將結(jié)果放入棧S2中；如此下去，直至ch的優(yōu)先級高于棧頂運算符的優(yōu)先級，將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){消除一對括號}9#*33#operate(‘3’,’*’,’3’)10#9#return(gettop(s2))中綴表達式求值算法ElemTypeEvalExpression(){charch,opnd[maxch],optr[maxch];//opnd是運算數(shù)棧,optr是運算符棧init(optr);push(optr,‘#’);init(opnd);ch=getchar();while(ch!=‘#’||gettop(optr)!=‘#’)if(!in(ch,op)){push(opnd,ch);ch=getchar();}//不是運算符就進棧elseswitch(precede(gettop(optr),ch)){case‘<’://棧頂元素優(yōu)先級低push(optr,ch);ch=getchar();break;case‘=’://脫括號并接收下一字符pop(optr,x);ch=getchar();break;case‘>’://退棧并將運算結(jié)果入棧pop(optr,theta);pop(opnd,b);pop(opnd,a);push(opnd,operate(a,theta,b));break;}//switchreturngettop(opnd);}中綴表達式轉(zhuǎn)為后綴表達式概念：前綴表達式，中綴表達式，后綴表達式+ab,a+b,ab+〔1〕中綴表達式轉(zhuǎn)為后綴表達式設中綴表達式和后綴表達式分別在向量IFX和PFX申，用棧S實現(xiàn)中綴式轉(zhuǎn)為后綴式，對IFX中表達式從左到右掃描，設TOKEN是掃描讀到的符號，轉(zhuǎn)換算法可描述如下：棧初始化從左到右掃描向量IFX，重復下述兩步操作，直到表達式尾：①從IPX中取出下個TOKEN(數(shù)字、運算符、左括號、右括號)；②CASETOKENOF‘(’：將TOKEN壓入棧S;‘)’：退棧并將退棧元素送PFX，直到碰到左括號，左括號退棧不送PFX。操作數(shù)：將操作數(shù)直接送入PFX;操作符：如棧空或TOKEN比棧頂元素優(yōu)先級高，將TOKEN進棧；否那么，退棧并將退棧元素送入PFX，然后再將TOKEN與新棧頂元素比較之;當遇到中綴表達式結(jié)束符號，連續(xù)退棧并送退棧元素到PFX，直至?？?。舉例：將中綴表達式

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

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

算法舉例3.3后綴表達式求值

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

缺點：時間效率低空間開銷大算法不容易優(yōu)化對于頻繁使用的算法，或不具備遞歸功能的程序設計語言，需要把遞歸算法轉(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é)點數(shù)據(jù)的遞歸算法if(L){printf(L->data);∥輸出結(jié)點的值

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

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

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

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

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

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

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

…a2Q(b)空隊rearfrontQ

∧

(c)鏈隊中只有一個元素結(jié)點frontrearQa1∧

鏈隊列的類型描述

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

typedefstruct{StructLQNode*front,*rear;}LQueue,*LinkedQueue;//將頭尾指針封裝在一起的鏈隊鏈隊列的初始化創(chuàng)立一個帶頭結(jié)點的空隊LinkedQueueLinkedQueueInit(){Q=(LinkedQueue)malloc(sizeof(LQueue));//申請頭尾指針結(jié)點p=(LinkedQNode)malloc(sizeof(LQNode));

//申請鏈隊頭結(jié)點p->next=NULL;Q->front=Q->rear=p;returnQ;}

鏈隊列的入隊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;}鏈隊列的判空intLinkedQueueEmpty(LinkedQueueQ){if(Q->front==Q->rear)returntrue;elsereturnfalse;}

鏈隊列的出隊出隊

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

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

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

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

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

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

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

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

}}

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

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