第三章(數據結構)

第三章棧和隊列第1頁【學習目標】掌握棧和隊列這兩種抽象數據類型的特點，并能在相應的應用問題中正確選用它們。2.熟練掌握棧類型的兩種實現方法。3.熟練掌握循環(huán)隊列和鏈隊列的基本操作實現算法。4.理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程?！局R點】順序棧、鏈棧、循環(huán)隊列、鏈隊列

注意它們的基本操作實現時的特殊情況，如棧滿和棧空、隊滿和隊空的條件以及它們的描述方法。【學習指南】

第2頁

棧和隊列是在程序設計中被廣泛使用的兩種線性數據結構，它們的特點在于基本操作的特殊性，棧必須按"后進先出"的規(guī)則進行操作，而隊列必須按"先進先出"的規(guī)則進行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結構。

和線性表相比，從"數據結構"的角度看，它們都是線性結構，即數據元素之間的關系相同。但它們是完全不同的數據類型。除了它們各自的基本操作集不同外，主要區(qū)別是對插入和刪除操作的"限定"。第3頁

線性表：Insert(L,i,x)

Delete(L,i)

(1≤i≤n+1)

(1≤i≤n)

棧：Insert(L,n+1,x)

Delete(L,n)

隊列：Insert(L,n+1,x)

Delete(L,1)插入刪除線性表允許在表內任一位置進行插入和刪除；棧只允許在表尾一端進行插入和刪除；隊列只允許在表尾一端進行插入，在表頭一端進行刪除。第4頁3.1.1棧的類型定義

棧（Stack）是限定只能在表的一端進行插入和刪除操作的線性表。在表中，允許插入和刪除的一端稱作"棧頂(top)"，不允許插入和刪除的另一端稱作"棧底(bottom)"

。

通常稱往棧頂插入元素的操作為"入棧"，稱刪除棧頂元素的操作為"出棧"。因為后入棧的元素先于先入棧的元素出棧，故被稱為是一種"后進先出"的結構，因此又稱LIFO（LastInFirstOut的縮寫）表如左圖所示的鐵路調度站表示棧的特點

第5頁類型定義如下：

ADTStack{

數據對象：D＝{ai|ai

∈ElemSet,i=1,2,...,n,n≥0}

數據關系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定an端為棧頂，a1

端為棧底。

基本操作：

InitStack(&S)構造一個空棧S。

DestroyStack(&S)初始條件：棧S已存在。操作結果：棧S被銷毀。

ClearStack(&S)初始條件：棧S已存在。操作結果：將S清為空棧。

StackEmpty(S)判空，通常以它作為循環(huán)結束的條件

GetTop(S,&e)取棧頂元素，只以e返回棧頂元素，并不從棧中刪除 Push(&S,e)入棧操作

Pop(&S,&e)出棧操作，不僅以e返回棧頂元素，并將它從棧中刪除。

}ADTStack第6頁3.1.2棧的存儲表示和操作的實現一、順序棧類型的定義和線性表類似，棧也有兩種存儲表示，其順序存儲結構簡稱為順序棧。和順序表類似，對順序棧也需要事先為它分配一個可以容納最多元素的存儲空間，base為這個存儲空間的基地址，也即一維數組的地址。從名稱來講，“棧頂指針”意為指示棧頂元素在棧中的位置，但它的值實際是棧中元素的個數，和順序表中的length值的意義相同。為了應用方便，這個"最大空間的容量"應由使用這個順序棧的程序員決定，它的默認值和順序表的默認值相同。第7頁順序棧的結構top指向壓棧時下一個元素將要存放的位置。出棧時top減一指向彈棧時下一個元素的取值位置。?？盏臈l件：top=base棧滿的條件：top-base>=stacksizetoptopbase空棧basetopABCABCbase滿棧DE棧的表示和實現非空非滿棧第8頁順序表示

#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;

其中stacksize表示棧當前可以使用的最大容量。Base為棧底，Top為棧頂。棧頂指針指向棧頂元素的下一個位置（即下次壓棧時元素所放的位置）順序隊列第9頁基本操作的實現：初始化棧

StatusInitStack(SqStack&S){

//構造一個空棧

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;

returnOK;}//InitStack第10頁壓棧:StatusPush(SqStack&S,SElemTypee){

//元素e插入到棧中，成為新的棧頂

if(S.top-S.base>=S.stacksize)//棧滿

{S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);

if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}//if*S.top++=e;returnOK;}//Push第11頁彈棧:StatusPop(SqStack&S,SElemType&e){

//從棧頂讀取數據放入e內，棧中下一元素所

//在位置成為新的棧頂

if（S.top==S.base）returnERROR;//?？?/p>

e=*--S.top;

returnOK;}//Pop

注意top的操作順序和值的變化。壓棧：valuetop;top++;

彈棧：top--;top->value;第12頁StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}思考：語句e=*(S.top-1);改為e=*(--S.top);是否正確？第13頁二、鏈棧

鏈棧即為棧的鏈式存儲結構。

鏈棧的定義更簡單，結點結構和單鏈表中的結點結構相同，無須重復定義。注意鏈棧中指針的方向是從棧頂指向棧底的，這正好和單鏈表是相反的。第14頁能否將鏈棧中的指針方向反過來，從棧底到棧頂？不行，如果反過來的話，刪除棧頂元素時，為修改其前驅指針，需要從棧底一直找到棧頂。因為鏈棧的操作是線形表鏈式存儲結構的特例，因此，相關操作可以自己總結出來。

第15頁壓棧的處理：

p=malloc(Lnode);p->next=s->next;s->next=p;彈棧的處理:p=s->next;s->next=s->next->next;spp棧的鏈式表示：假設以首結點作為棧頂，鏈帶有頭結點。第16頁補充：一種新的棧的類型定義

#defineStackSize100typedefchardatatype;typedefstruct{datatypedata[stacksize];inttop;}seqstack;SeqStack*s;思考：如何判斷空棧和滿棧第17頁3.2、棧的應用舉例

3.2.1數制轉換

由于棧的操作具有后進先出的固有特性，致使棧成為程序設計中的有用工具。反之，凡應用問題求解的過程具有"后進先出"的天然特性的話，則求解的算法中也必然需要利用"棧"。十進制數N和其他d進制數的轉換是計算機實現計算的基本問題，其解決方法很多，其中一個簡單算法基于下列原理：

N=(Ndivd)×d+Nmodd

(其中：div為整除運算，mod為求余運算)

例如：(1348)10=(2504)8

NNdiv8N%8 13481684 168210 2125 202第18頁假設現要編制一個滿足下列要求的程序：對于輸入的任意一個非負十進制整數，打印輸出與其等值的八進制數。八進制的各個數位產生的順序是從低位到高位的，而打印輸出的順序，一般來說應從高位到低位，這恰好和計算過程相反。第19頁voidconversion()

{

//對于輸入的任意一個非負十進制整數，打印輸出與其等值的八進制數

InitStack(S);

//構造空棧

scanf(“%d”,N)

//輸入一個十進制數

while(N)

{

Push(S,N%8);

//“余數”入棧

N=N/8;

//非零“商”繼續(xù)運算

}//while

while(!StackEmpty)

{

//和“求余”所得相逆的順序輸出八進制的各位數

Pop(S,e);

cout<<e;

}//while

}//conversion第20頁

檢驗括號是否匹配的方法可用"期待的急迫程度"這個概念來描述。即后出現的"左括弧"，它等待與其匹配的"右括弧"出現的"急迫"心情要比先出現的左括弧高。換句話說，對"左括弧"來說，后出現的比先出現的"優(yōu)先"等待檢驗，對"右括弧"來說，每個出現的右括弧要去找在它之前"最后"出現的那個左括弧去匹配。顯然，必須將先后出現的左括弧依次保存，為了反映這個優(yōu)先程度，保存左括弧的結構用棧最合適。這樣對出現的右括弧來說，只要"棧頂元素"相匹配即可。如果在棧頂的那個左括弧正好和它匹配，就可將它從棧頂刪除。什么樣的情況是“不匹配”的情況呢？1．來的右括弧非是所“期待”的；2．來的是“不速之客”；

3．直到結束，也沒有到來所“期待”的。這三種情況對應到棧的操作即為：1．和棧頂的左括弧不相匹配；

2．棧中并沒有左括弧等在哪里；

3．棧中還有左括弧沒有等到和它相匹配的右括弧。3.2.2、括弧匹配檢驗第21頁1．“匹配”不是“相等”。因此若在遇到左括弧時是將當前這個左括弧進棧的話，那么在遇到右括弧時必須分別不同情況進行判別。

2．和棧頂元素進行比較的前提是棧不為空。因此判別當前出現的右括弧是否和相應左括弧匹配之前有否先判別當前棧是否為空。

3．“沒有等到”即為棧不空的情況。因此在算法結束之前，要判別棧是否已為空了？

4．此外別忘了使用棧之前一定要進行初始化。注意：第22頁下面這段程序是只檢測“（”和“）”的；Staticpair(){inistack(s);ch=getchar();While(ch!=eof)do{switch(ch){case’(’:push(s,’(‘);case’)’:if(notempty(s))pop(s);elsereturn(false);}}if(empty(s))return(true);elsereturn(false);}思考：不設棧，而設一個變量count,count初值為0，遇到“（”就加1，遇到“）”就減1，如果最后count=0,則匹配，否則不匹配，可以嗎？為什么？第23頁{}[]（）的配對問題。

[（5+（2-6）+10）+6]*2[（5+（2-6）+10]+6）*2

（（5+2-6）+10）+6）*2

判斷的標準：方法：見到左括號壓棧，見到右括號彈棧，并和彈出的數據配對。

課堂練習：假設表達式結束符為#,試寫出其算法第24頁intMatchJudge(){//匹配返回1，不匹配返回0InitStack(S);

scanf(“%c”,ch);

while(ch!=“#”){if(ch==“(”||ch==“[”||ch==“{”)

push(s,ch);

if(ch==“)”）

{pop(s,e);if(e<>“(”)return0;}if(ch==“]”){pop(s,e);if(e<>“[”)return0;}if(ch==“}”){pop(s,e);if(e<>“{”)return0;}

scanf(“%c”,ch);}//whileif

StackEmpty(s)return1

elsereturn0;}//MatchJudge第25頁3.2.3行編輯程序在編輯程序中，設立一個輸入緩沖區(qū)，用于接受用戶輸入的一行字符，然后逐行存入用戶數據區(qū)。允許用戶輸入錯誤，并在發(fā)現有誤時可以及時更正。字符“#”為刪節(jié)符，刪除左邊一個可見字符。字符“@”為刪行符，刪除當前一行。用棧來處理一行，一行結束即用戶輸入‘\n’。例如：用戶輸入：whli##ilr#e(s#*s)outcha@putchar(*s=#++);則實際有效為：

while(*s)putchar(*s++);第26頁voidLineEdit(){Initstack(S);ch=getchar();while(ch!=EOF){while(ch!=EOF&&ch!=‘\n’){

switch(ch){case‘#’:Pop(s,c);case‘@’:Clearstack(s);default:Push(S,ch);}

ch=getchar();}ClearStack(s);if(ch!=eof)ch=gethar();}DestroyStack(s);}第27頁3.2.5表達式求值：

任何一個表達式都是由操作數(operand)、運算符(operator)和界限符(delimiter)組成，其中，操作數可以是常數也可以是被說明為變量或常量的標識符；運算符可以分為算術運算符、關系運算符和邏輯運算符等三類；基本界限符有左右括弧和表達式結束符等。為了敘述簡潔，在此僅限于討論只含二元運算符的算術表達式?？蓪⑦@種表達式定義為：表達式=操作數運算符操作數

操作數=簡單變量|表達式簡單變量=標識符|無符號整數算術運算的規(guī)則是：先乘除后加減、先左后右和先括弧內后括弧外。則對表達式進行運算不能按其中運算符出現的先后次序進行第28頁在計算機中，對二元表達式可以有三種不同的標識方法。

假設Exp=S1+OP+S2

則稱OP+S1+S2為表達式的前綴表示法（簡稱前綴式）

稱S1+OP+S2為表達式的中綴表示法（簡稱中綴式）

稱S1+S2+OP為表達式的后綴表示法（簡稱后綴式）

例如：

若

則它的

前綴式為：

中綴式為：

后綴式為：

后綴式：運算符放在運算數后面，運算符可沒有優(yōu)先級，式中沒有括號，這種表達式叫后綴表達式，這是波蘭的盧卡。謝維奇提出的，因此這種式子又稱為逆波蘭式。第29頁1．三式中的“操作數之間的相對次序相同”；

2．三式中的“運算符之間的的相對次序不同”；

3．//中綴式丟失了括弧信息，致使運算的次序不確定；

4．前綴式的運算規(guī)則為：連續(xù)出現的兩個操作數和在它們之前且緊靠它們的運算符構成一個最小表達式；

5．后綴式的運算規(guī)則為：

·運算符在式中出現的順序恰為表達式的運算順序；

·每個運算符和在它之前出現且緊靠它的兩個操作數構成一個最小表達式；方法：把每個運算符移到相應運算數后，再根據運算次序排列，刪除所有括號。如：2*（5-3）/7+4→253-*7/4+寫出下列中綴式的后綴式：

4+2*3-10/516-9*(4+3)2*(x+y)/(1-x)2*((x+y)-(1-x))423*+105/-16943+*-2xy+*1x-/2xy+1x--*第30頁以下就分"如何按后綴式進行運算"和"如何將原表達式轉換成后綴式"兩個問題進行討論。如何按后綴式進行運算？

可以用兩句話來歸納它的求值規(guī)則："先找運算符，后找操作數。"運算過程為：對后綴式從左向右"掃描"，遇見操作數則暫時保存，遇見運算符即可進行運算；此時參加運算的兩個操作數應該是在它之前剛剛碰到的兩個操作數，并且先出現的是第一操作數，后出現的是第二操作數。由此可見，在運算過程中保存操作數的結構應該是個棧。第31頁OperandTypeCal(OperandTypea[]){InitStack(s);i=1;while(a[i]<>’@’){if(a[i]inopnd){Push(s,a[i]);}else{Pop(s,b);Pop(s,a);Push(s,Operate(a,a[i],b));}i=i+1;}//whilereturnGetTop(s);}//program第32頁如何由原表達式轉換成后綴式？

我們先引進一個運算符的"優(yōu)先數"的概念。給每個運算符賦以一個優(yōu)先數的值，如下所列：運算符：＃（＋－×/優(yōu)先數：－101123

對原表達式中出現的每一個運算符是否即刻進行運算取決于在它后面出現的運算符，如果它的優(yōu)先數"高或等于"后面的運算，則它的運算先進行，否則就得等待在它之后出現的所有優(yōu)先數高于它的"運算"都完成之后再進行。顯然，保存運算符的結構應該是個棧，從棧底到棧頂的運算符的優(yōu)先數是從低到高的，因此它們運算的先后應是從棧頂到棧底的。第33頁從原表達式求得后綴式的規(guī)則為：

1)設立運算符棧；

2)設表達式的結束符為"#"，預設運算符棧的棧底為"#"；

3)若當前字符是操作數，則直接發(fā)送給后綴式；

4)若當前字符為運算符且優(yōu)先數大于棧頂運算符，則進棧，否則退出棧頂運算符發(fā)送給后綴式；

5)若當前字符是結束符，則自棧頂至棧底依次將棧中所有運算符發(fā)送給后綴式；

6)"("對它之前后的運算符起隔離作用，則若當前運算符為"("時進棧；

7)")"可視為自相應左括弧開始的表達式的結束符，則從棧頂起，依次退出棧頂運算符發(fā)送給后綴式直至棧頂字符為"("止。第34頁算符優(yōu)先算法：利用運算優(yōu)先關系的規(guī)定來實現對表達式的編譯或解釋執(zhí)行。表達式的組成：操作數+算符（操作符+界限符）算符優(yōu)先關系

+_*/()#+>><<<>>_>><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=將后綴式轉換和求值合并到一起，有第35頁算符優(yōu)先算法的實現1）置操作數棧為空棧，表達式起始符＃為運算符棧的棧底。2）依次讀入表達式的元素，

a.若是操作數,則進操作數棧。

b.若是運算符則同運算符棧棧頂棧元素進行優(yōu)先級比較，

b.1若棧頂元素優(yōu)先級高，則彈出該運算符，取其操作數進行相應運算，之后結果進操作數棧，再將此算符和算符新的棧頂元素比較。

b.2否則，將此運算符壓棧。

b.3否則，則是一對括號，要脫括號第36頁OperandTypeEvaluateExpression(){InitStack(OPTR);Push(OPTR,’#’);InitStack(OPND);c=getchar();while(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,OP)){Push(OPND,C);c=getchar();}elseswitch(Precede(GetTop(OPTR),c)){case‘<’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR,x);c=getchar();break;case‘>’:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//program

第37頁步驟OPTR棧OPND棧輸入字符主要操作1＃

3*(7-2)#PUSH(OPND,’3’)2＃3

*(7-2)#PUSH(OPTR,’*’)3＃*3

(7-2)#PUSH(OPTR,’(’)4＃*(3

7-2)#PUSH(OPND,’7’)5＃*(-37

-2)#PUSH(OPTR,’-’)6＃*(-37

2)#PUSH(OPND,’2’)7＃*(372

)#Operate(‘7’,’-’,’2’)8＃*(35)#POP(OPTR){去括號}9＃*35#operate(‘3’,’#’,’5’)10＃15#RETURN(GETTOP(OPND))第38頁3.3、遞歸函數的實現

在程序設計中，經常會碰到多個函數的嵌套調用。和匯編程序設計中主程序和子程序之間的鏈接和信息交換相類似，在高級語言編制的程序中，調用函數和被調用函數之間的鏈接和信息交換也是由編譯程序通過棧來實施的。

當一個函數在運行期間調用另一個函數時，在運行該被調用函數之前，需先完成三件事：將所有的實在參數、返回地址等信息傳遞給被調用函數保存；為被調用函數的局部變量分配存儲區(qū)；將控制轉移到被調用函數的入口。而從被調用函數返回調用函數之前，應該完成：

1)保存被調函數的計算結果；

2)釋放被調函數的數據區(qū)；

3)依照被調函數保存的返回地址將控制轉移到調用函數。第39頁

當多個函數嵌套調用時，由于函數的運行規(guī)則是：后調用先返回，因此各函數占有的存儲管理應實行"棧式管理"。

假設主函數調用函數A，函數A又調用函數B，顯然，在函數B運行期間主函數和函數A占用的存儲都不能被覆蓋，反之，當函數B運行結束，它所占用的存儲區(qū)便可釋放，同時因為程序控制轉移到函數A，當前程序訪問的數據自然就是函數A占用的存儲區(qū)了第40頁遞歸程序的執(zhí)行例：1voidditui(intn){2if(n>1){3printf(n);4ditui(n-1);5}//if6}//ditui1234561234Ditui(4)Ditui(5)1234Ditui(3)1234Ditui(2)1256Ditui(1)565656輸出2輸出3輸出4輸出5第41頁1voidditui2(intn){2if(n>1){3ditui(n-1);4printf(n);5}//if6}//ditui21234561234Ditui(4)Ditui(5)1234Ditui(3)1234Ditui(2)1256Ditui(1)565656輸出2輸出3輸出4輸出5第42頁遞歸函數的實現

一個遞歸函數的運行過程類似于多個函數的嵌套調用，差別僅在于"調用函數和被調用函數是同一個函數"。為了保證"每一層的遞歸調用"都是對"本層"的數據進行操作，在執(zhí)行遞歸函數的過程中需要一個"遞歸工作棧"。它的作用是:1、將遞歸調用時的實在參數和函數返回地址傳遞給下一層執(zhí)行的遞歸函數；2、保存本層的參數和局部變量，以便從下一層返回時重新使用它們。

遞歸執(zhí)行過程中所占用的數據區(qū)，稱之為遞歸工作棧。

每一層的遞歸參數等數據合成一個記錄，稱之為遞歸工作記錄。

棧頂記錄指示當前層的執(zhí)行情況，稱之為當前活動記錄。

遞歸工作棧的棧頂指針，稱之為當前環(huán)境指針。第43頁

在此，稱調用遞歸函數的主函數為"第0層"，則從主函數調用遞歸函數被稱為進入遞歸函數的"第1層"，從遞歸函數的"第i層"遞歸調用本函數被稱為進入遞歸函數的"第i+1層"。顯然，當遞歸函數執(zhí)行到第i層時，從第1層到第i-1層的數據都必須被保存下來，以便一層一層退回時繼續(xù)使用。遞歸函數執(zhí)行過程中每一層所占用的內存數據區(qū)合起來就是一個"遞歸工作棧"。下面用漢諾塔問題來說明遞歸程序和堆棧的使用設主程序中有如下的調用語句：

inti; ….10 hanoi(3,a,b,c);voidhanoi(intn,charx,chary,charz);第44頁voidhanoi(intn,charx,chary,charz)

//將塔座x上按直徑由小到大且至上而下編號為1至n

//的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。

1{

2

if(n==1)

3

{

move(x,1,z);

//將編號為1的圓盤從x移到z

}

4

else {

5

hanoi(n-1,x,z,y); //將x上編號為1至n-1的圓盤移到y,z作輔助塔

6

move(x,n,z);

//將編號為n的圓盤從x移到z

7

hanoi(n-1,y,x,z); //將y上編號為1至n-1的圓盤移到z,x作輔助塔

}

}

第45頁(3,a,b,c)(2,a,b,c)(1,a,b,c)a→b(1,c,a,b)a→c(1,b,c,a)(2,b,a,c)b→c(1,a,b,c)第46頁隊列的定義：一種運算受限的線性表。它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。例如：排隊購物。操作系統中的作業(yè)排隊。先進入隊列的成員總是先離開隊列。因此隊列亦稱作先進先出(FirstInFirstOut)的線性表，簡稱FIFO表。當隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2,…an之后，a1是隊頭元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,…an，也就是說隊列的修改是依先進先出的原則進行的。3.4隊列

3.4.1抽象數據類型隊列的定義出隊入隊隊頭隊尾a1,a2,…an第47頁隊列的抽象數據類型定義：ADTQueue{數據對象：D={ai|ai∈ElemSet,i=1,2,..n,n>=0}數據關系：R1={<ai-1,ai>|ai-1,ai∈D,I=2,…n}基本操作：InitQueue(&Q);DestoryQueue(&Q);ClearQueue(&Q);QueueEmpty(Q);QueueLength(Q);GetHead(Q,&e);EnQueue(&Q,e);DeQueue(&Q,&e);QueueTraverse(Q,visit())}第48頁3.4.2隊列的存儲表示和操作的實現

鏈隊列鏈隊列是隊列的鏈式存儲結構，其結構示意圖如下所示：僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個尾指針，指向鏈表的最后一個結點。于是，一個鏈隊列由一個頭指針Q.front和一個尾指針Q.rear共同確定。Q.front==Q.rear時，為空鏈隊列第49頁

typedefSLinkQueuePtr;//鏈隊列的結點結構和單鏈表相同

typedefstruct{

QueuePtrfront;//隊列的頭指針

QueuePtrrear;//隊列的尾指針

intlength;

//隊列元素個數

}Queue;

//鏈隊列//基本操作接口（函數聲明）

voidInitQueue(Queue&Q);

//構造一個空隊列Q

voidDestroyQueue(Queue&Q);

//銷毀隊列Q，Q不再存在

voidClearQueue(Queue&Q);//將Q置為空隊列

boolQueueEmpty(QueueQ);//若隊列Q為空隊列，則返回TRUE，否則返回FALSE

intQueueLength(QueueQ);//返回隊列Q中元素個數，即隊列的長度

boolGetHead(QueueQ,ElemType&e);//若隊列不空，則用e返回Q的隊列頭元素，并返回TRUE；否則返回FALSE

voidEnQueue(Queue&Q,ElemTypee);

//在當前隊列的尾元素之后插入元素e為新的隊列尾元素

boolDeQueue(Queue&Q,ElemType&e);

//若隊列不空，則刪除當前隊列Q中的頭元素，用e返回其值，并返回TRUE；

//否則返回FALSE

voidQueueTraverse(QueueQ,void(*visit(ElemType))

//依次對Q的每個元素調用函數visit()，一旦visit()失敗，則操作失敗。鏈隊列的類型定義：第50頁voidInitQueue(Queue&Q)

{//構造一個空隊列Q

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(1);

//存儲分配失敗

Q.front->next=NULL;

Q.length=0;

}voidEnQueue(Queue&Q,ElemTypee)

{//在當前隊列的尾元素之后，插入元素e為新的隊列尾元素

s=(QueuePtr)malloc(sizeof(QNode));

if(!s)exit(1);

//存儲分配失敗

s->data=e;

s->next=NULL;

Q.rear->next=s;

//修改尾結點的指針

Q.rear=s;

//移動隊尾指針

++Q.length;

//隊列長度增1

}第51頁boolDeQueue(Queue&Q,ElemType&e)

{//若隊列不空，則刪除當前隊列Q中的頭元素，用e返回其值，

//并返回TRUE；否則返回FALSE

if(Q.front==Q.rear)

//鏈隊列中只有一個頭結點

returnFALSE;

p=Q.front->next;

e=p->data;

//返回被刪元素

Q.front->next=p->next;

//修改頭結點指針

if(Q.rear==p)Q.rear=Q.front;

deletep;

//釋放被刪結點

--Q.length;

returnTRUE;

}//DeQueue

它是否多余？能否刪去？由于一般情況下，出隊列的操作只涉及隊頭元素，因此不需要修改隊尾指針，但當鏈隊列中只有一個數據元素時，隊頭元素恰好也是隊尾元素，當它被刪除之后，隊尾指針就"懸空"了，待下次再做入隊操作時，就要產生指針的"懸空訪問"的錯誤，因此在這種情況下必須同時修改尾指針。第52頁和順序棧相類似，在利用順序分配存儲結構實現隊列時，除了用一維數組描述隊列中數據元素的存儲區(qū)域之外，尚需設立兩個指針front和rear分別指示“隊頭”和“隊尾”的位置。為了敘述方便，在此約定：初始化建空隊列時，令front=rear=0，每當插入一個新的隊尾元素后，尾指針front增1；每當刪除一個隊頭元素之后，頭指針增1。因此，在非空隊列中，頭指針始終指向隊頭元素，而尾指針指向隊尾元素的"下一個"位置。如下圖所示。3.4.3循環(huán)隊列

第53頁非循環(huán)隊列：如何判斷空隊?

如何判斷滿隊?由于隊首的移動特征，實際采用循環(huán)隊列。rearfront空隊front非空非滿隊1rearABCC滿隊DECfront非空非滿隊2Drearrearfront非循環(huán)隊列：第54頁假設在這之后又有兩個元素f和g相繼入隊列，而隊列中的元素b和c又相繼出隊列。則隊頭指針指向元素d，隊尾指針則指到數組"之外"的位置上去了，致使下一個入隊操作無法進行(請注意此時隊列空間并未滿)。為此，設想這個數組的存儲空間是個"環(huán)"，認定"7"的下一個位置是"0"。如下圖所示。第55頁循環(huán)隊列：Maxsize-101frontrear這種循環(huán)意義下的加1操作可以描述為：if(i+1==MAXSIZE)i=0;elsei++;

利用模運算可簡化為：i=(i+1)%MAXSIZE第56頁Maxsize-1frontrearJ3J4J5012345Maxsize-1frontJ3J4J5J6J7J8rear循環(huán)隊列：空隊Q.rear==Q.front;

滿隊？第57頁處理方法（1）另設標志位以區(qū)別隊列是“空”還是“滿”（2）少用一個元素空間，約定以“隊列頭指針在環(huán)狀隊列尾指針的下一位置”作為隊列“滿”狀態(tài)的標志。(Q.rear+1)%MAXSIZE==Q.frontQ.rear指向入隊時下一個元素的存放位置（未有）Q.front指向出隊時下一個元素的存放位置（已有）第58頁循環(huán)隊列的結構定義如下：

typedefstruct{

ElemType*elem;

//存儲空間基址

intrear;

//隊尾指針

intfront;

//隊頭指針

intqueuesize;

//允許的最大存儲空間，以元素為單位

}Queue;voidInitQueue(Queue&Q，intmaxsize)

{

//構造一個最大存儲空間為maxsize的空隊列Q

Q.elem=malloc(maxsize*sizeof(ElemType);//為循環(huán)隊列分配存儲空間

if(!Q.elem)exit(1);

//存儲分配失敗

Q.queuesize=maxsize;

Q.front=Q.rear=0;

}//InitQueue第59頁boolDeQueue(Queue&Q,ElemType&e)

{

//若隊列不空，則刪除當前隊列Q中的頭元素，用e返回其值

//并返回TRUE；否則返回FALSE

if(Q.front==Q.rear)

returnFALSE;

e=Q.elem[Q.front];

Q.front=(Q.front+1)%Q.queuesize;

returnTRUE;

}判別循環(huán)隊列為"空"的條件應該是什么？在隊列初始化的函數中，設置隊頭和隊尾指針均為0，那么能否由"隊頭指針為0"來作為隊列空的判別條件呢？顯然是不對的，由前面兩個插圖的例子就可見，由于隊頭指針和隊尾指針都是"單方向"移動的，因此當隊頭指針"追上"隊尾指針時，說明所有曾經插入隊列的元素都已經出列，所以隊列變空的條件應該是"兩個指針指向循環(huán)隊列中的同一位置"。第60頁boolEnQueue(Queue&Q,ElemTypee)

{

//若當前隊列不滿，這在當前隊列的尾元素之后，

//插入元素e為新的隊列尾元素,并返回TRUE,否則返回FALSE

if((Q.rear+1)%Q.queuesize==Q.front)

returnFALSE;

Q.elem[Q.rear]=e;

Q.rear=(Q.rear+1)%Q.queuesize;

returnTRUE;

}由于順序存儲結構是一次性地分配空間，因此在入隊列的操作中首先應該判別當前隊列是否已經"滿"了，那么隊列滿的判別條件又是什么呢？

當隊尾指針"追上"隊頭指針時，隊列就"滿"了。盡管它和上面我們說的隊列"變空"時的指針變化趨勢不同，但對計算機程序來說，它只能判別一個靜態(tài)的"狀態(tài)"，因此不能再以"兩個指針相等"來作為隊列滿的條件。當然可以為循環(huán)隊列另設一個"滿/空"的標記以示區(qū)別。在此采用的是另一種方法，即犧牲一個元素單位的空間，以"隊列指針即將追上隊頭指針"作為"隊列滿"的判別條件。因此對循環(huán)隊列來說，它實際可以存放元素的"最大值"要比所設的最大值小1。第61頁intQueueLength(QueueQ)

{

//返回隊列Q中元素個數，即隊列的長度

return((Q.rear-Q.front+Q.queuesize)%Q.queuesize);

}

因為在循環(huán)隊列中，隊尾指針的"數值"有可能比隊頭指針的數值小，因此為避免在求隊列長度兩者相減時出現負值的情況，在作取模運算之前先加上一個最大容量的值。第62頁練習簡述以下算法的功能

voida3(queue&q){stacks;InitStack(s);intd;while(!QueueEmpty(q)){DeQueue(q,d);push(s,d);}while(!StackEmpty(s)){pop(s,d);EnQueue(q,d);}}第63頁1、編寫一個打印二項式系數表（即楊輝三角）的算法。

111

1

2

1

1

3

3

1

1

4

6

4

1

……

這個問題的程序可以有很多種寫法，一種最直接的想法是利用兩個數組，其中一個存放已經計算得到的第k行的值，然后輸出第k行的值同時計算第k+1行的值。如此寫得的程序顯然結構清晰，但需要兩個輔助數組的空間，并且這兩個數組在計算過程中需相互交換。如若引入“循環(huán)隊列”，則可以省略一個數組的輔助空間，而且可以利用隊列的操作將“交換移動等"屏蔽起來，使程序結構變得清晰，容易被人理解。如果要求計算并輸出楊輝三角前n行的值，則隊列的最大空間應為n+2。假設隊列中已存有第k行的計算結果，并為了計算方便，在兩行之間添加一個"0"作為行界值，則在計算第k+1行之前，頭指針正指向第k行的"0"，而尾元素為第k+1行的"0"。由此從左到右依次輸出第k行的值，并將計算所得的第k+1行的值插入隊列的基本操作為：第64頁寫出完整的算法的話，還需要補充哪些細節(jié)呢？1.輸出e是有條件的，對嗎？即行末的"0"不需要輸出；

2.一行計算結束之后需要補一個"0"，這個"0"值既是剛剛計算完的這行的"尾0"，又是即將開始計算的下一行的"頭0"；

3.其它初始化和結尾(輸出最后一行)等。do{DeQueue(Q,s);

//s為二項式系數表第k行中“左上方”的值

GetHead(Q,e);

//e為二項式系數表第k行中“右上方”的值

cout<<e；//輸出e的值

EnQueue(Q,s+e);

//計算所得第k+1行的值入隊列

}while(e!=0);第65頁voidyanghui(intn)

{

//打印輸出楊輝三角的前n(n>0)行

QueueQ;

for(i=1;i<=n;i++)

cout<<'';

cout<<'1'<<endl;

//在中心位置輸出楊輝三角最頂端的"1"

InitQueue(Q,n+2);

//設置最大容量為n+2的空隊列

EnQueue(Q,0);

//添加行界值

EnQueue(Q,1);EnQue