數(shù)據(jù)結(jié)構(gòu)（第2版）（C語(yǔ)言實(shí)現(xiàn)）課件：棧和隊(duì)列

棧和隊(duì)列

棧是一種操作受限的線性表。棧具有線性表的結(jié)構(gòu)特點(diǎn)，即每一個(gè)元素只有一個(gè)前驅(qū)元素和后繼元素（除了第一個(gè)元素和最后一個(gè)元素外），但它只允許在表的一端進(jìn)行插入和刪除操作。隊(duì)列也是一種操作受限的線性表。隊(duì)列在操作系統(tǒng)和事務(wù)管理等軟件設(shè)計(jì)中應(yīng)用廣泛，如鍵盤輸入緩沖區(qū)問(wèn)題就是利用隊(duì)列的思想實(shí)現(xiàn)的。

本章重點(diǎn)和難點(diǎn)：

1、棧的順序表示與算法實(shí)現(xiàn)

2、棧的鏈?zhǔn)奖硎九c算法實(shí)現(xiàn)

3、求算術(shù)表達(dá)式的值4、遞歸的消除3.1棧的表示與實(shí)現(xiàn)3.1.1棧的表示與實(shí)現(xiàn)棧（stack），也稱為堆棧，它是限定僅在表尾進(jìn)行插入和刪除操作的線性表。對(duì)棧來(lái)說(shuō)，表尾（允許操作的一端）稱為棧頂（top），另一端稱為棧底（bottom）。棧頂是動(dòng)態(tài)變化的，它由一個(gè)稱為棧頂指針（top）的變量指示。當(dāng)表中沒有元素時(shí)，稱為空棧。棧的插入操作稱為入?；蜻M(jìn)棧，刪除操作稱為出?；蛲藯！?.1棧的表示與實(shí)現(xiàn)

在棧S=(a1,a2,…,an)中，a1稱為棧底元素，an稱為棧頂元素，由棧頂指針top指示。棧中的元素按照a1，a2，…，an的順序進(jìn)棧，當(dāng)前的棧頂元素為an。如圖所示。最先進(jìn)棧的元素一定是棧底元素，最后進(jìn)棧的元素一定是棧頂元素。每次刪除的元素是棧頂元素，也就是最后進(jìn)棧的元素。因此，棧是一種后進(jìn)先出（lastinfirstout，簡(jiǎn)稱LIFO）的線性表。3.1棧的表示與實(shí)現(xiàn)

若將元素a、b、c和d依次入棧，最后將棧頂元素出棧，棧頂指針top的變化情況如圖所示。3.1棧的表示與實(shí)現(xiàn)3.1.2棧的抽象數(shù)據(jù)類型

1．?dāng)?shù)據(jù)對(duì)象集合棧的數(shù)據(jù)對(duì)象集合為{a1，a2，…，an}，每個(gè)元素都有相同的類型DataType。棧中數(shù)據(jù)元素之間是一對(duì)一的關(guān)系。棧具有線性表的特點(diǎn)：除了第一個(gè)元素a1外，每一個(gè)元素有且只有一個(gè)直接前驅(qū)元素，除了最后一個(gè)元素an外，每一個(gè)元素有且只有一個(gè)直接后繼元素。3.1棧的表示與實(shí)現(xiàn)2．基本操作集合（1）InitStack(&S)：初始化操作，建立一個(gè)空棧S。（2）StackEmpty(S)：若棧S為空，返回1，否則返回0。（3）GetTop(S,&e)：返回棧S的棧頂元素給e。（4）PushStack(&S,e)：在棧S中插入元素e，使其成為新的棧頂元素。（5）PopStack(&S,&e)：刪除棧S的棧頂元素，并用e返回其值。（6）StackLength(S)：返回棧S的元素個(gè)數(shù)。（7）ClearStack(S)：清空棧S。3.1棧的表示與實(shí)現(xiàn)3.1.3順序棧

1.棧的順序存儲(chǔ)結(jié)構(gòu)

采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧。順序棧是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，可利用C語(yǔ)言中的數(shù)組作為順序棧的存儲(chǔ)結(jié)構(gòu)，同時(shí)附設(shè)一個(gè)棧頂指針top，用于指向順序棧的棧頂元素。當(dāng)top=0時(shí)表示空棧。棧的順序存儲(chǔ)結(jié)構(gòu)類型描述如下：

#defineStackSize100typedefstruct{DataTypestack[StackSize];inttop;}SeqStack;3.1棧的表示與實(shí)現(xiàn)

當(dāng)棧中元素已經(jīng)有StackSize個(gè)時(shí)，稱為棧滿。如果繼續(xù)進(jìn)棧操作則會(huì)產(chǎn)生溢出，稱為上溢。對(duì)空棧進(jìn)行刪除操作，稱為下溢。順序棧的結(jié)構(gòu)如圖所示。元素a、b、c、d、e、f、g、h依次進(jìn)棧后，a為棧底元素，h為棧頂元素。在實(shí)際操作中，棧頂指針指向棧頂元素的下一個(gè)位置。順序棧涉及的一些基本操作如下：（1）在初始化棧時(shí)，將棧頂指針置為0，即令S.top=0。（2）判斷棧空條件為S.top==0，棧滿條件為S.top==StackSize-1。（3）棧的長(zhǎng)度（即棧中元素個(gè)數(shù)）為S.top。（4）進(jìn)棧操作時(shí)，先判斷棧是否已滿，若未滿，將元素壓入棧中，即S.stack[S.top]=e，然后使棧頂指針加1，即S.top++。出棧操作時(shí)，先判斷棧是否為空，若不為空，使棧頂指針減1，即S.top--，然后元素出棧，即e=S.stack[S.top]。3.1棧的表示與實(shí)現(xiàn)2順序棧的基本運(yùn)算（1）初始化棧。voidInitStack(SeqStack*S)/*初始化棧*/{S->top=0; /*把棧頂指針置為0*/}（2）判斷棧是否為空。intStackEmpty(SeqStackS)/*判斷棧是否為空，棧為空返回1，否則返回0*/{if(S.top==0) /*如果棧頂指針top為0*/return1; /*返回1*/else /*否則*/return0; /*返回0*/}3.1棧的表示與實(shí)現(xiàn)（3）取棧頂元素。

intGetTop(SeqStackS,DataType*e){if(S.top<=0) /*如果棧為空*/{printf(“棧已經(jīng)空!\n”);return0;}else /*否則*/{*e=S.stack[S.top-1]; /*在取棧頂元素*/return1;}}3.1棧的表示與實(shí)現(xiàn)（4）將元素e入棧。

intPushStack(SeqStack*S,DataTypee)/*將元素e進(jìn)棧，元素進(jìn)棧成功返回1，否則返回0.*/{if(S->top>=StackSize) /*如果棧已滿*/{printf(“棧已滿，不能將元素進(jìn)棧！\n”);return0;}else /*否則*/{S->stack[S->top]=e; /*元素e進(jìn)棧*/S->top++; /*修改棧頂指針*/return1;}}3.1棧的表示與實(shí)現(xiàn)（5）將棧頂元素出棧。

intPopStack(SeqStack*S,DataType*e){if(S->top==0) /*如果棧為空*/{printf(“棧中已經(jīng)沒有元素，不能進(jìn)行出棧操作!\n”);return0;}else /*否則*/{S->top--; /*先修改棧頂指針，即出棧*/*e=S->stack[S->top]; /*將出棧元素賦給e*/return1;}}3.1棧的表示與實(shí)現(xiàn)（6）求棧的長(zhǎng)度。

intStackLength(SeqStackS)/*求棧的長(zhǎng)度*/{returnS.top;}（7）清空棧。

voidClearStack(SeqStack*S)/*清空棧*/{S->top=0; /*將棧頂指針置為0*/}3.1棧的表示與實(shí)現(xiàn)3．棧的共享在使用順序棧時(shí)，因?yàn)闂？臻g的大小難以準(zhǔn)確估計(jì)，可能會(huì)出現(xiàn)有的棧還有空閑空間。為了能充分利用棧的空間，可以讓多個(gè)棧共享一個(gè)足夠大的連續(xù)存儲(chǔ)空間，通過(guò)利用棧頂指針能靈活移動(dòng)的特性，使多個(gè)棧存儲(chǔ)空間互相補(bǔ)充，存儲(chǔ)空間得到有效利用，這就是棧的共享。3.1棧的表示與實(shí)現(xiàn)

共享?xiàng)５臄?shù)據(jù)結(jié)構(gòu)類型描述如下。

typedefstruct{DataTypestack[StackSize];inttop[2];}SSeqStack;

其中，top[0]和top[1]分別是兩個(gè)棧的棧頂指針。用一維數(shù)組表示的共享?xiàng)Ｈ鐖D所示。3.1棧的表示與實(shí)現(xiàn)（1）初始化棧。voidInitStack(SSeqStack*S)/*共享?xiàng)５某跏蓟?/{S->top[0]=0;S->top[1]=StackSize-1;}3.1棧的表示與實(shí)現(xiàn)（2）取棧頂元素。intGetTop(SSeqStackS,DataType*e,intflag)/*取棧頂元素。將棧頂元素值返回給e，并返回1表示成功；否則返回0表示失敗。*/{ switch(flag) { case1: /*為1，表示要取左端棧的棧頂元素*/ if(S.top[0]==0) return0; *e=S.stack[S.top[0]-1]; break; case2: /*為2，表示要取右端棧的棧頂元素*/ if(S.top[1]==StackSize-1) return0; *e=S.stack[S.top[1]+1]; break; default: return0; } return1;}3.1棧的表示與實(shí)現(xiàn)（3）將元素e入棧。intPushStack(SSeqStack*S,DataTypee,intflag)/*將元素e入共享?xiàng)?。進(jìn)棧成功返回1，否則返回0*/{if(S->top[0]==S->top[1]) /*如果共享?xiàng)Ｒ褲M*/return0; /*返回0，進(jìn)棧失敗*/switch(flag){case1: /*當(dāng)flag為1，表示將元素進(jìn)左端的棧*/S->stack[S->top[0]]=e; /*元素進(jìn)棧*/S->top[0]++; /*修改棧頂指針*/break;case2: /*當(dāng)flag為2，表示將元素要進(jìn)右端的棧*/S->stack[S->top[1]]=e; /*元素進(jìn)棧*/S->top[1]--; /*修改棧頂指針*/break;default:return0;}return1; /*返回1，進(jìn)棧成功*/}3.1棧的表示與實(shí)現(xiàn)（4）將棧頂元素出棧。

intPopStack(SSeqStack*S,DataType*e,intflag){switch(flag) /*在出棧操作之前，判斷哪個(gè)棧要進(jìn)行出棧操作*/{case1: /*為1，表示左端的棧需要出棧操作*/if(S->top[0]==0) /*左端的棧為空*/return0; /*返回0，出棧操作失敗*/S->top[0]--; /*修改棧頂指針，元素出棧操作*/*e=S->stack[S->top[0]]; /*將出棧的元素賦給e*/break;case2: /*為2，表示右端的棧需要出棧操作*/if(S->top[1]==StackSize-1) /*右端的棧為空*/return0; /*返回0，出棧操作失敗*/S->top[1]++; /*修改棧頂指針，元素出棧操作*/*e=S->stack[S->top[1]]; /*將出棧的元素賦給e*/break;default:return0;}return1;/*返回1，出棧操作成功*/}3.1棧的表示與實(shí)現(xiàn)（5）判斷棧是否為空。

intStackEmpty(SSeqStackS,intflag){ switch(flag) { case1: /*為1，表示判斷左端的棧是否為空*/ if(S.top[0]==0) return1; break; case2: /*為2，表示判斷右端的棧是否為空*/ if(S.top[1]==StackSize-1) return1; break; default:printf(“輸入的flag參數(shù)錯(cuò)誤!”); return-1; } return0;}3.1棧的表示與實(shí)現(xiàn)

在順序棧中，由于順序存儲(chǔ)結(jié)構(gòu)需要事先靜態(tài)分配，而存儲(chǔ)規(guī)模往往又難以確定，如果棧空間分配過(guò)小，可能會(huì)造成溢出；如果棧空間分配過(guò)大，又造成存儲(chǔ)空間浪費(fèi)。1棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組不一定連續(xù)的存儲(chǔ)單元來(lái)存放棧中的數(shù)據(jù)元素的。一般來(lái)說(shuō)，當(dāng)棧中數(shù)據(jù)元素的數(shù)目變化較大或不確定時(shí)，使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)作為棧的存儲(chǔ)結(jié)構(gòu)是比較合適的。人們將用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的棧稱為鏈棧或鏈?zhǔn)綏！?.1棧的表示與實(shí)現(xiàn)

鏈棧通常用單鏈表表示。插入和刪除操作都在棧頂指針的位置進(jìn)行，這一端稱為棧頂，通常由棧頂指針top指示。為了操作上的方便，通常在鏈棧中設(shè)置一個(gè)頭結(jié)點(diǎn)，用棧頂指針top指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的指針指向鏈棧的第一個(gè)結(jié)點(diǎn)。元素a、b、c、d依次入棧的鏈棧如圖所示。3.1棧的表示與實(shí)現(xiàn)

棧頂指針top始終指向頭結(jié)點(diǎn)，最先入棧的元素在鏈棧的棧底，最后入棧的元素成為棧頂元素。由于鏈棧的操作都是在鏈表的表頭位置進(jìn)行，因而鏈棧的基本操作的時(shí)間復(fù)雜度均為O(1)。鏈棧的結(jié)點(diǎn)類型描述如下：

typedefstructnode{DataTypedata;structnode*next;}LStackNode,*LinkStack;3.1棧的表示與實(shí)現(xiàn)

2鏈棧的基本運(yùn)算（1）初始化鏈棧。voidInitStack(LinkStack*top)/*鏈棧的初始化*/{if((*top=(LinkStack)malloc(sizeof(LStackNode)))==NULL)exit(-1);(*top)->next=NULL;/*將鏈棧的頭結(jié)點(diǎn)指針域置為空*/}3.1棧的表示與實(shí)現(xiàn)（2）判斷鏈棧是否為空。

intStackEmpty(LinkStacktop)/*判斷鏈棧是否為空*/{if(top->next==NULL) /*如果頭結(jié)點(diǎn)的指針域?yàn)榭?/return1; /*返回1*/else /*否則*/return0; /*返回0*/}3.1棧的表示與實(shí)現(xiàn)

（3）將元素e入棧。先動(dòng)態(tài)生成一個(gè)結(jié)點(diǎn)，用p指向該結(jié)點(diǎn)，將元素e值賦給*p結(jié)點(diǎn)的數(shù)據(jù)域，然后將新結(jié)點(diǎn)插入到鏈表的第一個(gè)結(jié)點(diǎn)之前。把新結(jié)點(diǎn)插入到鏈表中分為兩個(gè)步驟：①p->next=top->next；②top->next=p。進(jìn)棧操作如圖所示。3.1棧的表示與實(shí)現(xiàn)將元素e入棧的算法實(shí)現(xiàn)如下。intPushStack(LinkStacktop,DataTypee){LStackNode*p; /*定義指針p，指向新生成的結(jié)點(diǎn)*/if((p=(LStackNode*)malloc(sizeof(LStackNode)))==NULL){printf(“內(nèi)存分配失敗!”);exit(-1);}p->data=e; /*將e賦給p指向的結(jié)點(diǎn)數(shù)據(jù)域*/p->next=top->next; /*指針p指向頭結(jié)點(diǎn)*/top->next=p; /*棧頂結(jié)點(diǎn)的指針域指向新插入的結(jié)點(diǎn)*/return1;}3.1棧的表示與實(shí)現(xiàn)（4）將棧頂元素出棧。先判斷棧是否為空，如果棧為空，返回0表示出棧操作失?。环駝t，將棧頂元素出棧，并將棧頂元素值賦給e，最后釋放結(jié)點(diǎn)空間，返回1表示出棧操作成功。出棧操作如圖4.9所示。3.1棧的表示與實(shí)現(xiàn)將棧頂元素出棧的算法實(shí)現(xiàn)如下。intPopStack(LinkStacktop,DataType*e){LStackNode*p;p=top->next;if(!p) /*判斷鏈棧是否為空*/{printf(“棧已空”);return0;}top->next=p->next; /*將棧頂結(jié)點(diǎn)與鏈表斷開，即出棧*/*e=p->data; /*將出棧元素賦值給e*/free(p); /*釋放p指向的結(jié)點(diǎn)*/return1;}

（5）取棧頂元素。

intGetTop(LinkStacktop,DataType*e)/*取棧頂元素。取棧頂元素成功返回1，否則返回0*/{LStackNode*p;p=top->next; /*指針p指向棧頂結(jié)點(diǎn)*/if(!p)/*如果棧為空*/{printf(“棧已空”);return0;}*e=p->data; /*將p指向的結(jié)點(diǎn)元素賦值給e*/return1;}3.1棧的表示與實(shí)現(xiàn)3.1棧的表示與實(shí)現(xiàn)6）求棧的長(zhǎng)度。intStackLength(LinkStacktop){LStackNode*p;intcount=0; /*定義一個(gè)計(jì)數(shù)器，并初始化為0*/p=top; /*p指向棧頂指針*/while(p->next!=NULL) /*如果棧中還有結(jié)點(diǎn)*/{p=p->next; /*依次訪問(wèn)棧中的結(jié)點(diǎn)*/count++; /*每次找到一個(gè)結(jié)點(diǎn)，計(jì)數(shù)器累加1*/}returncount; /*返回棧的長(zhǎng)度*/}3.1棧的表示與實(shí)現(xiàn)（7）銷毀鏈棧。voidDestroyStack(LinkStacktop){LStackNode*p,*q;p=top;while(!p) /*如果棧還有結(jié)點(diǎn)*/{q=p; /*q就是要釋放的結(jié)點(diǎn)*/p=p->next; /*p指向下一個(gè)結(jié)點(diǎn)，即下一次要釋放的結(jié)點(diǎn)*/free(q); /*釋放q指向的結(jié)點(diǎn)空間*/}}3.1.1數(shù)制轉(zhuǎn)換

【例3.1】利用棧的基本操作實(shí)現(xiàn)將十進(jìn)制數(shù)1568轉(zhuǎn)換為對(duì)應(yīng)的八進(jìn)制數(shù)。

【分析】進(jìn)制轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題。根據(jù)我們掌握的C語(yǔ)言知識(shí)，我們可以采用輾轉(zhuǎn)相除法實(shí)現(xiàn)將十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)。將1568轉(zhuǎn)換為八進(jìn)制數(shù)的過(guò)程如圖所示。3.2棧的應(yīng)用

轉(zhuǎn)換后的八進(jìn)制數(shù)為(1568)8。每次不斷利用被除數(shù)除以8得到商數(shù)后，記下余數(shù)，又將商數(shù)作為新的被除數(shù)繼續(xù)除以8，直到商數(shù)為0為止，把得到的余數(shù)排列起來(lái)就是轉(zhuǎn)換后的八進(jìn)制數(shù)。依據(jù)此原理，得到十進(jìn)制數(shù)N轉(zhuǎn)換為八進(jìn)制的算法如下：（1）將N除以8，記下其余數(shù)；（2）判斷商是否為零，如果為零，結(jié)束程序；否則，將商送N，轉(zhuǎn)到（1）繼續(xù)執(zhí)行。得到的位序正好與八進(jìn)制數(shù)的位序相反，這恰好可利用棧的“后進(jìn)先出”特性，先把得到的余數(shù)序列放入棧保存，最后依次出棧得到八進(jìn)制數(shù)。4.3棧的鏈?zhǔn)奖硎九c實(shí)現(xiàn)3.2.2行編輯程序

試?yán)脳５摹昂筮M(jìn)先出”思想，編寫一個(gè)行編輯程序，前一個(gè)字符輸入有誤時(shí)，輸入’#’消除。當(dāng)輸入的一行有誤時(shí)，輸入’@’消除當(dāng)前行的字符序列。voidLineEdit(){

SeqStackS;charch;DataTypee;DataTypea[50];inti,j=0;

InitStack(&S);

printf("輸入字符序列(‘#’使前一個(gè)字符無(wú)效，’@’使當(dāng)前行的字符無(wú)效).\n");

ch=getchar();

while(ch!='\n')

{

3.2棧的應(yīng)用3.2棧的應(yīng)用

switch(ch)

{

case'#':/*如果當(dāng)前輸入字符是'#'，且棧不空，則將棧頂字符出棧*/

if(!StackEmpty(S))

PopStack(&S,&ch);

break;

case'@': /*如果當(dāng)前輸入字符是'@'，則將棧清空*/

ClearStack(&S);

break;

default:/*如果當(dāng)前輸入字符不是'#'和'@'，則將字符進(jìn)棧*/

PushStack(&S,ch);

}

ch=getchar(); /*讀入下一個(gè)字符*/} while(!StackEmpty(S)) {

PopStack(&S,&e);/*將字符出棧，并存入數(shù)組a中*/ a[j++]=e; } for(i=j-1;i>=0;i--) /*輸出正確的字符序列*/ printf("%c",a[i]); printf("\n");

ClearStack(&S);}

3.2.3求算術(shù)表達(dá)式的值表達(dá)式求值是程序設(shè)計(jì)編譯中的基本問(wèn)題，它的實(shí)現(xiàn)是棧應(yīng)用的一個(gè)典型例子。本節(jié)給大家介紹一種簡(jiǎn)單并廣為使用的算法，被稱之為算符優(yōu)先法。計(jì)算機(jī)編譯系統(tǒng)利用棧的“后進(jìn)先出”特性把人們便于理解的表達(dá)式翻譯成計(jì)算機(jī)能夠正確理解的表示序列。一個(gè)算術(shù)表達(dá)式是由操作數(shù)、運(yùn)算符和分界符組成。為了簡(jiǎn)化問(wèn)題，我們假設(shè)算術(shù)運(yùn)算符僅由加、減、乘、除四種運(yùn)算符和左、右圓括號(hào)組成。3.2棧的應(yīng)用

例如，一個(gè)算術(shù)表達(dá)式為

a-(b+c*d)/e

這種算術(shù)表達(dá)式中的運(yùn)算符總是出現(xiàn)在兩個(gè)操作數(shù)之間，這種算術(shù)表達(dá)式被稱為中綴表達(dá)式。計(jì)算機(jī)編譯系統(tǒng)在計(jì)算一個(gè)算術(shù)表達(dá)式之前，要將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后對(duì)后綴表達(dá)式進(jìn)行計(jì)算。后綴表達(dá)式就是算術(shù)運(yùn)算符出現(xiàn)在操作數(shù)之后，并且不含括號(hào)。計(jì)算機(jī)在求算術(shù)表達(dá)式的值時(shí)分為兩個(gè)步驟：（1）將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式；（2）依據(jù)后綴表達(dá)式計(jì)算表達(dá)式的值。3.2棧的典型應(yīng)用1．將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式要將一個(gè)算術(shù)表達(dá)式的中綴形式轉(zhuǎn)化為相應(yīng)的后綴形式，首先了解下算術(shù)四則運(yùn)算的規(guī)則。算術(shù)四則運(yùn)算的規(guī)則是：（1）先乘除，后加減；（2）同級(jí)別的運(yùn)算從左到右進(jìn)行計(jì)算；（3）先括號(hào)內(nèi)，后括號(hào)外。上面的算術(shù)表達(dá)式轉(zhuǎn)換為后綴表達(dá)式為：

abcd*+e/-3.2棧的應(yīng)用

轉(zhuǎn)換后的后綴表達(dá)式具有以下兩個(gè)特點(diǎn)：（1）后綴表達(dá)式與中綴表達(dá)式的操作數(shù)出現(xiàn)順序相同，只是運(yùn)算符先后順序改變了；（2）后綴表達(dá)式不出現(xiàn)括號(hào)。正因?yàn)楹缶Y表達(dá)式的以上特點(diǎn)，所以編譯系統(tǒng)不必考慮運(yùn)算符的優(yōu)先關(guān)系。僅需要從左到右依次掃描后綴表達(dá)式的各個(gè)字符，遇到運(yùn)算符時(shí)，直接對(duì)運(yùn)算符前面的兩個(gè)操作數(shù)進(jìn)行運(yùn)算即可。3.2棧的應(yīng)用

如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式呢？我們約定’#’作為后綴表達(dá)式的結(jié)束標(biāo)志，假設(shè)?1為棧頂運(yùn)算符，?2為當(dāng)前掃描的運(yùn)算符。則中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法描述如下：（1）初始化棧，并將’#’入棧；（2）若當(dāng)前讀入的字符是操作數(shù)，則將該操作數(shù)輸出，并讀入下一字符；（3）若當(dāng)前字符是運(yùn)算符，記作?2，則將?2與棧頂?shù)倪\(yùn)算符?1比較。若?1優(yōu)先級(jí)低于?2，則將?2進(jìn)棧；若?1優(yōu)先級(jí)高于?2，則將?1出棧并將其作為后綴表達(dá)式輸出。然后繼續(xù)比較新的棧頂運(yùn)算符?1與當(dāng)前運(yùn)算符?2的優(yōu)先級(jí)，若?1的優(yōu)先級(jí)與?2相等，且?1為’(‘，?2為’)’，則將?1出棧，繼續(xù)讀入下一個(gè)字符；（4）如果?2的優(yōu)先級(jí)與?1相等，且?1和?2都為’#‘，將?1出棧，棧為空。則完成中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，算法結(jié)束。3.2棧的應(yīng)用運(yùn)算符的優(yōu)先關(guān)系如表1所示。表1運(yùn)算符的優(yōu)先關(guān)系3.2棧的應(yīng)用

初始化一個(gè)空棧，用來(lái)對(duì)運(yùn)算符進(jìn)行出棧和入棧操作。中綴表達(dá)式(6-2)*5+(9+2)/2-7#轉(zhuǎn)換為后綴表達(dá)式的具體過(guò)程如圖所示（為了便于描述，在要轉(zhuǎn)換表達(dá)式的末尾加一個(gè)’#’作為結(jié)束標(biāo)記）。3.2棧的應(yīng)用3.2棧的應(yīng)用2．求后綴表達(dá)式的值將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式后，就可以計(jì)算利用后綴表達(dá)式的值了。計(jì)算后綴表達(dá)式的值的規(guī)則如下：依次讀入后綴表達(dá)式中的每個(gè)字符，如果是操作數(shù)，則將操作數(shù)進(jìn)入棧；如果是運(yùn)算符，則將處于棧頂?shù)膬蓚€(gè)操作數(shù)出棧，然后利用當(dāng)前運(yùn)算符進(jìn)行運(yùn)算，將運(yùn)行結(jié)果入棧，直到整個(gè)表達(dá)式處理完畢。利用上述規(guī)則，后綴表達(dá)式的62–5*92+2/+7-的值的運(yùn)算過(guò)程如圖所示。3.2棧的應(yīng)用3.2棧的應(yīng)用3.2棧的應(yīng)用3．算法實(shí)現(xiàn)

通過(guò)鍵盤輸入一個(gè)表達(dá)式，如（5*（12-3）+4）/2，要求將其轉(zhuǎn)換為后綴表達(dá)式，并計(jì)算該表達(dá)式的值。中綴表達(dá)式（5*（12-3）+4）/2#轉(zhuǎn)換為后綴表達(dá)式的處理流程如圖所示。①初始化OPTR棧和OPND棧，將“#”壓入OPTR棧。②掃描中綴表達(dá)式，讀入第一個(gè)字符ch，若未掃描完畢或OPTR不為空，則循環(huán)執(zhí)行以下操作：若ch不是運(yùn)算符，則壓入OPND棧，讀入下一字符ch；若ch是運(yùn)算符，則根據(jù)OPTR的棧頂元素θ和ch的優(yōu)先級(jí)關(guān)系進(jìn)行以下處理：若θ的優(yōu)先級(jí)小于ch，則ch壓入OPTR棧，讀入下一字符ch；若θ的優(yōu)先級(jí)大于ch，則彈出OPTR棧頂?shù)倪\(yùn)算符，從OPND棧彈出兩個(gè)數(shù)，進(jìn)行相應(yīng)運(yùn)算，結(jié)果壓入OPND棧；若θ的優(yōu)先級(jí)等于ch，則OPTR的棧頂元素是“(”且ch是“)”，這時(shí)彈出OPTR棧頂?shù)摹?”，括號(hào)匹配成功，然后讀入下一字符ch。③

OPND棧頂元素即為表達(dá)式求值結(jié)果，返回此元素。設(shè)置兩個(gè)棧：OPND-----操作數(shù)OPTR------運(yùn)算符另解，同時(shí)設(shè)置兩個(gè)棧

：表達(dá)式求值DataTypeComputeExpression(){InitStack(OPTR);Push(OPTR，‘#’);//初始化運(yùn)算符棧InitStack(OPND);ch=getchar();;//初始化操作數(shù)棧while(ch!='#'||GetTop(OPTR)!='#'){if(!In(ch)){Push(OPND,ch);ch=getchar();}//若ch不是運(yùn)算符，則入棧

elseswitch(Precede(GetTop(OPTR),ch)){//比較優(yōu)先級(jí)

case‘<’://當(dāng)前字符ch壓入OPTR棧，讀取下一字符Push(OPTR,ch);ch=getchar();break;case‘>’://將OPTR棧頂?shù)倪\(yùn)算符彈出，并進(jìn)行計(jì)算，并將結(jié)果入棧

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;case‘=’://去掉括號(hào)并讀取下一字符

Pop(OPTR,x);ch=getchar();break;}//switch}//whilereturnGetTop(OPND);}//返回表達(dá)式值的運(yùn)算結(jié)果另解，同時(shí)設(shè)置兩個(gè)棧求值3.3棧與遞歸3.3.1遞歸先來(lái)看一個(gè)簡(jiǎn)單的例子。如果兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)兔子，假設(shè)所有兔子都不死，那么一年以后可以繁殖多少對(duì)兔子呢？3.3棧與遞歸

我們不妨拿新出生的一對(duì)小兔子來(lái)分析下。第一、二個(gè)月小兔子沒有繁殖能力，所以還是一對(duì)；兩個(gè)月后，生下一對(duì)小兔子，小兔子數(shù)共有2對(duì)兔子；三個(gè)月后，老兔子又生下一對(duì)，因?yàn)樾⊥米舆€沒有繁殖能力，所以一共是3對(duì)兔子；依次類推，可以得出下表。表

每個(gè)月兔子的對(duì)數(shù)經(jīng)過(guò)的月數(shù)123456789101112兔子對(duì)數(shù)11235813213455891443.3棧與遞歸

從表中不難看出，數(shù)字1、1、2、3、5、8……構(gòu)成了一個(gè)數(shù)列，這個(gè)數(shù)列有個(gè)十分明顯的特征：前面相鄰兩項(xiàng)之和構(gòu)成后一項(xiàng)?？捎脭?shù)學(xué)函數(shù)表示為：3.3棧與遞歸

如果要打印出斐波那契數(shù)列的前40項(xiàng)，用常規(guī)的迭代方法怎樣實(shí)現(xiàn)呢？代碼如下：

voidmain(){inti,a[40];a[0]=0;a[1]=1;printf(“%4d”,a[0]);printf(“%4d”,a[1]);for(i=2;i<40;i++){a[i]=a[i-1]+a[i-2];printf(“%4d”,a[i]);}}3.3棧與遞歸以上代碼比較簡(jiǎn)單，不用過(guò)多解釋，如果用遞歸實(shí)現(xiàn)，代碼會(huì)更加簡(jiǎn)潔。

intFib(intn){if(n==0)return0;elseif(n==1)return1;elsereturnFib(n-1)+Fib(n-2);}voidmain(){inti;for(i=0;i<40;i++)printf(“%4d”,Fib(i));}3.3棧與遞歸例如，當(dāng)n=4時(shí)，代碼執(zhí)行過(guò)程如圖4.20所示。3.3棧與遞歸2。什么是遞歸函數(shù)

如果一個(gè)函數(shù)在函數(shù)體中直接調(diào)用自己，稱為直接遞歸函數(shù)。如果經(jīng)過(guò)一系列的中間調(diào)用，間接調(diào)用自己的函數(shù)稱為間接遞歸函數(shù)。例如，n的階乘的遞歸定義如下：

n的階乘遞歸函數(shù)C語(yǔ)言實(shí)現(xiàn)如下：

intfact(intn){if(n==1)return1;elsen*fact(n-1);}3.3棧與遞歸Ackermann函數(shù)定義如下：Ackerman遞歸函數(shù)C語(yǔ)言實(shí)現(xiàn)如下：intAck(intm,intn){if(m==0)returnn+1;elseif(n==0)returnAck(m-1,1);elsereturnAck(m-1,Ack(m,n-1));}3.3棧與遞歸3。分析遞歸調(diào)用過(guò)程遞歸問(wèn)題可以被分解成規(guī)模小、性質(zhì)相同的問(wèn)題加以解決。在今后將要學(xué)習(xí)的廣義表、二叉樹等都具有遞歸的性質(zhì)，它們的操作可以用遞歸實(shí)現(xiàn)。

n階漢諾塔問(wèn)題。假設(shè)有3個(gè)塔座A、B、C，在塔座A上放置有n個(gè)直徑大小各不相同、從小到大編號(hào)為1，2，…，n的圓盤，如圖所示。要求將A軸上的n個(gè)圓盤移動(dòng)到塔座C上并要求按照同樣的疊放順序排列，圓盤移動(dòng)時(shí)必須遵循以下規(guī)則：（1）每次只能移動(dòng)一個(gè)圓盤；（2）圓盤可以放置在A、B和C中的任何一個(gè)塔座；（3）任何時(shí)候都不能將一個(gè)較大的圓盤放在較小的圓盤上。3.3棧與遞歸

如何實(shí)現(xiàn)將放在A上的圓盤按照規(guī)則移動(dòng)到C上呢？當(dāng)n=1時(shí)，直接將編號(hào)為1的圓盤從塔座A移動(dòng)到C上即可。當(dāng)n>1時(shí)，需利用塔座B作為輔助塔座，先將放置在編號(hào)為n之上的n-1個(gè)圓盤從塔座A上移動(dòng)到B上，然后將編號(hào)為n的圓盤從塔座A移動(dòng)到C上，最后將塔座B上的n-1個(gè)圓盤移動(dòng)到塔座C上。那現(xiàn)在將n-1個(gè)圓盤從一個(gè)塔座移動(dòng)到另一個(gè)塔座又成為與原問(wèn)題類似的問(wèn)題，只是規(guī)模減小了1，故可用同樣的方法解決。3.3棧與遞歸voidHanoi(intn,chara,charb,charc)/*將塔座A上按照從小到大自上而下編號(hào)為1到n的那個(gè)圓盤按照規(guī)則搬到塔座C上，B可以作為輔助塔座*/{if(n==1)Move(a,1,c);/*將編號(hào)為1的圓盤從A移動(dòng)到C*/else{Hanoi(n-1,a,c,b);/*將編號(hào)為1到n-1的圓盤從A移動(dòng)到B，C作為輔助塔座*/Move(a,n,c);/*將編號(hào)為n的圓盤從A移動(dòng)到C*/Hanoi(n-1,b,a,c);/*將編號(hào)為1到n-1的圓盤從B移動(dòng)到C，A作為輔助塔座*/}}3.3棧與遞歸下面以n=3，觀察一下漢諾塔遞歸調(diào)用的具體過(guò)程。3.3棧與遞歸

遞歸的實(shí)現(xiàn)本質(zhì)上就是把嵌套調(diào)用變成棧實(shí)現(xiàn)。在遞歸調(diào)用過(guò)程中，被調(diào)用函數(shù)在執(zhí)行前系統(tǒng)要完成3件事情：（1）將所有參數(shù)和返回地址傳遞給被調(diào)用函數(shù)保存；（2）為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)空間；（3）將控制轉(zhuǎn)到被調(diào)用函數(shù)的入口。當(dāng)被調(diào)用函數(shù)執(zhí)行完畢，返回給調(diào)用函數(shù)前，系統(tǒng)同樣需要完成3個(gè)任務(wù)：（1）保存被調(diào)用函數(shù)的執(zhí)行結(jié)果；（2）釋放被調(diào)用函數(shù)的數(shù)據(jù)存儲(chǔ)區(qū)；（3）將控制轉(zhuǎn)到調(diào)用函數(shù)的返回地址處。3.3棧與遞歸3.3.2消除遞歸

遞歸的算法也完全可以轉(zhuǎn)換為非遞歸實(shí)現(xiàn)，這就是遞歸的消除。消除遞歸方法有兩種：一種是對(duì)于簡(jiǎn)單的遞歸可以直接用迭代，通過(guò)循環(huán)結(jié)構(gòu)就可以消除；另一種方法是利用棧的方式實(shí)現(xiàn)。3.3棧與遞歸【例3.3】編寫求n!的遞歸算法與利用棧實(shí)現(xiàn)的非遞歸算法。intfact2(intn)/*n的階乘非遞歸實(shí)現(xiàn)*/{ints[MaxSize][2],top=-1; /*定義一個(gè)二維數(shù)組，并將棧頂指針置為-1*/top++;/*棧頂指針加1，將工作記錄入棧*/s[top][0]=n; /*記錄每一層的參數(shù)*/s[top][1]=0; /*記錄每一層的結(jié)果返回值*/do{if(s[top][0]==1) /*遞歸出口，當(dāng)?shù)谝痪S數(shù)組中的元素值不為0，說(shuō)明已經(jīng)有結(jié)果返回*/s[top][1]=1;3.3棧與遞歸if(s[top][0]>1&&s[top][1]==0) /*通過(guò)棧模擬遞歸的遞推過(guò)程，將問(wèn)題依次入棧*/{top++;s[top][0]=s[top-1][0]-1;s[top][1]=0; /*將結(jié)果置為0，還沒有返回結(jié)果*/}if(s[top][1]!=0) /*模擬遞歸的返回過(guò)程，將每一層調(diào)用的結(jié)果返回*/{s[top-1][1]=s[top][1]*s[top-1][0];top--;}}while(top>0);returns[0][1];}3.4隊(duì)列的表示與實(shí)現(xiàn)

隊(duì)列只允許在表的一端進(jìn)行插入操作，在表的另一端進(jìn)行刪除操作。3.4.1什么是隊(duì)列隊(duì)列（queue）是一種先進(jìn)先出（firstinfirstout，縮寫為FIFO）的線性表，它只允許在表的一端進(jìn)行插入，另一端刪除元素。這與我們?nèi)粘Ｉ钪械呐抨?duì)是一致的，最早進(jìn)入隊(duì)列的元素最早離開。在隊(duì)列中，允許插入的一端稱為隊(duì)頭（front），允許刪除的一端稱為隊(duì)尾（rear）。3.4隊(duì)列的表示與實(shí)現(xiàn)

假設(shè)隊(duì)列為q=（a1，a2，…，ai，…，an），那么a1為隊(duì)頭元素，an為隊(duì)尾元素。進(jìn)入隊(duì)列時(shí)，是按照a1，a2，…，an的順序進(jìn)入的，退出隊(duì)列時(shí)也是按照這個(gè)順序退出的。也就是說(shuō)，當(dāng)先進(jìn)入隊(duì)列的元素都退出之后，后進(jìn)入隊(duì)列的元素才能退出。即只有當(dāng)a1，a2，…，an-1都退出隊(duì)列以后，an才能退出隊(duì)列。3.4隊(duì)列的表示與實(shí)現(xiàn)

3.4.2隊(duì)列的抽象數(shù)據(jù)類型

1．?dāng)?shù)據(jù)對(duì)象集合隊(duì)列的數(shù)據(jù)對(duì)象集合為{a1，a2，…，an}，每個(gè)元素都具有相同的數(shù)據(jù)類型DataType。隊(duì)列中的數(shù)據(jù)元素之間也是一對(duì)一的關(guān)系。除了第一個(gè)元素a1外，每一個(gè)元素有且只有一個(gè)直接前驅(qū)元素，除了最后一個(gè)元素an外，每一個(gè)元素有且只有一個(gè)直接后繼元素。3.4隊(duì)列的表示與實(shí)現(xiàn)

2．基本操作集合（1）InitQueue(&Q)：初始化操作，建立一個(gè)空隊(duì)列Q。（2）QueueEmpty(Q)：若Q為空隊(duì)列，返回1，否則返回0。（3）EnQueue(&Q,e)：插入元素e到隊(duì)列Q的隊(duì)尾。（4）DeQueue(&Q,&e)：刪除Q的隊(duì)首元素，并用e返回其值。（5）Gethead(Q,&e)：用e返回Q的隊(duì)首元素。（6）ClearQueue(&Q)：將隊(duì)列Q清空。3.4隊(duì)列的表示與實(shí)現(xiàn)

3.4.3順序隊(duì)列順序隊(duì)列通常采用一維數(shù)組依次存放從隊(duì)頭到隊(duì)尾的元素。同時(shí)，使用兩個(gè)指針?lè)謩e指示數(shù)組中存放的第一個(gè)元素和最后一個(gè)元素的位置。其中，指向第一個(gè)元素的指針被稱為隊(duì)頭指針front，指向最后一個(gè)元素的指針被稱為隊(duì)尾指針rear。元素a、b、c、d、e、f、g依次進(jìn)入隊(duì)列后的狀態(tài)如圖5.2所示。元素a存放在數(shù)組下標(biāo)為0的存儲(chǔ)單元中，g存放在下標(biāo)為6的存儲(chǔ)單元中，隊(duì)頭指針front指向第一個(gè)元素a，隊(duì)尾指針rear指向最后一個(gè)元素g的下一位置。3.4隊(duì)列的表示與實(shí)現(xiàn)

在使用隊(duì)列前，先初始化隊(duì)列，此時(shí)，隊(duì)列為空，隊(duì)頭指針front和隊(duì)尾指針rear都指向隊(duì)列的第一個(gè)位置，即front=rear=0，如圖所示。每一個(gè)元素進(jìn)入隊(duì)列，隊(duì)尾指針rear就會(huì)增1，若元素a、b、c依次進(jìn)入空隊(duì)列，front指向第一個(gè)元素，rear指向下標(biāo)為3的存儲(chǔ)單元，如圖所示。3.4隊(duì)列的表示與實(shí)現(xiàn)

當(dāng)一個(gè)元素出隊(duì)列時(shí)，隊(duì)頭指針front增1，隊(duì)頭元素即a出隊(duì)后，front向后移動(dòng)一個(gè)位置，指向下一個(gè)位置，rear不變，如圖所示。順序隊(duì)列的類型描述如下：#defineQueueSize80 /*隊(duì)列的容量*/typedefstructSqueue{DataTypequeue[QueueSize];intfront,rear; /*隊(duì)頭指針和隊(duì)尾指針*/}SeqQueue;3.4隊(duì)列的表示與實(shí)現(xiàn)

在對(duì)順序隊(duì)列進(jìn)行插入和刪除操作的過(guò)程中，可能會(huì)出現(xiàn)“假溢出”現(xiàn)象。經(jīng)過(guò)多次插入和刪除操作后，實(shí)際上隊(duì)列還有存儲(chǔ)空間，但是又無(wú)法向隊(duì)列中插入元素，我們將這種溢出稱為“假溢出”。例如，在上圖所示的隊(duì)列中插入3個(gè)元素h、i、j，然后刪除2個(gè)元素a，b之后，就會(huì)出現(xiàn)如圖所示的情況。當(dāng)插入元素j后，隊(duì)尾指針rear將越出數(shù)組的下界而造成“假溢出”。3.4隊(duì)列的表示與實(shí)現(xiàn)

3.4.4順序循環(huán)隊(duì)列的表示與實(shí)現(xiàn)

1．順序循環(huán)隊(duì)列為了充分利用存儲(chǔ)空間，消除這種“假溢出”現(xiàn)象，當(dāng)隊(duì)尾指針rear和隊(duì)頭指針front到達(dá)存儲(chǔ)空間的最大值（假定隊(duì)列的存儲(chǔ)空間為QueueSize）的時(shí)候，讓隊(duì)尾指針和隊(duì)頭指針轉(zhuǎn)化為0，這樣就可以將元素插入到隊(duì)列還沒有利用的存儲(chǔ)單元中。例如，在圖中，插入元素j之后，rear將變?yōu)?，可以繼續(xù)將元素插入到下標(biāo)為0的存儲(chǔ)單元中。這樣就把順序隊(duì)列使用的存儲(chǔ)空間構(gòu)造成一個(gè)邏輯上首尾相連的循環(huán)隊(duì)列。3.4隊(duì)列的表示與實(shí)現(xiàn)

當(dāng)隊(duì)尾指針rear達(dá)到最大值QueueSize-1時(shí)，前提是隊(duì)列中還有存儲(chǔ)空間，若要插入元素，就要把隊(duì)尾指針rear變?yōu)?；當(dāng)隊(duì)頭指針front達(dá)到最大值QueueSize-1時(shí)，若要將隊(duì)頭元素出隊(duì)，要讓隊(duì)頭指針front變?yōu)?。這可通過(guò)取余操作實(shí)現(xiàn)隊(duì)列的首尾相連。例如，假設(shè)QueueSize=10，當(dāng)隊(duì)尾指針rear=9時(shí)，若要將新元素入隊(duì)，則先令rear=（rear+1）%10=0，然后將元素存入隊(duì)列的第0號(hào)單元，通過(guò)取余操作實(shí)現(xiàn)了隊(duì)列的邏輯上的首尾相連。3.4隊(duì)列的表示與實(shí)現(xiàn)

2．順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判斷但是，在順序循環(huán)隊(duì)列在隊(duì)空和隊(duì)滿的情況下，隊(duì)頭指針front和隊(duì)尾指針rear同時(shí)都會(huì)指向同一個(gè)位置，即front==rear，如圖所示。即隊(duì)列為空時(shí)，有front=0，rear=0，因此front==rear。隊(duì)滿時(shí)也有front=0，rear=0，因此front==rear。3.4隊(duì)列的表示與實(shí)現(xiàn)

為了區(qū)分這隊(duì)空還是隊(duì)滿，通常有兩個(gè)方法：（1）增加一個(gè)標(biāo)志位。設(shè)這個(gè)標(biāo)志位為flag，初始時(shí)，有flag=0；當(dāng)入隊(duì)列成功，則flag=1；出隊(duì)列成功，有flag=0。則隊(duì)列為空的判斷條件為：front==rear&&flag==0，隊(duì)列滿的判斷條件為：front==rear&&flag==1。（2）少用一個(gè)存儲(chǔ)單元。隊(duì)空的判斷條件為front==rear，隊(duì)滿的判斷條件為front==(rear+1)%QueueSize。那么，入隊(duì)的操作語(yǔ)句為：rear=（rear+1）%QueueSize，Q[rear]=x。出隊(duì)的操作語(yǔ)句為：front=（front+1）%QueueSize。少用一個(gè)存儲(chǔ)單元的順序循環(huán)隊(duì)列隊(duì)滿情況如圖所示。3.4隊(duì)列的表示與實(shí)現(xiàn)

順序循環(huán)隊(duì)列類型描述如下：

#defineQueueSize60 /*隊(duì)列的容量*/typedefstructSqueue{DataTypequeue[QueueSize];intfront,rear; /*隊(duì)頭指針和隊(duì)尾指針*/}SeqQueue;

其中，queue用來(lái)存儲(chǔ)隊(duì)列中的元素，front和rear分別表示隊(duì)頭指針和隊(duì)尾指針，取值范圍為0~QueueSize。3.4隊(duì)列的表示與實(shí)現(xiàn)

順序循環(huán)隊(duì)列的主要操作說(shuō)明如下：（1）初始化時(shí)，設(shè)置SQ.front=SQ.rear=0。（2）循環(huán)隊(duì)列隊(duì)空的條件為SQ.front==SQ.rear，隊(duì)滿的條件為SQ.front==（SQ.rear+1）%QueueSize。（3）入隊(duì)操作：先判斷隊(duì)列是否已滿，若隊(duì)列未滿，則將元素值e存入隊(duì)尾指針指向的存儲(chǔ)單元，然后將隊(duì)尾指針加1后取模。（4）出隊(duì)操作：先判斷隊(duì)列是否為空，若隊(duì)列不空，則先把隊(duì)頭指針指向的元素值賦給e，即取出隊(duì)頭元素，然后將隊(duì)頭指針加1后取模。（5）循環(huán)隊(duì)列的長(zhǎng)度為（SQ.rear+QueueSize-SQ.front）%QueueSize。3.4隊(duì)列的表示與實(shí)現(xiàn)

3.順序循環(huán)隊(duì)列的基本運(yùn)算順序循環(huán)隊(duì)列的基本運(yùn)算算法實(shí)現(xiàn)如下。（1）初始化隊(duì)列。

voidInitQueue(SeqQueue*SCQ)/*順序循環(huán)隊(duì)列的初始化*/{SCQ->front=SCQ->rear=0;}3.4隊(duì)列的表示與實(shí)現(xiàn)

（2）判斷隊(duì)列是否為空。若隊(duì)頭指針與隊(duì)尾指針相等，則隊(duì)列為空；否則隊(duì)列不為空。算法實(shí)現(xiàn)如下。intQueueEmpty(SeqQueueSCQ)/*判斷順序循環(huán)隊(duì)列是否為空，隊(duì)列為空返回1，否則返回0*/{if(SCQ.front==SCQ.rear) /*當(dāng)順序循環(huán)隊(duì)列為空時(shí)*/return1; /*返回1*/else /*否則*/return0; /*返回0*/}3.4隊(duì)列的表示與實(shí)現(xiàn)

（3）將元素e入隊(duì)。

intEnQueue(SeqQueue*SCQ,DataTypee){if(SCQ->front==(SCQ->rear+1)%QueueSize)/*在插入新的元素之前，判斷隊(duì)尾指針是否到達(dá)數(shù)組的最大值*/return0;SCQ->queue[SCQ->rear]=e;/*在隊(duì)尾插入元素e*/SCQ->rear=(SCQ->rear+1)%QueueSize; /*隊(duì)尾指針向后移動(dòng)一個(gè)位置*/return1;}3.4隊(duì)列的表示與實(shí)現(xiàn)

（4）將隊(duì)頭元素出隊(duì)。intDeQueue(SeqQueue*SCQ,DataType*e){if(SCQ->front==SCQ->rear) /*在刪除元素之前，判斷順序循環(huán)隊(duì)列是否為空*/return0;else{*e=SCQ->queue[SCQ->front]; /*將要?jiǎng)h除的元素賦值給e*/SCQ->front=(SCQ->front+1)%QueueSize; /*將隊(duì)頭指針向后移動(dòng)一個(gè)位置，指向新的隊(duì)頭*/return1;}}3.4隊(duì)列的表示與實(shí)現(xiàn)

（5）取隊(duì)頭元素。先判斷順序循環(huán)隊(duì)列是否為空，如果隊(duì)列為空，則返回0表示取隊(duì)頭元素失??；否則，把隊(duì)頭元素賦給e，并返回1表示取隊(duì)頭元素成功。

intGetHead(SeqQueueSCQ,DataType*e){if(SCQ.front==SCQ.rear) /*在取隊(duì)頭元素之前，判斷順序循環(huán)隊(duì)列是否為空*/return0;else{*e=SCQ.queue[SCQ.front]; /*將隊(duì)頭元素賦值給e，取出隊(duì)頭元素*/return1;}}3.4.5雙端隊(duì)列

雙端隊(duì)列可以在隊(duì)列的任何一端進(jìn)行插入和刪除操作，而一般的隊(duì)列要求在一端插入元素，在另一端刪除元素。其中，end1和end2分別是雙端隊(duì)列的指針。輸入受限的雙端隊(duì)列指的是只允許在隊(duì)列的一端插入元素，而兩端都能刪除元素的隊(duì)列。輸出受限的雙端隊(duì)列指的是只允許在隊(duì)列的一端刪除元素，兩端都能輸入元素的隊(duì)列。3.4隊(duì)列的表示與實(shí)現(xiàn)采用一個(gè)一維數(shù)組作為雙端隊(duì)列的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，試編寫入隊(duì)算法和出隊(duì)算法。雙端隊(duì)列為空的狀態(tài)如圖所示。在實(shí)際操作過(guò)程中，用循環(huán)隊(duì)列實(shí)現(xiàn)雙端隊(duì)列的操作是比較恰當(dāng)?shù)摹Ｔ豠，b，c依次進(jìn)入左端的隊(duì)列，元素e，f依次進(jìn)入右端的隊(duì)列，如圖所示。3.4隊(duì)列的表示與實(shí)現(xiàn)編寫算法，實(shí)現(xiàn)雙端隊(duì)列的入隊(duì)和出隊(duì)操作。求：（1）當(dāng)隊(duì)列滿時(shí)，最多只能有一個(gè)存儲(chǔ)空間為空；（2）在進(jìn)行插入和刪除元素時(shí)，隊(duì)列中的其他元素不動(dòng)。分析：設(shè)雙端隊(duì)列為Q，初始時(shí)，隊(duì)列為空，有Q.end1==Q.end2，隊(duì)滿的條件為（Q.end1-1+QueueSize）%QueueSize==Q.end2或（Q.end2+1+QueueSize）%QueueSize==Q.end1。對(duì)于左端的隊(duì)列，當(dāng)元素入隊(duì)時(shí)，需要執(zhí)行Q.end-1操作；當(dāng)元素出隊(duì)列時(shí)，需要執(zhí)行Q.end1+1操作。對(duì)于右端的隊(duì)列，當(dāng)元素入隊(duì)時(shí)，需要執(zhí)行Q.end2+1操作；當(dāng)元素出隊(duì)列時(shí)，需要執(zhí)行Q.end2-1操作。3.4隊(duì)列的表示與實(shí)現(xiàn)3.4隊(duì)列的表示與實(shí)現(xiàn)

3.4.6鏈?zhǔn)疥?duì)列順序隊(duì)列在插入和刪除操作過(guò)程中需要移動(dòng)大量元素，這樣算法的效率會(huì)比較低，為了避免以上問(wèn)題，可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示隊(duì)列。

1．鏈?zhǔn)疥?duì)列的表示鏈?zhǔn)疥?duì)列通常用鏈表實(shí)現(xiàn)。一個(gè)鏈隊(duì)列顯然需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針（分別稱為隊(duì)頭指針和隊(duì)尾指針）才能唯一確定。這里，與單鏈表一樣，為了操作上的方便，我們給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)，并令隊(duì)頭指針front指向頭結(jié)點(diǎn)，用隊(duì)尾指針rear指向最后一個(gè)結(jié)點(diǎn)。3.4隊(duì)列的表示與實(shí)現(xiàn)

一個(gè)不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列和帶頭結(jié)點(diǎn)的鏈隊(duì)列分別如下圖所示。3.4隊(duì)列的表示與實(shí)現(xiàn)

對(duì)于帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列，當(dāng)隊(duì)列為空時(shí)，隊(duì)頭指針front和隊(duì)尾指針rear都指向頭結(jié)點(diǎn)。如圖所示。鏈?zhǔn)疥?duì)列中，插入和刪除操作只需要移動(dòng)隊(duì)頭指針和隊(duì)尾指針，這兩種操作的指針變化如圖所示。3.4隊(duì)列的表示與實(shí)現(xiàn)

鏈?zhǔn)疥?duì)列的類型描述如下：/*結(jié)點(diǎn)類型定義*/typedefstructQNode{DataTypedata;structQNode*next;}LQNode,*QueuePtr;/*隊(duì)列類型定義*/typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;3.4隊(duì)列的表示與實(shí)現(xiàn)

2．鏈?zhǔn)窖h(huán)隊(duì)列將鏈?zhǔn)疥?duì)列的首尾相連就構(gòu)成了鏈?zhǔn)窖h(huán)隊(duì)列。在鏈?zhǔn)窖h(huán)隊(duì)列中，可以只設(shè)置隊(duì)尾指針，如圖所示。隊(duì)列LQ為空的判斷條件為L(zhǎng)Q.rear->next==LQ.rear。3.4隊(duì)列的表示與實(shí)現(xiàn)

2鏈?zhǔn)疥?duì)列的基本運(yùn)算鏈?zhǔn)疥?duì)列的基本運(yùn)算算法實(shí)現(xiàn)如下。（1）初始化隊(duì)列。voidInitQueue(LinkQueue*LQ)/*初始化鏈?zhǔn)疥?duì)列*/{LQ->front=LQ->rear=(LQNode*)malloc(sizeof(LQNode));if(LQ->front==NULL)exit(-1);LQ->front->next=NULL; /*把頭結(jié)點(diǎn)的指針域置為為0*/}3.4隊(duì)列的表示與實(shí)現(xiàn)

（2）判斷隊(duì)列是否為空。intQueueEmpty(LinkQueueLQ)/*判斷鏈?zhǔn)疥?duì)列是否為空，隊(duì)列為空返回1，否則返回0*/{if(LQ.rear->next==NULL)/*當(dāng)鏈?zhǔn)疥?duì)列為空時(shí)*/return1; /*返回1*/else /*否則*/return0; /*返回0*/}3.4隊(duì)列的表示與實(shí)現(xiàn)

（3）將元素e入隊(duì)。先為新結(jié)點(diǎn)申請(qǐng)一個(gè)空間，然后將e賦給數(shù)據(jù)域，并使原隊(duì)尾元素結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)，隊(duì)尾指針指向新結(jié)點(diǎn)，從而將結(jié)點(diǎn)加入隊(duì)列中。操作過(guò)程如圖所示。將元素e入隊(duì)的算法實(shí)現(xiàn)如下。intEnQueue(LinkQueue*LQ,DataTypee)/*將元素e插入到鏈?zhǔn)疥?duì)列LQ中，插入成功返回1*/{LQNode*s;s=(LQNode*)malloc(sizeof(LQNode)); if(!s)exit(-1); /*如果申請(qǐng)空間失敗，則退出并返回參數(shù)-1*/s->data=e; /*將元素值賦值給結(jié)點(diǎn)的數(shù)據(jù)域*/s->next=NULL;/*將結(jié)點(diǎn)的指針域置為空*/LQ->rear->next=s; /*將原來(lái)隊(duì)列的隊(duì)尾指針指向s*/LQ->rear=s; /*將隊(duì)尾指針指向s*/return1;}3.4隊(duì)列的表示與實(shí)現(xiàn)

3.4隊(duì)列的表示與實(shí)現(xiàn)

（4）將隊(duì)頭元素出隊(duì)。intDeQueue(LinkQueue*LQ,DataType*e){LQNode*s;if(LQ->front==LQ->rear)/*判斷鏈?zhǔn)疥?duì)列是否為空*/return0;else{s=LQ->front->next; /*使指針s指向隊(duì)頭元素的指針*/*e=s->data; /*將要?jiǎng)h除的隊(duì)頭元素賦給e*/LQ->front->next=s->next;/*使頭結(jié)點(diǎn)指針指向s的下一個(gè)結(jié)點(diǎn)*/if(LQ->rear==s)LQ->rear=LQ->front; /*如果要?jiǎng)h除的結(jié)點(diǎn)是隊(duì)尾，則使隊(duì)尾指針指向隊(duì)頭指針*/free(s); /*釋放指針s指向的結(jié)點(diǎn)空間*/return1;}}3.4隊(duì)列的表示與實(shí)現(xiàn)

（5）取隊(duì)頭元素。intGetHead(LinkQueueLQ,DataType*e){LQNode*s;if(LQ.front==LQ.rear)/*在取隊(duì)頭元素之前，判斷鏈?zhǔn)疥?duì)列是否為空*/return0;else{s=LQ.front->next;/*將指針p指向隊(duì)列的第一個(gè)元素即隊(duì)頭元素*/*e=s->data; /*將隊(duì)頭元素賦給e，取出隊(duì)頭元素*/return1;}}（6）清空隊(duì)列。

voidClearQueue(LinkQueue*LQ)/*清空隊(duì)列*/{while(LQ->front!=NULL){LQ->rear=LQ->front->next; /*隊(duì)尾指針指向隊(duì)頭指針指向的下一個(gè)結(jié)點(diǎn)*/free(LQ->front); /*釋放隊(duì)頭指針指向的結(jié)點(diǎn)*/LQ->front=LQ->rear;/*隊(duì)頭指針指向隊(duì)尾指針*/}}3.4隊(duì)列的表示與實(shí)現(xiàn)

3.5.1隊(duì)列在楊輝三角中的應(yīng)用

從圖中可以看出，楊輝三角具有以下性質(zhì)：

（1）第一行只有一個(gè)元素；

（2）第i行有i個(gè)元素；

（3）第i行最左端和最右端元素為1；

（4）第i行中間元素是它上一行i-1行對(duì)應(yīng)位置元素與對(duì)應(yīng)位置前一個(gè)元素之和。3.5隊(duì)列的應(yīng)用3.5隊(duì)列的應(yīng)用構(gòu)造隊(duì)列的步驟如下：（1）在第8行中，第一個(gè)元素先入隊(duì)。假設(shè)隊(duì)列為Q，Q.queue[rear]=1；Q.rear=(Q.rear+1)%QueueSize。（2）第8行中的中間6個(gè)元素需要通過(guò)第7行（已經(jīng)入隊(duì)）得到并入隊(duì)。Q.queue[rear]=Q.queue[front]+Q.queue[front+1]；Q.rear=(Q.rear+1)%QueueSize