數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列第一頁(yè)，共五十四頁(yè)，編輯于2023年，星期三3.1

棧3.1.1

棧的基本概念1

棧的概念

棧(Stack)：是限制在表的一端進(jìn)行插入和刪除操作的線(xiàn)性表。又稱(chēng)為后進(jìn)先出LIFO

(LastInFirstOut)或先進(jìn)后出FILO

(FirstInLastOut)線(xiàn)性表。

棧頂(Top)：允許進(jìn)行插入、刪除操作的一端，又稱(chēng)為表尾。用棧頂指針(top)來(lái)指示棧頂元素。

棧底(Bottom)：是固定端，又稱(chēng)為表頭。

空棧：當(dāng)表中沒(méi)有元素時(shí)稱(chēng)為空棧。第二頁(yè)，共五十四頁(yè)，編輯于2023年，星期三

設(shè)棧S=(a1，a2，…an)，則a1稱(chēng)為棧底元素，an為棧頂元素，如圖3-1所示。棧中元素按a1，a2，…an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。即棧的修改是按后進(jìn)先出的原則進(jìn)行的。圖3-1順序棧示意圖a1a2aian????bottomtop進(jìn)棧（push）出棧(pop)2棧的抽象數(shù)據(jù)類(lèi)型定義ADTStack{數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n，n≥0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1，ai∈D,i=2,3,…,n}基本操作：初始化、進(jìn)棧、出棧、取棧頂元素等}ADTStack第三頁(yè)，共五十四頁(yè)，編輯于2023年，星期三棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為順序棧，和線(xiàn)性表相類(lèi)似，用一維數(shù)組來(lái)存儲(chǔ)棧。根據(jù)數(shù)組是否可以根據(jù)需要增大，又可分為靜態(tài)順序棧和動(dòng)態(tài)順序棧?！綮o態(tài)順序棧實(shí)現(xiàn)簡(jiǎn)單，但不能根據(jù)需要增大棧的存儲(chǔ)空間；◆動(dòng)態(tài)順序?？梢愿鶕?jù)需要增大棧的存儲(chǔ)空間，但實(shí)現(xiàn)稍為復(fù)雜。3.1.2

棧的順序存儲(chǔ)表示第四頁(yè)，共五十四頁(yè)，編輯于2023年，星期三采用動(dòng)態(tài)一維數(shù)組來(lái)存儲(chǔ)棧。所謂動(dòng)態(tài)，指的是棧的大小可以根據(jù)需要增加?！粲胋ottom表示棧底指針，棧底固定不變的；棧頂則隨著進(jìn)棧和退棧操作而變化。用top(稱(chēng)為棧頂指針)指示當(dāng)前棧頂位置。◆用top=bottom作為?？盏臉?biāo)記，每次top指向棧頂數(shù)組中的下一個(gè)存儲(chǔ)位置?！?/p>

結(jié)點(diǎn)進(jìn)棧：首先將數(shù)據(jù)元素保存到棧頂(top所指的當(dāng)前位置)，然后執(zhí)行top加1，使top指向棧頂?shù)南乱粋€(gè)存儲(chǔ)位置;3.1.2.1

棧的動(dòng)態(tài)順序存儲(chǔ)表示第五頁(yè)，共五十四頁(yè)，編輯于2023年，星期三◆結(jié)點(diǎn)出棧：首先執(zhí)行top減1，使top指向棧頂元素的存儲(chǔ)位置，然后將棧頂元素取出。圖3-2是一個(gè)動(dòng)態(tài)棧的變化示意圖。圖3-2(動(dòng)態(tài))堆棧變化示意圖空棧bottomtop元素a進(jìn)棧bottomtopa元素b，c進(jìn)棧bottomtopabc元素c退棧bottomtopabbottomtopabdef元素d，e，f進(jìn)棧第六頁(yè)，共五十四頁(yè)，編輯于2023年，星期三基本操作的實(shí)現(xiàn)1

棧的類(lèi)型定義#defineSTACK_SIZE100/*棧初始向量大小*/#defineSTACKINCREMENT10/*存儲(chǔ)空間分配增量*/#typedefintElemType;typedefstructsqstack{ElemType*bottom;/*棧不存在時(shí)值為NULL*/ElemType*top;/*棧頂指針*/intstacksize;/*當(dāng)前已分配空間，以元素為單位*/}SqStack;第七頁(yè)，共五十四頁(yè)，編輯于2023年，星期三2棧的初始化StatusInit_Stack(void){SqStackS;S.bottom=(ElemType*)malloc(STACK_SIZE*sizeof(ElemType));if(!S.bottom)returnERROR;S.top=S.bottom;/*?？諘r(shí)棧頂和棧底指針相同*/S.stacksize=STACK_SIZE;returnOK;}第八頁(yè)，共五十四頁(yè)，編輯于2023年，星期三3壓棧(元素進(jìn)棧)Statuspush(SqStackS,ElemTypee)

{if(S.top-S.bottom>=S.stacksize-1){S.bottom=(ElemType*)realloc((S.STACKINCREMENT+STACK_SIZE)*sizeof(ElemType));/*棧滿(mǎn)，追加存儲(chǔ)空間*/if(!S.bottom)returnERROR;

S.top=S.bottom+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top=e;S.top++;/*棧頂指針加1，e成為新的棧頂*/returnOK;}第九頁(yè)，共五十四頁(yè)，編輯于2023年，星期三4

彈棧(元素出棧)Statuspop(SqStackS,ElemType*e)/*彈出棧頂元素*/{if(S.top==S.bottom)returnERROR;

/*?？眨祷厥?biāo)志*/S.top--;e=*S.top;returnOK;}

第十頁(yè)，共五十四頁(yè)，編輯于2023年，星期三采用靜態(tài)一維數(shù)組來(lái)存儲(chǔ)棧。棧底固定不變的，而棧頂則隨著進(jìn)棧和退棧操作變化的，◆棧底固定不變的；棧頂則隨著進(jìn)棧和退棧操作而變化，用一個(gè)整型變量top(稱(chēng)為棧頂指針)來(lái)指示當(dāng)前棧頂位置?！粲胻op=0表示?？盏某跏紶顟B(tài)，每次top指向棧頂在數(shù)組中的存儲(chǔ)位置。

◆

結(jié)點(diǎn)進(jìn)棧：首先執(zhí)行top加1，使top指向新的棧頂位置，然后將數(shù)據(jù)元素保存到棧頂(top所指的當(dāng)前位置)。3.1.2.2

棧的靜態(tài)順序存儲(chǔ)表示(簡(jiǎn)略)第十一頁(yè)，共五十四頁(yè)，編輯于2023年，星期三◆結(jié)點(diǎn)出棧：首先把top指向的棧頂元素取出，然后執(zhí)行top減1，使top指向新的棧頂位置。若棧的數(shù)組有Maxsize個(gè)元素，則top=Maxsize-1時(shí)棧滿(mǎn)。圖3-3是一個(gè)大小為5的棧的變化示意圖。圖3-3靜態(tài)堆棧變化示意圖空棧bottomtopTop=11個(gè)元素進(jìn)棧bottomtopaTop=33個(gè)元素進(jìn)棧bottomtopabcTop=4棧滿(mǎn)bottomtopabedTop=2元素c進(jìn)棧bottomtopab第十二頁(yè)，共五十四頁(yè)，編輯于2023年，星期三基本操作的實(shí)現(xiàn)1棧的類(lèi)型定義#defineMAX_STACK_SIZE100/*棧向量大小*/#typedefintElemType;typedefstructsqstack{ElemTypestack_array[MAX_STACK_SIZE];inttop;}SqStack;第十三頁(yè)，共五十四頁(yè)，編輯于2023年，星期三2棧的初始化SqStackInit_Stack(void){SqStackS;S.bottom=S.top=0;return(S);}第十四頁(yè)，共五十四頁(yè)，編輯于2023年，星期三3壓棧(元素進(jìn)棧)Statuspush(SqStackS,ElemTypee)/*使數(shù)據(jù)元素e進(jìn)棧成為新的棧頂*/{if(S.top==MAX_STACK_SIZE-1)returnERROR;/*棧滿(mǎn)，返回錯(cuò)誤標(biāo)志*/S.top++;/*棧頂指針加1*/S.stack_array[S.top]=e;/*e成為新的棧頂*/returnOK;/*壓棧成功*/}第十五頁(yè)，共五十四頁(yè)，編輯于2023年，星期三4

彈棧(元素出棧)Statuspop(SqStackS,ElemType*e)/*彈出棧頂元素*/{if(S.top==0)returnERROR;/*?？眨祷劐e(cuò)誤標(biāo)志*/*e=S.stack_array[S.top];S.top--;returnOK;}第十六頁(yè)，共五十四頁(yè)，編輯于2023年，星期三當(dāng)棧滿(mǎn)時(shí)做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，簡(jiǎn)稱(chēng)“上溢”。上溢是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。當(dāng)?？諘r(shí)做退棧運(yùn)算也將產(chǎn)生溢出，簡(jiǎn)稱(chēng)“下溢”。下溢則可能是正常現(xiàn)象，因?yàn)闂Ｔ谑褂脮r(shí)，其初態(tài)或終態(tài)都是空棧，所以下溢常用來(lái)作為控制轉(zhuǎn)移的條件。第十七頁(yè)，共五十四頁(yè)，編輯于2023年，星期三1棧的鏈?zhǔn)奖硎?/p>

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為鏈棧，是運(yùn)算受限的單鏈表。其插入和刪除操作只能在表頭位置上進(jìn)行。因此，鏈棧沒(méi)有必要像單鏈表那樣附加頭結(jié)點(diǎn)，棧頂指針top就是鏈表的頭指針。圖3-4是棧的鏈?zhǔn)酱鎯?chǔ)表示形式。3.1.3

棧的鏈?zhǔn)酱鎯?chǔ)表示(簡(jiǎn)略)空棧top?非空棧topa4a3a1?a2圖3-4鏈棧存儲(chǔ)形式鏈棧的結(jié)點(diǎn)類(lèi)型說(shuō)明如下：typedefstructStack_Node{ElemTypedata;structStack_Node*next;}Stack_Node;第十八頁(yè)，共五十四頁(yè)，編輯于2023年，星期三2

鏈?；静僮鞯膶?shí)現(xiàn)(1)

棧的初始化Stack_Node*Init_Link_Stack(void){Stack_Node*top;top=(Stack_Node*)malloc(sizeof(Stack_Node));top->next=NULL;return(top);}第十九頁(yè)，共五十四頁(yè)，編輯于2023年，星期三(2)壓棧(元素進(jìn)棧)Statuspush(Stack_Node*top,ElemTypee){Stack_Node*p;p=(Stack_Node*)malloc(sizeof(Stack_Node));if(!p)returnERROR;/*申請(qǐng)新結(jié)點(diǎn)失敗，返回錯(cuò)誤標(biāo)志*/p->data=e;p->next=top->next;top->next=p;/*鉤鏈*/returnOK;}第二十頁(yè)，共五十四頁(yè)，編輯于2023年，星期三(3)

彈棧(元素出棧)Statuspop(Stack_Node*top,ElemType*e)/*將棧頂元素出棧*/{Stack_Node*p;ElemTypee;if(top->next==NULL)returnERROR;/*?？眨祷劐e(cuò)誤標(biāo)志*/p=top->next;e=p->data;/*取棧頂元素*/top->next=p->next;/*修改棧頂指針*/free(p);returnOK;}第二十一頁(yè)，共五十四頁(yè)，編輯于2023年，星期三3.2

棧的應(yīng)用

由于棧具有的“后進(jìn)先出”的固有特性，因此，棧成為程序設(shè)計(jì)中常用的工具和數(shù)據(jù)結(jié)構(gòu)。以下是幾個(gè)棧應(yīng)用的例子。第二十二頁(yè)，共五十四頁(yè)，編輯于2023年，星期三3.2.1數(shù)制轉(zhuǎn)換十進(jìn)制整數(shù)N向其它進(jìn)制數(shù)d(二、八、十六)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題。轉(zhuǎn)換法則：該轉(zhuǎn)換法則對(duì)應(yīng)于一個(gè)簡(jiǎn)單算法原理:n=(ndivd)*d+nmodd其中：div為整除運(yùn)算,mod為求余運(yùn)算例如(1348)10=(2504)8，其運(yùn)算過(guò)程如下：nndiv8nmod8134816841682102125202第二十三頁(yè)，共五十四頁(yè)，編輯于2023年，星期三

采用靜態(tài)順序棧方式實(shí)現(xiàn)voidconversion(intn,intd)/*將十進(jìn)制整數(shù)N轉(zhuǎn)換為d(2或8)進(jìn)制數(shù)*/{SqStackS;intk,*e;S=Init_Stack();while(n>0){k=n%d;push(S,k);n=n/d;}

/*求出所有的余數(shù)，進(jìn)棧*/while(S.top!=0)/*棧不空時(shí)出棧，輸出*/{pop(S,e);printf(“%1d”,*e);}}

第二十四頁(yè)，共五十四頁(yè)，編輯于2023年，星期三3.2.2括號(hào)匹配問(wèn)題在文字處理軟件或編譯程序設(shè)計(jì)時(shí)，常常需要檢查一個(gè)字符串或一個(gè)表達(dá)式中的括號(hào)是否相匹配?匹配思想：從左至右掃描一個(gè)字符串(或表達(dá)式)，則每個(gè)右括號(hào)將與最近遇到的那個(gè)左括號(hào)相匹配。則可以在從左至右掃描過(guò)程中把所遇到的左括號(hào)存放到堆棧中。每當(dāng)遇到一個(gè)右括號(hào)時(shí)，就將它與棧頂?shù)淖罄ㄌ?hào)(如果存在)相匹配，同時(shí)從棧頂刪除該左括號(hào)。算法思想：設(shè)置一個(gè)棧，當(dāng)讀到左括號(hào)時(shí)，左括號(hào)進(jìn)棧。當(dāng)讀到右括號(hào)時(shí)，則從棧中彈出一個(gè)元素，與讀到的左括號(hào)進(jìn)行匹配，若匹配成功，繼續(xù)讀入；否則匹配失敗，返回FLASE。第二十五頁(yè)，共五十四頁(yè)，編輯于2023年，星期三算法描述#defineTRUE0#defineFLASE-1SqStackS;S=Init_Stack();/*堆棧初始化*/intMatch_Brackets(){charch,x;scanf(“%c”,&ch);while(asc(ch)!=13)/*不等于回車(chē)*/第二十六頁(yè)，共五十四頁(yè)，編輯于2023年，星期三{if((ch==‘(’)||(ch==‘[’))push(S,ch);elseif(ch==‘]’){x=pop(S);if(x!=‘[’){printf(“’[’括號(hào)不匹配”);returnFLASE;}}elseif(ch==‘)’){x=pop(S);if(x!=‘(’){printf(“’(’括號(hào)不匹配”);returnFLASE;}}}第二十七頁(yè)，共五十四頁(yè)，編輯于2023年，星期三if(S.top!=0){printf(“括號(hào)數(shù)量不匹配！”);returnFLASE;}elsereturnTRUE;}第二十八頁(yè)，共五十四頁(yè)，編輯于2023年，星期三3.3棧與遞歸調(diào)用的實(shí)現(xiàn)(簡(jiǎn))棧的另一個(gè)重要應(yīng)用是在程序設(shè)計(jì)語(yǔ)言中實(shí)現(xiàn)遞歸調(diào)用。

遞歸調(diào)用：一個(gè)函數(shù)(或過(guò)程)直接或間接地調(diào)用自己本身，簡(jiǎn)稱(chēng)遞歸(Recursive)。遞歸是程序設(shè)計(jì)中的一個(gè)強(qiáng)有力的工具。因?yàn)檫f歸函數(shù)結(jié)構(gòu)清晰，程序易讀，正確性很容易得到證明。為了使遞歸調(diào)用不至于無(wú)終止地進(jìn)行下去，實(shí)際上有效的遞歸調(diào)用函數(shù)(或過(guò)程)應(yīng)包括兩部分：遞推規(guī)則(方法)，終止條件。例如：求n!第二十九頁(yè)，共五十四頁(yè)，編輯于2023年，星期三Fact(n)=1當(dāng)n=0時(shí)終止條件n*fact(n-1)當(dāng)n>0時(shí)遞推規(guī)則

為保證遞歸調(diào)用正確執(zhí)行，系統(tǒng)設(shè)立一個(gè)“遞歸工作?！?，作為整個(gè)遞歸調(diào)用過(guò)程期間使用的數(shù)據(jù)存儲(chǔ)區(qū)。每一層遞歸包含的信息如：參數(shù)、局部變量、上一層的返回地址構(gòu)成一個(gè)“工作記錄”。每進(jìn)入一層遞歸，就產(chǎn)生一個(gè)新的工作記錄壓入棧頂；每退出一層遞歸，就從棧頂彈出一個(gè)工作記錄。第三十頁(yè)，共五十四頁(yè)，編輯于2023年，星期三

從被調(diào)函數(shù)返回調(diào)用函數(shù)的一般步驟：(1)若棧為空，則執(zhí)行正常返回。⑵從棧頂彈出一個(gè)工作記錄。⑶將“工作記錄”中的參數(shù)值、局部變量值賦給相應(yīng)的變量；讀取返回地址。⑷將函數(shù)值賦給相應(yīng)的變量。(5)轉(zhuǎn)移到返回地址。第三十一頁(yè)，共五十四頁(yè)，編輯于2023年，星期三1

隊(duì)列的基本概念

隊(duì)列(Queue)：也是運(yùn)算受限的線(xiàn)性表。是一種先進(jìn)先出(FirstInFirstOut，簡(jiǎn)稱(chēng)FIFO)的線(xiàn)性表。只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。

隊(duì)首(front)

：允許進(jìn)行刪除的一端稱(chēng)為隊(duì)首。

隊(duì)尾(rear)

：允許進(jìn)行插入的一端稱(chēng)為隊(duì)尾。例如：排隊(duì)購(gòu)物。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入隊(duì)列的成員總是先離開(kāi)隊(duì)列。

3.4

隊(duì)列3.4.1

隊(duì)列及其基本概念第三十二頁(yè)，共五十四頁(yè)，編輯于2023年，星期三

隊(duì)列中沒(méi)有元素時(shí)稱(chēng)為空隊(duì)列。在空隊(duì)列中依次加入元素a1,a2,…,an之后，a1是隊(duì)首元素，an是隊(duì)尾元素。顯然退出隊(duì)列的次序也只能是a1,a2,…,an，即隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的，如圖3-5所示。a1,a2,…,an出隊(duì)入隊(duì)隊(duì)尾隊(duì)首圖3-5隊(duì)列示意圖2

隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義ADTQueue{數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}第三十三頁(yè)，共五十四頁(yè)，編輯于2023年，星期三數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}約定a1端為隊(duì)首，an端為隊(duì)尾?；静僮鳎篊reate()：創(chuàng)建一個(gè)空隊(duì)列；EmptyQue()：若隊(duì)列為空，則返回true，否則返回flase；??InsertQue(x)：向隊(duì)尾插入元素x；DeleteQue(x)：刪除隊(duì)首元素x；}ADTQueue第三十四頁(yè)，共五十四頁(yè)，編輯于2023年，星期三3隊(duì)列的順序表示和實(shí)現(xiàn)(簡(jiǎn))

利用一組連續(xù)的存儲(chǔ)單元(一維數(shù)組)

依次存放從隊(duì)首到隊(duì)尾的各個(gè)元素，稱(chēng)為順序隊(duì)列。對(duì)于隊(duì)列，和順序棧相類(lèi)似，也有動(dòng)態(tài)和靜態(tài)之分。本部分介紹的是靜態(tài)順序隊(duì)列，其類(lèi)型定義如下：#defineMAX_QUEUE_SIZE100typedefstructqueue{ElemTypeQueue_array[MAX_QUEUE_SIZE];intfront;intrear;}SqQueue;第三十五頁(yè)，共五十四頁(yè)，編輯于2023年，星期三隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

設(shè)立一個(gè)隊(duì)首指針front，一個(gè)隊(duì)尾指針rear

，分別指向隊(duì)首和隊(duì)尾元素。

◆初始化：front=rear=0。

◆入隊(duì)：將新元素插入rear所指的位置，然后rear加1。

◆出隊(duì)：刪去front所指的元素，然后加1并返回被刪元素。

◆隊(duì)列為空：front=rear?！絷?duì)滿(mǎn)：rear=MAX_QUEUE_SIZE-1或front=rear。第三十六頁(yè)，共五十四頁(yè)，編輯于2023年，星期三

在非空隊(duì)列里，隊(duì)首指針始終指向隊(duì)頭元素，而隊(duì)尾指針始終指向隊(duì)尾元素的下一位置。

順序隊(duì)列中存在“假溢出”現(xiàn)象。因?yàn)樵谌腙?duì)和出隊(duì)操作中，頭、尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無(wú)法重新利用。因此，盡管隊(duì)列中實(shí)際元素個(gè)數(shù)可能遠(yuǎn)遠(yuǎn)小于數(shù)組大小，但可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊(duì)操作。該現(xiàn)象稱(chēng)為假溢出。如圖3-6所示是數(shù)組大小為5的順序隊(duì)列中隊(duì)首、隊(duì)尾指針和隊(duì)列中元素的變化情況。因此,目前很少使用。第三十七頁(yè)，共五十四頁(yè)，編輯于2023年，星期三

(a)空隊(duì)列Q.frontQ.rear入隊(duì)3個(gè)元素a3a2a1Q.frontQ.rear(c)出隊(duì)3個(gè)元素Q.frontQ.rear(d)入隊(duì)2個(gè)元素a5a4Q.frontQ.rear圖3-6隊(duì)列示意圖第三十八頁(yè)，共五十四頁(yè)，編輯于2023年，星期三3.4.3

循環(huán)隊(duì)列為充分利用向量空間，克服上述“假溢出”現(xiàn)象的方法是：將為隊(duì)列分配的向量空間看成為一個(gè)首尾相接的圓環(huán)，并稱(chēng)這種隊(duì)列為循環(huán)隊(duì)列(CircularQueue)。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，隊(duì)首、隊(duì)尾指針仍要加1，朝前移動(dòng)。只不過(guò)當(dāng)隊(duì)首、隊(duì)尾指針指向向量上界(MAX_QUEUE_SIZE-1)時(shí)，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為：if(i+1==MAX_QUEUE_SIZE)i=0;elsei++;其中：i代表隊(duì)首指針(front)或隊(duì)尾指針(rear)第三十九頁(yè)，共五十四頁(yè)，編輯于2023年，星期三用模運(yùn)算可簡(jiǎn)化為：i=(i+1)%MAX_QUEUE_SIZE;顯然，為循環(huán)隊(duì)列所分配的空間可以被充分利用，除非向量空間真的被隊(duì)列元素全部占用，否則不會(huì)上溢。因此，真正實(shí)用的順序隊(duì)列是循環(huán)隊(duì)列。例：設(shè)有循環(huán)隊(duì)列QU[0，5]，其初始狀態(tài)是front=rear=0，各種操作后隊(duì)列的頭、尾指針的狀態(tài)變化情況如下圖3-7所示。123450(a)空隊(duì)列frontrear123450(b)d,e,b,g入隊(duì)frontdebgrear123450(c)d,e出隊(duì)bgfrontrear第四十頁(yè)，共五十四頁(yè)，編輯于2023年，星期三入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿(mǎn)時(shí)頭尾指針均相等。因此，無(wú)法通過(guò)front=rear來(lái)判斷隊(duì)列“空”還是“滿(mǎn)”。解決此問(wèn)題的方法是：約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿(mǎn)。即：◆rear所指的單元始終為空。123450(d)i,j,k入隊(duì)bgfrontijkrear123450(e)b,g出隊(duì)ijkrearfront123450(f)r,p,s,t入隊(duì)ijkfrontrprear圖3-7循環(huán)隊(duì)列操作及指針變化情況第四十一頁(yè)，共五十四頁(yè)，編輯于2023年，星期三◆循環(huán)隊(duì)列為空：front=rear。◆循環(huán)隊(duì)列滿(mǎn)：(rear+1)%MAX_QUEUE_SIZE

=front。循環(huán)隊(duì)列的基本操作1循環(huán)隊(duì)列的初始化SqQueueInit_CirQueue(void){SqQueueQ;Q.front=Q.rear=0;return(Q);}第四十二頁(yè)，共五十四頁(yè)，編輯于2023年，星期三

2入隊(duì)操作StatusInsert_CirQueue(SqQueueQ,ElemTypee)/*將數(shù)據(jù)元素e插入到循環(huán)隊(duì)列Q的隊(duì)尾*/{if((Q.rear+1)%MAX_QUEUE_SIZE==Q.front)returnERROR;/*隊(duì)滿(mǎn)，返回錯(cuò)誤標(biāo)志*/Q.Queue_array[Q.rear]=e;/*元素e入隊(duì)*/Q.rear=(Q.rear+1)%MAX_QUEUE_SIZE;/*隊(duì)尾指針向前移動(dòng)*/returnOK;/*入隊(duì)成功*/}第四十三頁(yè)，共五十四頁(yè)，編輯于2023年，星期三

3出隊(duì)操作StatusDelete_CirQueue(SqQueueQ,ElemType*x

)/*將循環(huán)隊(duì)列Q的隊(duì)首元素出隊(duì)*/{if(Q.front==Q.rear)returnERROR;/*隊(duì)空，返回錯(cuò)誤標(biāo)志*/*x=Q.Queue_array[Q.front];/*取隊(duì)首元素*/Q.front=(Q.front+1)%MAX_QUEUE_SIZE;

/*隊(duì)首指針向后移動(dòng)*/returnOK;}第四十四頁(yè)，共五十四頁(yè)，編輯于2023年，星期三1隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為鏈隊(duì)列，它是限制僅在表頭進(jìn)行刪除操作和表尾進(jìn)行插入操作的單鏈表。需要兩類(lèi)不同的結(jié)點(diǎn)：數(shù)據(jù)元素結(jié)點(diǎn)，隊(duì)列的隊(duì)首指針和隊(duì)尾指針的結(jié)點(diǎn)，如圖3-8所示。3.4.2

隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)數(shù)據(jù)元素結(jié)點(diǎn)類(lèi)型定義：typedefstructQnode{ElemTypedata;structQnode*next;}QNode;數(shù)據(jù)元素結(jié)點(diǎn)data指針結(jié)點(diǎn)frontrear圖3-8鏈隊(duì)列結(jié)點(diǎn)示意圖第四十五頁(yè)，共五十四頁(yè)，編輯于2023年，星期三指針結(jié)點(diǎn)類(lèi)型定義：typedefstructlink_queue{QNode*front；//隊(duì)頭指針Qnode*rear;//隊(duì)尾指針}Link_Queue;2鏈隊(duì)運(yùn)算及指針變化

鏈隊(duì)的操作實(shí)際上是單鏈表的操作，只不過(guò)是刪除在表頭進(jìn)行，插入在表尾進(jìn)行。插入、刪除時(shí)分別修改不同的指針。鏈隊(duì)運(yùn)算及指針變化如圖3-9所示。第四十六頁(yè)，共五十四頁(yè)，編輯于2023年，星期三圖3-9隊(duì)列操作及指針變化(a)空隊(duì)列frontrear∧(b)x入隊(duì)x∧frontrear(c)y再入隊(duì)y∧frontrearx(d)x出隊(duì)y∧xfrontrear第四十七頁(yè)，共五十四頁(yè)，編輯于2023年，星期三

3鏈隊(duì)列的基本操作⑴

鏈隊(duì)列的初始化LinkQueue*Init_LinkQueue(void){LinkQueue*Q;QNode*p;p=(QNode*)malloc(sizeof(QNode));/*開(kāi)辟頭結(jié)點(diǎn)*/p->next=NULL;Q=(LinkQueue*)malloc(sizeof(LinkQueue));

/*開(kāi)辟鏈隊(duì)的指針結(jié)點(diǎn)*/Q.front=Q.rear=p;return(Q);}第四十八頁(yè)，共五十四頁(yè)，編輯于2023年，星期三

⑵

鏈隊(duì)列的入隊(duì)操作

在已知隊(duì)列的隊(duì)尾插入一個(gè)元素e，即修改隊(duì)尾指針(Q.rear)。StatusInsert_CirQueue(LinkQueue*Q,ElemTypee)/*將數(shù)據(jù)元素e插入到鏈隊(duì)列Q的隊(duì)尾*/{p=(QNode*)malloc(sizeof(QNode));if(!p)returnERROR;/*申請(qǐng)新結(jié)點(diǎn)失敗，返回錯(cuò)誤標(biāo)志*/p->data=e;p->next=NULL;/*形成新結(jié)點(diǎn)*/Q.rear->next=p;Q.rear=p;/*新結(jié)點(diǎn)插入到隊(duì)尾*/ret