數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計（第二版）課件 第3章 棧與隊列

第三章棧與隊列西安科技大學計算機學院張小艷數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計第二章復習第三章棧和隊列1．教學目的：①掌握棧和隊列這兩種數(shù)據(jù)結(jié)構(gòu)的特點。②熟練掌握棧的兩種實現(xiàn)方法，注意棧滿和?？盏臈l件。③熟練掌握循環(huán)隊列和鏈隊列的基本操作，注意隊滿和隊空的條件。④理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。⑤了解棧和隊列的一些典型應用。掌握棧和隊列的定義、特點、典型算法及在實際中的應用。2．教學要求：3．教學重點：①掌握棧和隊列兩種數(shù)據(jù)結(jié)構(gòu)的特點。②掌握棧與隊列在兩種存儲結(jié)構(gòu)上的基本操作的實現(xiàn)。4．教學難點：①循環(huán)隊列。②遞歸。3.1棧3.1.1棧的定義當棧中沒有元素時稱為空棧。處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素。將線性表的插入和刪除運算限制為僅在表的一端進行。將表中允許進行插入、刪除操作的一端稱為棧頂(Top)，表的另一端被稱為棧底(Bottom)。棧的插入操作被稱為進?；蛉霔?，刪除操作稱為出?；蛲藯?。（a1,a2,…，ai-1，ai，ai+1，…，an）BottomTopa1a2……an進棧出棧棧底棧頂?shù)谝环N：1，2，3進，再3，2，1出。出棧次序：321第二種：1進，1出，2進，2出，3進，3出。出棧次序：123第三種：1進，2進，2出，1出，3進，3出。出戰(zhàn)次序：213第四種：1進，1出，2進，3進，3出，2出。出戰(zhàn)次序：132第五種：1進，2進，2出，3進，3出，1出。出戰(zhàn)次序：231

棧對線性表的插入和刪除的位置做了限制，但是值得注意的是，沒有對元素插入和刪除的時間進行限制。所以，并不是說元素依a1,a2,…,an的順序進棧過程中不允許元素出棧。例如，1,2,3依次進棧，會有哪些出棧次序?不會有，因為3先出棧，那意味著3進過棧；若3進過，就是說1、2已經(jīng)在棧里了，1是棧底，3是棧頂，出來次序只能是321。

有沒有312的出棧次序呢?3.1.2基本操作(1)棧初始化Init_Stack(S)：構(gòu)造了一個空棧。(2)判?？誆mpty_Stack(S)：棧S存在，若S為空棧返回為1，否則返回為0。(3)入棧Push_Stack(S,x)：棧S已存在且不滿，在棧S的頂部插入一個新元素x，x成為新的棧頂元素。棧發(fā)生變化。(4)出棧Pop_Stack(S)：棧S存在且非空。將棧S的頂部元素從棧中刪除，棧中少了一個元素。棧發(fā)生變化。(5)讀棧頂元素Top_Stack(S)：棧S存在且非空。棧頂元素作為結(jié)果返回，棧不變化。a1a2……an進棧出棧棧底棧頂棧本身就是一個線性表，第二章所討論的線性表的兩種存儲結(jié)構(gòu)同樣適合棧。棧底位置可以設(shè)置在數(shù)組的任一個端點，而棧頂是隨著插入和刪除而變化的;設(shè)一個位置指針top（棧頂指針）來動態(tài)地指示棧頂元素在順序棧中的位置。1．順序棧利用順序存儲方式表示的棧稱為順序棧。棧中的數(shù)據(jù)元素用一個預設(shè)的足夠大的一維數(shù)組來實現(xiàn)datatypedata[MAXSIZE];3.2棧的存儲結(jié)構(gòu)#defineMAXSIZE<最大元素數(shù)>typedefstruct{datatypeelem[MAXSIZE];inttop;}SeqStack；定義一個指向順序棧的指針：

SeqStack*S

通常0下標端設(shè)為棧底，這樣空棧時棧頂指針S->top?=?-1；入棧時，棧頂指針加1，即S->top++；出棧時，棧頂指針減1，即S->top--。⑴置?？枕樞驐５幕静僮鳎篿ntInit_SeqStack(SeqStack*s){if((s=(SeqStack*)malloc(sizeof(SeqStack)))==NULL)return0;s->top=-1;return1;}⑵判?？読ntEmpty_SeqStack(SeqStack*s){if(s->top==-1)return1;elsereturn0;}⑶入棧1intPush_SeqStack(SeqStack*S,datatypex) /*插入數(shù)據(jù)元素x*/2{3if(S->top==MAXSIZE-1) /*棧滿不能入棧*/4return0;5else6{S->top++; /*棧頂指針加1*/7S->elem[S->top]=x; /*將插入數(shù)據(jù)元素x賦給棧頂空間*/8return1;9}10}⑷出棧1intPop_SeqStack(SeqStack*S,datatype*x)2{if(S->top==-1)3return0; /*?？詹荒艹鰲?/4else5{6*x=S->elem[S->top]; /*棧頂元素存入*x，返回*/7S->top--; /*棧頂指針減1*/8return1;9}10}⑸取棧頂元素intTop_SeqStack(SeqStack*s,datatype*x){if(Empty_SeqStack(s))return0;else{*x=s->data[s->top];return1;}}⑴

對于順序棧，入棧時，首先判斷是否棧滿。棧滿時，不能入棧。說明：⑵出棧和讀棧頂元素操作，先判斷棧是否為空，為空不能操作。棧滿的條件為：s->top==MAXSIZE-1可以讓多個棧共用一個足夠大的連續(xù)存儲空間。利用棧的動態(tài)特性使它們的存儲空間互補。這就是棧的共享鄰接空間假設(shè)兩個棧共享一維數(shù)組stack[MAXSIZE]，只要整個數(shù)組stack[MAXSIZE]未被占滿，無論哪個棧的入棧都不會發(fā)生上溢。棧的共享中最常見的是兩個棧的共享。它可以利用棧的“棧底位置不變，棧頂位置動態(tài)變化”的特性，兩個棧底分別為-1和MAXSIZE，它們的棧頂都往中間方向延伸。3.2.2兩個棧的共享空間#defineMAXSIZE<最大元素數(shù)>typedefstruct{datatypestack[MAXSIZE];intlefttop;intrighttop;}dupsqstack;兩棧共享鄰接空間的結(jié)構(gòu)如下：charstatus;status=’L’;status=’R’;在進行棧操作時，需指定棧號；判斷棧滿的條件為：s->lefttop+1==s->righttop;為了識別左右棧，必須另外設(shè)定標志：兩個棧共享空間時初始化、進棧和出棧操作的算法：intinitDupStack(dupsqstack*s){if((s=(dupsqstack*)malloc(sizeof(dupsqstack)))==NULL)return0;

s->lefttop=-1;s->righttop=MAXSIZE;return1;}1初始化操作2入棧操作intpushDupStack(dupsqstack*s,charstatus,datatypex){if(s->lefttop+1==s->righttop)return0;

if(status=’L’)s->stack[++s->lefttop]=x;

elseif(status=’R’)

s->stack[--s->righttop]=x;elsereturn0;return1;}datatypepopDupStack(dupsqstack*s,charstatus){if(status==’L’)if(s->lefttop<0)returnNULL;else

return(s->stack[s->lefttop--]);

elseif(status==’R’){if(s->righttop>MAXSIZE-1)returnNULL;else

return(s->stack[s->righttop++]);

}elsereturnNULL;}（3）出棧操作3.2.3.鏈棧用鏈式存儲結(jié)構(gòu)實現(xiàn)的棧稱為鏈棧，C語言描述：typedefstructnode{datatypedata;structnode*next;}StackNode，*LinkStackptr;LinkStackptrtoptypedefstructlinkStack{LinkStackptrtop;intcount;}linkStack;top

∧說明：棧的主要運算是在棧頂插入、刪除，將鏈表的頭部做棧頂是最方便的，而且沒必要象單鏈表為了運算方便附加一個頭結(jié)點?！?/p>

（NULL）abcdes

鏈棧示意圖1intPush_LinkStack(LinkStack*S,datatypex)2{LinkStackptrp;3if((p=(LinkStackptr)malloc(sizeof(StackNode)))==NULL)4return0;5p->data=x;6p->next=S->top;7S->top=p;8S->count++;9return1;10}鏈?；静僮鞯膶崿F(xiàn)如下：1入棧1LinkStackPop_LinkStack(LinkStack*S,datatype*x)2{3LinkStackptrp;4if(S->top==NULL)returnNULL;5else6{7*x=(S->top)->data;8p=S->top;9S->top=(S->top)->next;10free(p);11S->count--;12return(S->top);13}14}2出棧topabcdep∧ppppNULL將十進制數(shù)N轉(zhuǎn)換為r進制的數(shù)，其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法：以N=3467，r=8為例轉(zhuǎn)換方法如下：

NN/8（整除）N%8（求余）

34674333低

4335415466606高所以：（3467）10=（6613）8補充例1簡單應用：數(shù)制轉(zhuǎn)換問題3.3棧的應用舉例算法思想(討論）：當N>0時重復①，②①若N≠0，則將N%r壓入棧s中，執(zhí)行②；若N=0，將棧s的內(nèi)容依次出棧，算法結(jié)束。②用N/r代替N#defineL10voidconversion(intN，intr){ints[L],top;intx;top=-1;while(N){if(top<L-1)s[++top]=N%r;N=N/r;}while(top!=-1){x=s[top--];printf(“%d”,x);}}算法3.1(a)算法3.1(b)typedefintdatatype;voidconversion(intN，intr){SeqStacks;datetypex;Init_SeqStack(&s);while(N){Push_SeqStack(&s，N%r);N=N/r;}while(Empty_SeqStack(&s)){Pop_SeqStack(&s，&x);printf(“%d”，x);}

}例3.1表達式求值。

1.中綴表達式求值(又稱波蘭表達式）例如，10+(5-3)*5就是一個中綴表達式，是我們常說的四則運算表達式。

我們這里處理的是理想化狀態(tài)下的四則運算表達式(即每個二目運算符在兩個操作數(shù)的中間，假設(shè)操作數(shù)是整型常數(shù)，運算符只含加、減、乘、除等四種，界限符有左右括號和表達式起始、結(jié)束符“#”)，例如，#(7+15)*(23-28/4)#。要對一個簡單的算術(shù)表達式求值，首先要了解算術(shù)四則運算的規(guī)則，即：

(1)從左到右；

(2)先乘除，后加減；

(3)先括號內(nèi)，后括號外。表3-1算符之間的優(yōu)先關(guān)系表達式求值算法的基本過程如下：

(1)首先初始化操作數(shù)棧operand和運算符棧operator，并將表達式起始符“?！眽喝脒\算符棧。

(2)依次讀入表達式中的每個字符，若是操作數(shù)則直接進入操作數(shù)棧operand。若是運算符，則與運算符棧operator的棧頂運算符進行優(yōu)先權(quán)比較，并做如下處理：①若棧頂運算符的優(yōu)先級低于剛讀入的運算符，則讓剛讀入的運算符進operator棧。②若棧頂運算符的優(yōu)先級高于剛讀入的運算符，則將棧頂運算符退棧，送入θ，同時將操作數(shù)棧operand退棧兩次，得到兩個操作數(shù)a、b，對a、b進行θ運算后，將運算結(jié)果作為中間結(jié)果推入operand棧。③若棧頂運算符的優(yōu)先級與剛讀入的運算符的優(yōu)先級相同，說明左、右括號相遇，只需將棧頂運算符左括號“(”退棧即可。operator棧的棧頂元素和當前讀入的字符均為“#”時，說明表達式起始符“#”與表達式結(jié)束符“#”相遇，整個表達式求解結(jié)束。以?#10+3*2#?為例1intExpEvaluation()2{/*operator和operand分別為運算符棧和運算數(shù)棧，OPS為運算符集合*/3InitStack(&operand); /*初始化運算數(shù)棧*/4InitStack(&operator); /*初始化運算符棧*/5PushStack(&operator,'#'); /*“#”入運算符棧*/6printf(″\n\nPleaseinputanexpression(Endingwith#):″);7ch=getchar(); /*讀入表達式中的一個字符*/8while(ch!='#'||GetTop(operator)!='#')/*GetTop()通過函數(shù)值返回棧頂元素*/9{10if(!In(ch,OPS)) /*判斷ch是否運算符*/11{a=GetNumber(&ch);/*用ch逐個讀入操作數(shù)的各位數(shù)碼，并轉(zhuǎn)化為十進制數(shù)a*/12PushStack(&operand,a);13}14else

15switch(Compare(GetTop(operator),ch))16{case'<':PushStack(&operator,ch);17ch=getchar();break;18case'=':PopStack(&operator,&x);19ch=getchar();break;20case'>':PopStack(&operator,&op);21PopStack(&operand,&b);22PopStack(&operand,&a);23v=Execute(a,op,b); /*對a和b進行op運算*/24PushStack(&operand,v);25break;26}27}28v=GetTop(operand);29return(v);30}2.后綴表達式求值(又稱逆波蘭表達式）后綴表達式32*5-?的計算過程typedefchardatetype;1doublecalcul_exp(char*A)2{/*本函數(shù)返回由后綴表達式A表示的表達式運算結(jié)果*/3SeqStarckS;4ch=*A++;5InitStack(S);6while(ch!='#')7{8if(ch!=運算符)9PushStack(S,ch);10else11{12PopStack(S,&b);/*取第二個運算量*/13PopStack(S,&a);/*取第一個運算量*/14switch(ch)15{casech=='+':c=a+b;break;16casech=='-':c=a-b;break;17casech=='*':c=a*b;break;18casech=='/':c=a/b;break;19casech=='%':c=a%b;break;20}21PushStack(S,c);22}23ch=*A++;24}25PopStack(S,result);26returnresult;27}棧非常重要的一個應用是在程序設(shè)計語言中用來實現(xiàn)遞歸。遞歸是指在函數(shù)直接或間接的調(diào)用自己。3.4

棧與遞歸1)很多數(shù)學函數(shù)是遞歸定義的例如，階乘及二階Fibonacci數(shù)列：2)有的數(shù)據(jù)結(jié)構(gòu)可用遞歸描述(例如:二叉樹,廣義表等)3)還有一類問題,沒有明顯的遞歸結(jié)構(gòu)。但用遞歸求解比迭代求解更簡單如八皇后問題、Hanoi塔問題。3.4.1棧與遞歸的實現(xiàn)過程fact(n)=1，??n?=?0/*遞歸終止條件*/n?×?(n-1)，?n?>?0?/*遞歸步驟*/fib(n)=0，

n?=?0/*遞歸終止條件*/1，

n?=?1/*遞歸終止條件*/fib(n-1)?+?fib(n-2)，??n?>?1/*遞歸步驟*/

以階乘函數(shù)為例說明棧在遞歸中的應用。

intfact(intn){if(n==0)return1;elsereturn(n*fact(n-1));}可以看出，遞歸的特點如下：①遞歸就是在過程或函數(shù)里調(diào)用自身。②在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，稱為遞歸出口。

如果一個問題具有以下特點時，我們可以選擇遞歸實現(xiàn)：①問題具有類同自身的子問題的性質(zhì)，被定義項在定義中的應用具有更小的尺度。如上面階乘函數(shù)的遞歸設(shè)計：fact(n)?=?n?×?fact(n-1)。②被定義項在最小尺度上有直接解。如階乘的遞歸設(shè)計：n=0時，結(jié)果為1，即fact(0)=1。

設(shè)計遞歸的方法是：

①尋找方法，將問題化為原問題的子問題求解。例如，n!?=?n?×?(n-1)!。②設(shè)計遞歸出口，確定遞歸終止條件。例如，求解n!?時，當n?=?1時，n!?=?1。

遞歸函數(shù)的調(diào)用類似于多層函數(shù)的嵌套調(diào)用，只是調(diào)用單位和被調(diào)用單位是同一個函數(shù)而已。在每次調(diào)用時系統(tǒng)將屬于各個遞歸層次的信息組成一個活動記錄(ActivationRecord)，這個記錄中包含著本層調(diào)用的實參、返回地址、局部變量等信息，并將這個活動記錄保存在系統(tǒng)的“遞歸工作?！敝?。每當遞歸調(diào)用一次，就要在棧頂為過程建立一個新的活動記錄，一旦本次調(diào)用結(jié)束，則將棧頂活動記錄出棧，根據(jù)獲得的返回地址信息返回到本次的調(diào)用處。遞歸進層(i→i+1層)系統(tǒng)的工作遞歸退層(i←i+1層)系統(tǒng)的工作①保存本層參數(shù)與返回地址，為局部變量分配空間。就是在遞歸工作棧棧頂建立一個新的活動記錄。②將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口①保存被調(diào)函數(shù)的計算結(jié)果。②恢復上層參數(shù)，釋放被調(diào)函數(shù)所占存儲區(qū)，即將棧頂活動記錄出棧。③根據(jù)獲得的返回地址信息返回到本次的調(diào)用處main(){intm,n=3;m=fact(n);

R1:printf(″%d!=%d\n″,n,m);

}intfact(intn){intf;if(n==0)f=1;elsef=n*fact(n-1);returnf;}R1為主函數(shù)調(diào)用fact時返回點的位置，

R2為fact函數(shù)中遞歸調(diào)用fact(n-1)時返回點的位置。

fact(n-1)返回后再進行乘運算。

設(shè)主函數(shù)中n?=?3R2設(shè)有3根針A、B、C，在A上有n個金片，從上到下疊放，且直徑依次從小到大，編號依次為1,2,3,4，…，n。要求按下列規(guī)則將所有金片移至C針：每次只能移動一個金片；大金片不能疊在小金片上面；金片臨時置于B針。當n?=?1時，直接將A上的移到C上即可。當n?=?2時，可以利用B針，先將1號金片移到B上，然后將2號金片移到C上，再將1號金片從B上移到C上，結(jié)束。當n?=?3時，同樣借助B針，依照上面原則，先將1、2號金片借助C針移到B針上，之后將3號金片移到C針上，再將B上的1、2號金片借助A針移到C針上?！?/p>

也就是說，當n?>?1時，需要利用輔助針B，先設(shè)法將壓在n號金片之上的n-1個金片移到B上，這樣就可以將A上的n號金片直接移到C上，再將B上的n-1個金片借助A移到C上。這是一個典型的遞歸。3.4.2漢諾塔voidhanoi(intn,charX,charY,charZ) /*將X上的n個金片借助Y移到Z上*/①{if(n==1)②{move(n,X,Z);/*可以寫成：printf(“將X上的%d號金片移到Z上”,n)，*/③}④else⑤{hanoi(n-1,X,Z,Y);/*將X上的n-1個金片借助Z移到Y(jié)上*/⑥move(n,X,Z); /*將X上的n號金片移到Z上*/⑦hanoi(n-1,Y,X,Z); /*將Y上的n-1個金片借助X移到Z上*/⑧}⑨}main(){intn;printf("請輸入金片數(shù)n:\n");scanf("%d",&n);hanoi(n,'A','B','C');/*調(diào)用函數(shù)*/}voidhanoi(intn,charX,charY,charZ) ①{if(n==1)②{move(n,X,Z);③}④else⑤{hanoi(n-1,X,Z,Y);⑥move(n,X,Z); ⑦hanoi(n-1,Y,X,Z); ⑧}⑨}main(){intn;printf("請輸入金片數(shù)n:\n");scanf("%d",&n);hanoi(n,'A','B','C');/*調(diào)用函數(shù)*/}voidhanoi(intn,charX,charY,charZ) ①{if(n==1)②{move(n,X,Z);③}④else⑤{hanoi(n-1,X,Z,Y);⑥move(n,X,Z); ⑦hanoi(n-1,Y,X,Z); ⑧}⑨}main(){intn;printf("請輸入金片數(shù)n:\n");scanf("%d",&n);hanoi(n,'A','B','C');/*調(diào)用函數(shù)*/}voidhanoi(intn,charX,charY,charZ) ①{if(n==1)②{move(n,X,Z);③}④else⑤{hanoi(n-1,X,Z,Y);⑥move(n,X,Z); ⑦hanoi(n-1,Y,X,Z); ⑧}⑨}main(){intn;printf("請輸入金片數(shù)n:\n");scanf("%d",&n);hanoi(n,'A','B','C');/*調(diào)用函數(shù)*/}voidhanoi(intn,charX,charY,charZ) ①{if(n==1)②{move(n,X,Z);③}④else⑤{hanoi(n-1,X,Z,Y);⑥move(n,X,Z); ⑦hanoi(n-1,Y,X,Z); ⑧}⑨}main(){intn;printf("請輸入金片數(shù)n:\n");scanf("%d",&n);hanoi(n,'A','B','C');/*調(diào)用函數(shù)*/}voidhanoi(intn,charX,charY,charZ) ①{if(n==1)②{move(n,X,Z);③}④else⑤{hanoi(n-1,X,Z,Y);⑥move(n,X,Z); ⑦hanoi(n-1,Y,X,Z); ⑧}⑨}main(){intn;printf("請輸入金片數(shù)n:\n");scanf("%d",&n);hanoi(n,'A','B','C');/*調(diào)用函數(shù)*/}voidhanoi(intn,charX,charY,charZ) ①{if(n==1)②{move(n,X,Z);③}④else⑤{hanoi(n-1,X,Z,Y);⑥move(n,X,Z); ⑦hanoi(n-1,Y,X,Z); ⑧}⑨}main(){intn;printf("請輸入金片數(shù)n:\n");scanf("%d",&n);hanoi(n,'A','B','C');/*調(diào)用函數(shù)*/}voidhanoi(intn,charX,charY,charZ) ①{if(n==1)②{move(n,X,Z);③}④else⑤{hanoi(n-1,X,Z,Y);⑥move(n,X,Z); ⑦hanoi(n-1,Y,X,Z); ⑧}⑨}main(){intn;printf("請輸入金片數(shù)n:\n");scanf("%d",&n);hanoi(n,'A','B','C');/*調(diào)用函數(shù)*/}voidhanoi(intn,charX,charY,charZ) ①{if(n==1)②{move(n,X,Z);③}④else⑤{hanoi(n-1,X,Z,Y);⑥move(n,X,Z); ⑦hanoi(n-1,Y,X,Z); ⑧}⑨}main(){intn;printf("請輸入金片數(shù)n:\n");scanf("%d",&n);hanoi(n,'A','B','C');/*調(diào)用函數(shù)*/}

借助B針，從A針移動n個金片到C針，需要移動多少次?設(shè)M(n)為移動金片的次數(shù)，對于M(n)有下列遞推等式：當n?=?1時，M(n)?=?1當n?>?1時，M(n)?=?M(n?-?1)?+?1?+?M(n?-?1)?=?2M(n?-?1)?+?1我們來解這個遞推公式：

M(n)

=

2M(n

-

1)

+

1

=

2[2M(n

-

2)

+

1]

+

1

=

22M(n

-

2)

+

2

+

1

=

22[2M(n

-

3)

+

1]

+

2

+

1

=

23M(n

-

3)

+

22

+

2

+

1

=…

=

2iM(n

-

i)

+

2i-1

+

2i-2

+

…

+

2

+

1

=…=

2n-1M(n

-

(n

-

1))

+

2n-1

-

1

=

2n

-

1

n=64時，

M(64)?=?264

-?1?=?18?446?744?073?709?551?615假如每秒鐘一次，共需多長時間呢?一個平年365天有31?536?000秒，閏年366天有31?622?400秒，平均每年31?556?952秒，計算一下：584

554

049

253.855年18?446?744?073?709?551?61531?556?9523.5隊列的定義及基本運算

允許插入的一端叫做隊尾(rear)，允許刪除的一端則稱為隊頭(front)。設(shè)隊列為q=(a1，a2，…，an)，a1是隊頭元素，an是隊尾元素.3.5.1隊列的定義隊列(Queue)是一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素.特點：先進先出(FistInFistOut，縮寫為FIFO)

。a1a2…ai…anan-1frontrear入隊列出隊列(1)隊列初始化Init_Queue(q)：隊列q不存在，構(gòu)造了一個空隊。(2)入隊操作In_Queue(q,x)：隊列q存在，對已存在的隊列q，插入一個元素x到隊尾，隊發(fā)生變化。(3)出隊操作Out_Queue(q,x)：隊列q存在且非空，刪除隊首元素，并返回其值，隊發(fā)生變化。(4)讀隊頭元素Front_Queue(q,x)：隊列q存在且非空，讀隊頭元素，并返回其值，隊不變。(5)判隊空操作Empty_Queue(q)：隊列q存在，若q為空隊則返回為1；否則返回為0。3.5.2基本運算a1a2…ai…anan-1frontrear入隊列出隊列3.6隊列的存儲結(jié)構(gòu)及操作實現(xiàn)#defineMAXSIZE1024/*隊列的最大容量*/typedefstruct{datatypedata[MAXSIZE];/*隊列的存儲空間*/intrear,front; /*隊頭隊尾指針*/}SeQueue;3.6.1順序隊列隊列的數(shù)據(jù)區(qū)為sq->data[0]～sq->data[MAXSIZE?-?1]

隊頭指針：sq->front隊尾指針：sq->rear

設(shè)隊頭指針指向當前隊頭元素前面一個位置，隊尾指針指向隊尾元素定義一個指向隊的指針變量：

SeQueue*sq;a1a2…ai…anan-1frontrear入隊列出隊列置空隊則為：

sq->front?=?-1;sq->rear?=?sq->front;不考慮溢出的情況下，入隊操作隊尾指針加1，指向新位置后，元素入隊。

sq->rear++;

sq->data[sq->rear]?=?x;不考慮隊空的情況下，出隊操作隊頭指針加1，表明隊頭元素出隊。sq->front++;x?=?sq->data[sq->front];隊中元素的個數(shù)：m?=?(sq->rear)?-?(q->front)。隊滿時：m?=?MAXSIZE；隊空時：m?=?0。請大家看圖思考GBCFEfrontrear0123456MAXSIZE-1DAH此時，再有元素入隊列就會溢出，可是從圖中看出隊列并不滿，請大家思考這是為什么呢？這種情況就稱為“假溢出”3.6.2循環(huán)隊列解決假溢出的方法之一是將隊列的數(shù)據(jù)區(qū)看成頭尾相接的循環(huán)結(jié)構(gòu)，頭尾指針的關(guān)系不變，將其稱為“循環(huán)隊列”入隊操作為：sq->rear=(sq->rear+1)%MAXSIZE出隊操作為:sq->front=(sq->front+1)%MAXSIZErear01234567EFGHIJfrontrearrearfrontfrontfrontfrontfrontrearrearLK“隊滿”和“隊空”的條件相同。這顯然是必須要解決的一個問題。frontfrontfront

方法一：附設(shè)一個存儲隊中元素個數(shù)的變量num，當num==0時隊空，當num==MAXSIZE時為隊滿。方法二：少用一個元素空間，隊滿的條件是：(rear+1)%MAXSIZE==front。typedefstruct{datatypedata[MAXSIZE];intfront,rear;intnum;}c_SeQueue;下面的循環(huán)隊列及操作按第一種方法實現(xiàn)循環(huán)隊列的類型定義及基本運算如下：rear01234567EFGHIJfrontrearrearfrontfrontfrontfrontfrontrearrearLKfrontfrontfront創(chuàng)建一個空隊列，由指針q指出。1intInit_SeQueue(c_SeQueue*q)2{3if((q=((c_SeQueue*)malloc(sizeof(c_SeQueue))))==NULL)return0;4q->front=MAXSIZE;5q->rear=MAXSIZE;6q->num=0;7return1;8}⑴置空隊rear01234567front1intIn_SeQueue(c_SeQueue*q,datatypex)2{if(q->num==MAXSIZE)3{printf(″隊滿″);4return–1;/*隊滿不能入隊*/5}6else7{q->rear=(q->rear+1)%MAXSIZE;8q->data[q->rear]=x;9q->num++;10return1;/*入隊完成*/11}12}⑵入隊rear01234567EFGHIJfrontrearrearfrontfrontfrontfrontfrontrearrearLKfrontfrontfront1intOut_SeQueue(c_SeQueue*q,datatype*x)2{if(q->num==0)3{printf(″隊空″);4return–1;/*隊空不能出隊*/5}6else7{q->front=(q->front+1)%MAXSIZE;8*x=q->data[q->front];/*讀出隊頭元素*/9q->num--;10return1; /*出隊完成*/11}12}⑶出隊rear01234567EFGHIJfrontrearrearfrontfrontfrontfrontfrontrearrearLKfrontfrontfront1intEmpty_SeQueue(c_SeQueue*q)2{if(q->num==0)3return1;4else5return0;6}⑷判隊空請寫出關(guān)于第二種方法實現(xiàn)的循環(huán)隊列。判空條件：q->front->next==NULL;

或q->rear=q->front;3.6.3鏈隊列為了操作的方便，給鏈隊列添加一個頭結(jié)點，并設(shè)定頭指針指向頭結(jié)點。frontrear^fronta1a2ai…an…rear^鏈隊的描述如下：typedefstructnode{datatypedata;structnode*next;}QNode;ty