《數(shù)據(jù)結(jié)構(gòu)》課件第3章

第3章棧和隊(duì)列3.1棧3.2隊(duì)列本章小結(jié)習(xí)題三實(shí)訓(xùn)3-1棧的應(yīng)用實(shí)訓(xùn)3-2隊(duì)列的應(yīng)用

【教學(xué)目標(biāo)】棧和隊(duì)列是兩種特殊并且非常重要的線性表。通過(guò)對(duì)本章學(xué)習(xí)，掌握棧和隊(duì)列的概念和特征，掌握棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，掌握棧和隊(duì)列的基本操作的實(shí)現(xiàn)算法——進(jìn)棧、出棧、判斷?？?、入隊(duì)、出隊(duì)、判斷隊(duì)列空和隊(duì)滿，并能熟練地運(yùn)用棧和隊(duì)列解決實(shí)際問(wèn)題。棧和隊(duì)列是兩種重要的數(shù)據(jù)結(jié)構(gòu)，也是兩種特殊的線性結(jié)構(gòu)。從數(shù)據(jù)的邏輯結(jié)構(gòu)角度來(lái)看，棧和隊(duì)列是線性表；從操作的角度來(lái)看，棧和隊(duì)列的基本操作是線性表操作的子集，是操作受限制的線性表。棧和隊(duì)列在操作系統(tǒng)、編譯原理、大型應(yīng)用軟件系統(tǒng)中得到了廣泛的應(yīng)用。3.1棧3.1.1棧的定義和基本操作

1.棧的定義棧(Stack)是一種限定性的線性表，是將線性表的插入和刪除運(yùn)算限制在表的一端進(jìn)行。通常將表中允許進(jìn)行插入、刪除操作的一端稱為棧頂(Top)，因此棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)變化的，它由一個(gè)稱為棧頂指針的位置指示器指示。同時(shí)表的另一端被稱為棧底(Bottom)，棧底是固定的。非空棧如圖3.1(a)所示。當(dāng)棧中沒(méi)有元素時(shí)稱為空棧，如圖3.1(b)所示。棧的插入操作被形象地稱為進(jìn)棧或入棧，刪除操作稱為出?；蛲藯?。圖3.1棧結(jié)構(gòu)示意圖(a)非空棧；(b)空棧假設(shè)有一個(gè)棧S=(a1,a2,…,ai-1,ai,ai+1,…,an)，如果a1先進(jìn)棧，則an最后進(jìn)棧。因?yàn)檫M(jìn)棧和出棧元素都只能在棧頂一端進(jìn)行，所以每次出棧的元素總是當(dāng)前棧中棧頂?shù)脑?，它是最后進(jìn)棧的元素，而最先進(jìn)棧的元素要到最后才能出棧。在日常生活中，有許多類似棧的例子。例如將洗凈的盤(pán)子放入消毒桶時(shí)，總是一個(gè)接一個(gè)地往上摞(相當(dāng)于進(jìn)棧)；取出盤(pán)子時(shí)，則是從最上面一個(gè)接一個(gè)地往外拿(相當(dāng)于出棧)，最后取出的是最先放進(jìn)去的那個(gè)盤(pán)子。因此，棧又被稱為后進(jìn)先出(LastInFirstOut,LIFO)的線性表。

2.棧的基本操作棧的基本操作主要有以下七種：

(1)?InitStack(S)。操作前提：S為未初始化的棧。操作結(jié)果：將S初始化為空棧。

(2)?ClearStack(S)。操作前提：棧S已經(jīng)存在。操作結(jié)果：將棧S置成空棧。

(3)?IsEmpty(S)。操作前提：棧S已經(jīng)存在。操作結(jié)果：判?？蘸瘮?shù)，若S為空棧，則函數(shù)值為T(mén)RUE或1，否則為FALSE或0。

(4)?IsFull(S)。操作前提：棧S已經(jīng)存在。操作結(jié)果：判棧滿函數(shù)，若S棧已滿，則函數(shù)值為T(mén)RUE或1，否則為FALSE或0。

(5)?Push(S,x)。操作前提：棧S已經(jīng)存在。操作結(jié)果：在S的頂部插入(亦稱壓入)元素x；若S棧未滿，將x插入棧頂位置，若棧已滿，則返回FALSE或0，表示操作失敗，否則返回TRUE或1。

(6)?Pop(S)。操作前提：棧S已經(jīng)存在。操作結(jié)果：刪除(亦稱彈出)棧S的頂部元素，返回該值；若棧為空，返回值為NULL，表示操作失敗。

(7)?GetTop(S)。操作前提：棧S已經(jīng)存在。操作結(jié)果：取棧S的頂部元素。與Pop(S)不同之處在于GetTop(S)不改變棧頂?shù)奈恢谩?.1.2棧的順序存儲(chǔ)結(jié)構(gòu)順序棧是用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)由于棧的操作的特殊性，還必須附設(shè)一個(gè)位置指針top(棧頂指針)來(lái)動(dòng)態(tài)地指示棧頂元素在順序棧中的位置。通常以top=-1表示空棧。順序棧的存儲(chǔ)結(jié)構(gòu)可以用C語(yǔ)言中的一維數(shù)組來(lái)表示。棧的順序存儲(chǔ)結(jié)構(gòu)定義用C語(yǔ)言描述如下：#defineMAXSIZE50#defineElemtypeint /*棧中元素類型，此處以int為例*/typedefstruct{Elemtypedata[MAXSIZE]; /*用來(lái)存放棧中元素的一維數(shù)組*/inttop; /*用來(lái)存放棧頂元素的下標(biāo)*/}SeqStack;SeqStack*S； /*定義指向棧的指針*/

top指針是在棧上進(jìn)行插入或刪除操作的依據(jù)，S->top?=?-1表示?？?，S->top?=?MAXSIZE-1表示棧滿，這是在順序棧的基本操作中必須考慮到的兩個(gè)重要條件。假設(shè)MAXSIZE為6，棧中最多可存放6個(gè)元素，即S->data[0]至S->data[5]。棧頂指針S->top在元素進(jìn)棧時(shí)做加1運(yùn)算，元素出棧時(shí)做減1運(yùn)算。圖3.2說(shuō)明了順序棧進(jìn)出操作時(shí)棧中元素和棧頂指針的關(guān)系。其中，圖(a)表示空棧狀態(tài)，圖(b)表示一個(gè)元素A入棧后的狀態(tài)，圖(c)表示棧滿狀態(tài)，圖(d)表示棧滿后再刪除元素F之后的狀態(tài)。圖3.2順序棧進(jìn)出操作示意圖(a)空棧；(b)元素A進(jìn)棧；(c)棧滿；(d)元素F出棧以下是C語(yǔ)言描述的在順序棧上實(shí)現(xiàn)棧的幾個(gè)基本操作的算法：

(1)初始化空棧。voidinitStack(SeqStack*S)

/*順序棧初始化為一個(gè)空棧*/{ S->top=-1;}

(2)判棧空。intisEmpty(SeqStack*S)

/*判棧S為空棧時(shí)返回值為真，反之為假*/{return(S->top==-1?1:0);}

(3)判棧滿。intisFull(SeqStack*S){return(S->top==MAXSIZE-1?1:0);}

(4)進(jìn)棧。intpush(SeqStack*S,Elemtypex)

/*元素x入棧*/{

if(S->top==MAXSIZE-1)

{printf(“棧滿\n”);

/*棧上溢，提示出錯(cuò)*/

return(0);}

else

{

S->top++;

/*棧頂指針加1*/

S->data[S->top]=x;

/*給棧頂元素賦值*/

return(1);

}}

(5)出棧。intpop(SeqStack*S,Elemtype*x){/*將棧S的棧頂元素彈出，其值復(fù)制到x所指的存儲(chǔ)空間中*/if(S->top==-1) /*棧為空*/return(0);

else{*x=S->data［S->top］;S->top--; /*修改棧頂指針*/return(1);}}

(6)取棧頂元素。intgettop(SeqStackS,Elemtype*x){/*將棧S的棧頂元素值復(fù)制到x所指的存儲(chǔ)空間中，但棧頂指針保持不變*/

if(S->top==-1) /*棧為空*/ return(0);

else

{

*x=S->data［S->top］;

return(1);

}}3.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧也可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示，這種存儲(chǔ)結(jié)構(gòu)的棧稱為鏈棧。在一個(gè)鏈棧中，為方便進(jìn)行插入和刪除操作，一般指定鏈表頭為棧頂，鏈尾為棧底。鏈棧的數(shù)據(jù)類型用C語(yǔ)言描述如下：#defineElemtypeint

/*棧中元素類型，此處以int為例*/typedefstructsnode{

Elemtypedata;

structsnode*next;

｝LinkStackNode；typedefLinkStackNode*LinkStack;

top是棧頂指針，它是指針類型變量，top唯一地確定一個(gè)鏈棧。對(duì)于不帶頭結(jié)點(diǎn)的鏈棧，棧頂元素為top，當(dāng)top?=?NULL時(shí)，該鏈棧為空棧；帶頭結(jié)點(diǎn)的鏈棧的棧頂元素為top->next，棧為空的條件是top->next?=?NULL，如圖3.3所示。圖3.3帶頭結(jié)點(diǎn)的鏈棧示意下面討論在帶頭結(jié)點(diǎn)的鏈棧上實(shí)現(xiàn)進(jìn)棧和出棧操作的算法。

1.進(jìn)棧操作算法分析：當(dāng)要將一個(gè)新元素x插入鏈棧時(shí)，可動(dòng)態(tài)地向系統(tǒng)申請(qǐng)一個(gè)結(jié)點(diǎn)p的存儲(chǔ)空間，將新元素x寫(xiě)入新結(jié)點(diǎn)p的數(shù)據(jù)域，然后將p結(jié)點(diǎn)插入在top的后繼位置。算法用C語(yǔ)言描述如下：intpush(LinkStacktop,Elemtypex)/*將數(shù)據(jù)元素x壓入棧top中*/{ LinkStackNode*p; p=(LinkStackNode*)malloc(sizeof(LinkStackNode)); if(p==NULL)return(0); /*申請(qǐng)空間失敗*/ p->data=x; p->next=top->next; /*新結(jié)點(diǎn)插入在top的后繼位置*/ top->next=p; return(1);}

2.出棧操作算法分析：當(dāng)棧頂元素p出棧時(shí)，先取出p的值，再刪除p。算法用C語(yǔ)言描述如下：intpop(LinkStacktop,Elemtype*x){/*將棧top的棧頂元素彈出，放到x所指的存儲(chǔ)空間中*/

LinkStackNode*p;

p=top->next; /*p指向棧頂元素*/

if(p==NULL) /*棧為空*/

return(0);

top->next=p->next; /*從鏈中刪除p結(jié)點(diǎn)*/*x=p->data;

free(temp); /*釋放存儲(chǔ)空間*/

return(1);}3.1.4棧與遞歸的實(shí)現(xiàn)棧非常重要的一個(gè)應(yīng)用是在程序設(shè)計(jì)語(yǔ)言中實(shí)現(xiàn)遞歸。遞歸是指在定義自身的同時(shí)又出現(xiàn)了對(duì)自身的調(diào)用。如果一個(gè)函數(shù)在其定義體內(nèi)直接調(diào)用自己，則稱其為直接遞歸函數(shù)；如果一個(gè)函數(shù)經(jīng)過(guò)一系列的中間調(diào)用語(yǔ)句，通過(guò)其它函數(shù)間接調(diào)用自己，則稱其為間接遞歸函數(shù)。

1.遞歸的定義遞歸就是一個(gè)事件或?qū)ο蟛糠值赜勺约航M成，或者由它自己定義。例如，求階乘就是遞歸的一個(gè)典型的例子：斐波那契數(shù)列也是一個(gè)典型例子：或n?=?2遞歸算法包括遞推和回歸兩部分：

(1)遞推就是將復(fù)雜問(wèn)題的求解“推到”對(duì)較簡(jiǎn)單問(wèn)題的求解，如將求n!推到求(n-1)!，(n-2)!……使用遞推時(shí)應(yīng)注意到，遞推應(yīng)有終止之時(shí)，如求n!時(shí)，以n=0，0!＝1為遞推的終止條件。

(2)回歸就是指當(dāng)“簡(jiǎn)單問(wèn)題得到解后，回歸到原問(wèn)題的解上”。例如在求n！時(shí)，當(dāng)計(jì)算完(n-l)！后，回歸到計(jì)算n?×?(n-1)!上。常見(jiàn)的遞歸方法有兩種:

(1)直接遞歸就是函數(shù)直接調(diào)用本身，如圖3.4(a)所示。

(2)間接遞歸就是一個(gè)函數(shù)如果在調(diào)用其它函數(shù)時(shí)，又產(chǎn)生了對(duì)自身的調(diào)用，如圖3.4(b)所示。圖3.4遞歸調(diào)用(a)直接遞歸；(b)間接遞歸

2.遞歸的實(shí)現(xiàn)

1)遞歸實(shí)現(xiàn)的優(yōu)點(diǎn)遞歸既是強(qiáng)有力的數(shù)學(xué)方法，也是程序設(shè)計(jì)中一個(gè)很有用的工具。其特點(diǎn)是對(duì)遞歸問(wèn)題描述簡(jiǎn)捷，結(jié)構(gòu)清晰，程序的正確性容易證明。

2)用遞歸算法求解問(wèn)題的要素遞歸函數(shù)又稱為自調(diào)用函數(shù)，函數(shù)(或過(guò)程)直接或間接調(diào)用自己的算法，稱為遞歸算法。遞歸過(guò)程是利用棧的技術(shù)來(lái)實(shí)現(xiàn)的，只不過(guò)這個(gè)過(guò)程是系統(tǒng)自動(dòng)完成的。遞歸算法的要點(diǎn)如下：

(1)所需解決的問(wèn)題可以轉(zhuǎn)化成另一個(gè)問(wèn)題，而解決新問(wèn)題的方法與原始問(wèn)題的解決方法相同，只是處理的對(duì)象不同，并且它們的某些參數(shù)是有規(guī)律地變化的。

(2)必須具備終止遞歸的條件。程序中不應(yīng)該出現(xiàn)無(wú)終止的遞歸調(diào)用，在某一特定的條件下，可以得到定解，而不再使用遞歸定義。

3)設(shè)計(jì)遞歸算法的方法

(1)尋找方法，將問(wèn)題化為原問(wèn)題的子問(wèn)題求解(例如n!?=?n?×?(n-1)!)。

(2)設(shè)計(jì)遞歸出口，確定遞歸終止條件(例如求解n!，當(dāng)n?=?1時(shí)，n!=?1)。

3.遞歸的實(shí)現(xiàn)機(jī)制在一個(gè)程序的運(yùn)行期間調(diào)用另一個(gè)過(guò)程函數(shù)時(shí)，在運(yùn)行被調(diào)用過(guò)程函數(shù)之前，計(jì)算機(jī)系統(tǒng)必須先完成以下工作：

(1)為被調(diào)用的過(guò)程函數(shù)分配數(shù)據(jù)區(qū)。函數(shù)的數(shù)據(jù)區(qū)中包括了函數(shù)所需的各種局部變量，如函數(shù)的形參、函數(shù)執(zhí)行過(guò)程中所需的臨時(shí)變量等。舉一個(gè)簡(jiǎn)單例子，在計(jì)算表達(dá)式x+y+z時(shí)，系統(tǒng)就要分配一個(gè)臨時(shí)的變量w存放x＋y的值，再把w和z的值相加。

(2)將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用的過(guò)程函數(shù)保存。

(3)把控制權(quán)轉(zhuǎn)移到被調(diào)用過(guò)程函數(shù)的入口。在被調(diào)用的過(guò)程函數(shù)運(yùn)行結(jié)束后返回到調(diào)用函數(shù)之前，也必須完成以下工作：

(1)保存被調(diào)用過(guò)程函數(shù)的計(jì)算結(jié)果。

(2)釋放被調(diào)用過(guò)程函數(shù)占用的數(shù)據(jù)區(qū)。

(3)恢復(fù)被調(diào)用過(guò)程函數(shù)保存的返回地址，并把控制權(quán)轉(zhuǎn)移到調(diào)用函數(shù)中的調(diào)用語(yǔ)句的下一條語(yǔ)句。上面是一個(gè)非遞歸的函數(shù)調(diào)用過(guò)程。在遞歸函數(shù)的調(diào)用和返回過(guò)程中是滿足先調(diào)用后返回的執(zhí)行次序的，即最先開(kāi)始調(diào)用的遞歸函數(shù)需要最后返回。所以，支持遞歸的程序設(shè)計(jì)語(yǔ)言系統(tǒng)其遞歸函數(shù)的數(shù)據(jù)區(qū)應(yīng)設(shè)計(jì)成棧的形式。這樣每次遞歸調(diào)用時(shí)都把當(dāng)前的調(diào)用參數(shù)、返回地址等壓入棧形式的遞歸函數(shù)數(shù)據(jù)區(qū)；當(dāng)本次調(diào)用結(jié)束時(shí)，系統(tǒng)退棧，并轉(zhuǎn)移控制權(quán)到調(diào)用函數(shù)繼續(xù)執(zhí)行，直到?？胀顺鲞f歸函數(shù)，返回調(diào)用函數(shù)。所以，計(jì)算機(jī)在執(zhí)行遞歸算法時(shí)，系統(tǒng)首先為遞歸調(diào)用建立一個(gè)棧，稱為遞歸工作棧。該棧的元素包括參數(shù)、局部變量和調(diào)用后的返回地址等信息。在每次調(diào)用遞歸之前，把本次算法中所有的參數(shù)、局部變量的當(dāng)前值和調(diào)用后的返回地址等壓入棧頂。在每次執(zhí)行遞歸調(diào)用結(jié)束之后，又把棧頂元素的信息彈出，分別賦給相應(yīng)的參數(shù)和局部變量，以便它恢復(fù)到調(diào)用前的狀態(tài)，然后返回地址所指定的位置，繼續(xù)執(zhí)行后續(xù)的指令。下面介紹子程序的調(diào)用，子程序的調(diào)用與返回處理是利用棧完成的。當(dāng)要去執(zhí)行調(diào)用的子程序前，先將下一條指令的地址(返回地址)保存到棧中，然后再執(zhí)行子程序。當(dāng)子程序執(zhí)行完成后，再?gòu)臈Ｖ腥〕龇祷氐刂贰Ｆ溥^(guò)程如圖3.5所示，當(dāng)主程序A調(diào)用子程序B時(shí)，首先將返回地址b壓入棧中，同樣，在子程序B調(diào)用子程序C時(shí)，需將返回地址c壓入棧中，當(dāng)子程序C執(zhí)行完畢后，就從棧中彈出返回地址c，回到子程序B，當(dāng)子程序B執(zhí)行完畢后，就從棧中彈出返回地址b，回到主程序A。圖3.5遞歸調(diào)用中棧的變化過(guò)程下面用求n!?為例來(lái)說(shuō)明遞歸的實(shí)現(xiàn)。使用遞歸方法求n!的算法，根據(jù)階乘的定義它可以表示為：由n!?的定義可以看出它是一種遞歸的定義，當(dāng)n=0時(shí)，是遞歸子程序的終止條件。用C語(yǔ)言描述的遞歸算法如下：

longfac(intn) /*遞歸調(diào)用函數(shù)*/{if(n<0)return(0);elseif(n==0)return(1);elsereturn(fac(n-1)*n);}3.2隊(duì)列3.2.1隊(duì)列的定義及基本操作隊(duì)列(Queue)也是一種特殊的線性表。它只允許在表的一端插入元素，而在另一端刪除元素，允許刪除操作的一端稱為隊(duì)頭(front)，允許插入操作的一端稱為隊(duì)尾(rear)。上述規(guī)定決定了先進(jìn)隊(duì)列的元素先出隊(duì)列，就如平時(shí)排隊(duì)買東西一樣。因此隊(duì)列又稱做先進(jìn)先出(FirstInFirstOut)的線性表，簡(jiǎn)稱FIFO表。假設(shè)有隊(duì)列Q?=?(a1,a2,…,an)，則隊(duì)列中的元素是按a1,a2,…,an的次序進(jìn)隊(duì)，而第一個(gè)出隊(duì)列的元素是a1，第二個(gè)出隊(duì)列的是a2，只有在ai-1出隊(duì)列后，ai才可以出隊(duì)列(1≤i≤n)。當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。隊(duì)列結(jié)構(gòu)示意圖如圖3.6所示。圖3.6隊(duì)列結(jié)構(gòu)示意圖隊(duì)列的基本操作主要有以下七種：

(1)?InitQueue(&Q)。初始化操作。設(shè)置一個(gè)空隊(duì)列。

(2)?IsEmpty(Q)。判空操作。若隊(duì)列為空，則返回1，否則返回0。

(3)?EnterQueue(&Q，x)。進(jìn)隊(duì)操作。在隊(duì)列Q的隊(duì)尾插入x。操作成功，返回值為1，否則返回值為0。

(4)?DeleteQueue(&Q,&x)。出隊(duì)操作。使隊(duì)列Q的隊(duì)頭元素出隊(duì)，并用x帶回其值。操作成功，返回值為1，否則返回值為0。

(5)?GetHead(Q,&x)。取隊(duì)頭元素操作。用x取得隊(duì)頭元素的值。操作成功，返回值為1，否則返回值為0。

(6)?ClearQueue(&Q)。隊(duì)列置空操作。將隊(duì)列Q置為空隊(duì)列。

(7)?DestroyQueue(&Q)。隊(duì)列銷毀操作。釋放隊(duì)列的空間。3.2.2隊(duì)列的順序存儲(chǔ)

1.順序隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列。和順序棧不同的是，在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲(chǔ)單元依次存放所有元素之外，由于隊(duì)列的插入和刪除分別在隊(duì)列的兩端進(jìn)行，隊(duì)頭和隊(duì)尾的位置是變化的，因此需附設(shè)兩個(gè)指針front和rear，分別用來(lái)指示隊(duì)頭和隊(duì)尾的位置。在初始化隊(duì)列時(shí)，隊(duì)列為空，在C語(yǔ)言中為了描述方便，通常約定front?=?rear?=?-1，如圖3.7所示；每當(dāng)插入新的隊(duì)尾元素時(shí)“尾指針增1”，即rear++，如圖3.8所示；每當(dāng)刪除隊(duì)頭元素時(shí)“頭指針增1”，即front++，如圖3.9所示。在非空隊(duì)列中，頭指針front總是指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針rear總是指向當(dāng)前的隊(duì)尾元素的位置。順序隊(duì)列為空的條件是front?=?rear。圖3.7空順序隊(duì)列圖3.8插入4個(gè)元素后的順序隊(duì)列圖3.9刪除2個(gè)元素后的順序隊(duì)列從圖3.9中可以看出，順序隊(duì)列為空的條件是front?=?rear，假設(shè)順序隊(duì)列的最大長(zhǎng)度為MAXSIZE，則順序隊(duì)列為滿的條件是rear?=?MAXSIZE-1，隊(duì)列長(zhǎng)度len?=?rear-front。注意，判斷順序隊(duì)列是否已滿，能否進(jìn)行插入操作，不是看隊(duì)列長(zhǎng)度是否達(dá)到最大，而是只看rear?+?1的值是否越界。順序隊(duì)列的數(shù)據(jù)類型用C語(yǔ)言描述如下：#defineElemtypeint#defineMAXSIZE50

/*隊(duì)列的最大長(zhǎng)度*/typedefstruct{

Elemtypedata[MAXSIZE]；

intfront，rear； /*確定隊(duì)頭、隊(duì)尾位置的兩個(gè)變量*/｝SeqQueue； /*順序隊(duì)列的類型*/

(1)初始化操作。initSeqQueue(SeqQueue*q)｛

q->front=-1;

q->rear=-1;｝

(2)出隊(duì)操作。出隊(duì)操作即刪除隊(duì)列的隊(duì)頭元素，front指針加1。算法用C語(yǔ)言描述如下：intdeleteSeqQueue(SeqQueue*q,Elemtype*x){

if(q->front==q->rear) /*隊(duì)列空，不能刪除*/

return(0);

else{

q->front++;*x=(q->data[q->front]);

return(1); /*刪除成功*/｝}

(3)入隊(duì)操作。入隊(duì)操作即在隊(duì)尾插入元素，將rear指針加1，數(shù)據(jù)存入rear指針指到的位置，見(jiàn)圖3.10和圖3.11。圖3.10待插入隊(duì)列圖3.11在隊(duì)尾添加元素G后的示意圖隊(duì)尾插入算法用C語(yǔ)言描述如下：intenterSeqQueue(SeqQueue*q,intx){

if(q->rear>=MAXSIZE-1)

return(0)； /*隊(duì)列已滿，插入失敗*/

else

{

(q->rear)++;

q->data[q->rear]=x;

return(1)； /*插入成功*/｝}在順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列中，必須要討論順序隊(duì)列的數(shù)組越界(或上溢)問(wèn)題，假設(shè)一個(gè)隊(duì)列最多能存放MAXSIZE(MAXSIZE=9)個(gè)元素，如圖3.12所示，隊(duì)列中已有MAXSIZE個(gè)元素，即隊(duì)列已滿，如果在隊(duì)列中再插入一個(gè)元素J，那么就出現(xiàn)了數(shù)組越界或上溢的現(xiàn)象。圖3.12隊(duì)列已滿，長(zhǎng)度達(dá)到最大上面是整個(gè)隊(duì)列中已裝滿MAXSIZE個(gè)元素的情況?？墒羌词箘h除了隊(duì)列頭元素，當(dāng)隊(duì)列處于圖3.13所示狀態(tài)時(shí)，如果再繼續(xù)插入新的隊(duì)尾元素，也會(huì)出現(xiàn)數(shù)組越界或上溢的現(xiàn)象，這種溢出是一種假溢出，因?yàn)殛?duì)列的可用空間并未占滿。解決假溢出最常用的辦法是使用循環(huán)隊(duì)列。圖3.13隊(duì)列已滿，長(zhǎng)度未達(dá)到最大

2.循環(huán)隊(duì)列循環(huán)隊(duì)列是將存儲(chǔ)隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的圓環(huán)，即將表示隊(duì)列的數(shù)組元素Q[0]看成是Q[MAXSIZE-1]的直接后繼，如圖3.14所示。在循環(huán)隊(duì)列中，當(dāng)rear?=?MAXSIZE-1時(shí)，只要Q[0]是空閑的，下一個(gè)元素就可放入Q[0]中。在循環(huán)隊(duì)列中，可以用“求?！边\(yùn)算來(lái)實(shí)現(xiàn)隊(duì)頭指針和隊(duì)尾指針的值的計(jì)算。圖3.14循環(huán)隊(duì)列示意圖入隊(duì)操作時(shí)，隊(duì)尾指針加1可描述為：q->rear?=?(q->rear?+?1)%MAXSIZE;出隊(duì)操作時(shí)，隊(duì)頭指針加1可描述為：q->front?=?(q->front?+?1)%MAXSIZE。如圖3.15(a)所示的循環(huán)隊(duì)列中，隊(duì)列頭元素是A，隊(duì)列尾元素是C，之后D、E和F相繼插入，則隊(duì)列空間均被占滿，如圖3.15(b)所示，此時(shí)front=rear；反之，若A、B、C相繼被從圖3.15(a)所示的循環(huán)隊(duì)列中刪除，使隊(duì)列呈“空”的狀態(tài)，如圖3.15(c)所示，此時(shí)亦存在關(guān)系式front=rear。圖3.15循環(huán)隊(duì)列的頭尾指針(a)一般情況；(b)隊(duì)列滿時(shí)；(c)空隊(duì)列由此可見(jiàn)，只根據(jù)等式front?=?rear無(wú)法判別循環(huán)隊(duì)列是“空”還是“滿”。解決方法主要有兩種。一種是另設(shè)一個(gè)標(biāo)志位flag以區(qū)別隊(duì)列是空還是滿。當(dāng)插入一個(gè)元素后，如果出現(xiàn)front?=?rear的情況，表示隊(duì)列已滿，則flag?=?1；當(dāng)刪除一個(gè)元素后，如果出現(xiàn)front=rear的情況，表示隊(duì)列為空，則flag?=?0。當(dāng)出現(xiàn)front?=?rear時(shí)，只要看flag標(biāo)記的值是0還是1，就可以判斷目前實(shí)際的空滿狀態(tài)。另一種方法是少用一個(gè)元素空間，即不用front所指空間，以隊(duì)尾指針加1等于隊(duì)頭指針為判斷隊(duì)滿的條件，即當(dāng)(rear?+?l)%MAXSIZE?=?front時(shí)表示隊(duì)滿，當(dāng)front?=?rear時(shí)表示隊(duì)空。圖3.16是循環(huán)隊(duì)列為滿的示意圖。圖3.16循環(huán)隊(duì)列為滿的示意圖在第二種方法中，當(dāng)rear≥front時(shí)，循環(huán)隊(duì)列的長(zhǎng)度len?=?rear-front；當(dāng)rear＜front時(shí)，len?=?rear-front+MAXSIZE。二者統(tǒng)一起來(lái)，即len?=?(rear?+?MAXSIZE-front)%MAXSIZE。下面給出循環(huán)隊(duì)列的幾種基本操作的實(shí)現(xiàn)算法。

(1)初始化隊(duì)列。設(shè)front與rear分別為隊(duì)頭和隊(duì)尾指針。采用少用一個(gè)元素空間的方法，即循環(huán)隊(duì)列的front所指空間不用，隊(duì)列中的第1個(gè)元素是front的后繼，rear指向隊(duì)尾元素。初始時(shí)，令front與rear為0。initQueue(SeqQueue*q){

q->front=q->rear=0;}

(2)判隊(duì)空。intqueueEmpty(SeqQueue*q){

if(q->rear==q->front)

return1;

else

return0;}

(3)取隊(duì)頭元素。intgetHead(SeqQueue*q,Elemtype*x){

if(queueEmpty(q))

{

printf("SeqQueueisempty");

return0;}else{

*x=q->data[(q->front+1)%MAXSIZE];

return1;}}

(4)入隊(duì)操作。

intenterQueue(SeqQueue*q,Elemtype*x)

/*將新元素x插入隊(duì)列*q的隊(duì)尾*/

{

if((q->rear+1)%MAXSIZE==q->front)

{

printf("SeqQueueisfull");return0；

}else{q->rear=(q->rear+1)%MAXSIZE;q->data[q->rear]=x;}}

(5)出隊(duì)操作。刪除隊(duì)列的隊(duì)頭元素，并返回該元素的值。

intdeleteQueue(SeqQueue*q,Elemtype*x)

{

if(queueEmpty(q))

{

printf("SeqQueueisempty");

return0;

}else{

q->front=(q->front+1)%MAXSIZE;*x=q->data[q->front];

return1;}}如果用戶的應(yīng)用程序中沒(méi)有循環(huán)隊(duì)列，則必須為它設(shè)定一個(gè)最大隊(duì)列長(zhǎng)度；若用戶無(wú)法預(yù)估所用隊(duì)列的最大長(zhǎng)度，則最好采用鏈隊(duì)列。3.2.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的隊(duì)列簡(jiǎn)稱為鏈隊(duì)列。它是僅在表頭刪除和表尾插入的單鏈表。一個(gè)鏈隊(duì)列要在表頭刪除和在表尾插入，顯然需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針，所以鏈隊(duì)列是一個(gè)帶頭指針和尾指針的單鏈表。為使用方便通常添加一個(gè)頭結(jié)點(diǎn)。鏈隊(duì)列用C語(yǔ)言可以描述如下：

#defineElemtypeint /*定義數(shù)據(jù)類型*/

typedefstructnode /*鏈表結(jié)點(diǎn)類型定義*/

{

Elemtypedata;

structnode*next;

}Node;typedefstruct{

Node*front,*rear;}LinkQueue;LinkQueue*q;當(dāng)一個(gè)隊(duì)列*q為空時(shí)，front=rear，其頭指針和尾指針都指向頭結(jié)點(diǎn)，如圖3.17所示。非空鏈隊(duì)列如圖3.18所示。圖3.17空鏈隊(duì)列圖3.18非空鏈隊(duì)列判斷鏈隊(duì)列為空的條件是：頭指針和尾指針均指向頭結(jié)點(diǎn)。鏈隊(duì)列的基本操作主要是入隊(duì)列和出隊(duì)列操作，其操作方法是對(duì)單鏈表進(jìn)行插入和刪除操作的特殊情況。圖3.19是入隊(duì)列和出隊(duì)列操作的示意圖。圖3.19隊(duì)列運(yùn)算指針變化情況(a)空隊(duì)列；(b)元素A1入隊(duì)列；(c)元素A2入隊(duì)列；(d)元素A1出隊(duì)列；(e)元素A2出隊(duì)列，隊(duì)列空從以上分析可以看出，插入在表尾進(jìn)行，rear?=?rear->next；刪除在表頭進(jìn)行，但頭指針front始終沒(méi)有發(fā)生變化，變化的是front->next；而當(dāng)刪除最后一個(gè)結(jié)點(diǎn)(front->next?=?=?rear)時(shí)，還要調(diào)整rear?=?NULL。下面給出鏈隊(duì)列的幾種基本操作的實(shí)現(xiàn)算法：

(1)初始化。

intinitQueue(LinkQueue*q)

/*將q初始化為一個(gè)空的鏈隊(duì)列*/

{

q->front=(Node*)malloc(sizeof(Node));

if(q->front!=NULL)

{

q->front->next=NULL;q->rear=q->front;return(1);}elsereturn(0); /*溢出！*/}

(2)判空隊(duì)。

intqueueEmpty(LinkQueue*q){

if(q->front==q->rear)

return(1);elsereturn(0);

｝

(3)入隊(duì)操作。intenterQueue(LinkQueue*q,Elemtypex) /*將數(shù)據(jù)元素x插入到隊(duì)列q中*/{

Node*s;

s=(Node*)malloc(sizeof(Node));

if(s!=NULL)

{ s->data=x; s->next=NULL; q->rear->next=s; q->rear=s; return(1);} else

return(0);

/*溢出！*/}

(4)出隊(duì)操作。intdeleteQueue(LinkQueue*q,Elemtype*x)

/*將隊(duì)列q的隊(duì)頭元素出隊(duì)，并存放到x所指向的存儲(chǔ)空間中*/{

Node*s;

if(q->front==q->rear)

return(0);

s=q->front->next;q->front->next=s->next;

/*隊(duì)頭元素s出隊(duì)*/if(q->rear==s) /*如果隊(duì)中只有一個(gè)元素s，則s出隊(duì)后成為空隊(duì)*/q->rear=q->front;*x=s->data;free(s); /*釋放存儲(chǔ)空間*/return(1);}本章小結(jié)棧和隊(duì)列是兩種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，它們都是操作受到限制的線性表。棧的插入和刪除均是在棧頂進(jìn)行，它是后進(jìn)先出的線性表；隊(duì)列的插入在隊(duì)尾，刪除在隊(duì)頭，它是先進(jìn)先出的線性表。當(dāng)解決具有先進(jìn)先出(或后進(jìn)先出)特性的實(shí)際問(wèn)題時(shí)，可以使用隊(duì)列(或棧)這類數(shù)據(jù)結(jié)構(gòu)來(lái)求解。和線性表類似，依照存儲(chǔ)表示的不同，棧有順序棧和鏈棧，隊(duì)列有順序隊(duì)列和鏈隊(duì)列兩種，而實(shí)際使用的順序隊(duì)列是循環(huán)隊(duì)列。在隊(duì)列中解決假溢出的方法有三種：一是每刪除一個(gè)元素后就將整個(gè)隊(duì)列的元素向隊(duì)頭移動(dòng)一個(gè)位置；二是在發(fā)生假溢出時(shí)將整個(gè)隊(duì)列中的元素向隊(duì)頭移動(dòng)，直到front=-1為止；三是采用循環(huán)隊(duì)列。在非循環(huán)的順序隊(duì)列中判斷隊(duì)空的條件是front?=?rear，判斷隊(duì)滿的條件是rear?=?MAXSIZE-1；在循環(huán)隊(duì)列中判斷隊(duì)空的條件是front?=?rear。而判斷隊(duì)滿的方法有兩種：一種是設(shè)置一個(gè)判斷隊(duì)滿的標(biāo)志位；另一種是少用一個(gè)元素空間，用front?=?(rear+l)％MAXSIZE作為隊(duì)滿的條件。本章還介紹了順序棧、鏈棧、循環(huán)隊(duì)列和鏈隊(duì)列的一些基本操作的實(shí)現(xiàn)算法，并舉出了棧和隊(duì)列在實(shí)際應(yīng)用中的例子。習(xí)題三

一、填空題

1.棧是限定僅在表尾進(jìn)行

操作的線性表，表頭端稱為

，表尾端稱為

，棧的操作特性是

。

2.隊(duì)列是限定僅在表尾進(jìn)行

和在表頭端進(jìn)行

的線性表，隊(duì)列的操作特性是

。

3.以下定義了一個(gè)順序棧：

#defineMAXSTACK500typedefstruct{chardata[MAXSTACK];inttop;}sqstack;sqstackss;?？盏臈l件是：

，棧滿的條件是：

；棧頂元素的表達(dá)式是：

，棧底元素的表達(dá)式是：

。

二、簡(jiǎn)答題

1.設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序插入在入棧操作之間，請(qǐng)回答下述問(wèn)題：

(1)若入、出棧次序?yàn)镻ush(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop()，則出棧的數(shù)字序列是什么(這里Push(i)表示i進(jìn)棧，Pop()表示出棧)?

(2)能否得到出棧序列1423和1432??并說(shuō)明為什么不能得到或者如何得到。

(3)請(qǐng)分析1，2，3，4的24種排列中，哪些序列可以通過(guò)相應(yīng)的入、出棧操作得到。

2.循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么?如何判別它的空和滿?

三、算法設(shè)計(jì)題

1.回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫(xiě)一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧。)

2.括號(hào)配對(duì)檢查，輸入一個(gè)只有左括號(hào)“(”和右括號(hào)“)”的序列，程序?qū)ㄌ?hào)配對(duì)的正確性進(jìn)行檢查并給出結(jié)果。提示：配對(duì)檢查算法中用到棧結(jié)構(gòu)。例如括號(hào)序列“(()())”、“()()(())”為正確配對(duì)，括號(hào)序列“()())”、“)()(”為不正確配對(duì)等。注意：輸入序列中只能出現(xiàn)左括號(hào)“(”和右括號(hào)“)”，序列的語(yǔ)法正確性由用戶保證。請(qǐng)給出完整的C程序描述。實(shí)訓(xùn)3-1棧的應(yīng)用【實(shí)訓(xùn)目的】

1.掌握?！昂筮M(jìn)先出”的特點(diǎn)。

2.學(xué)會(huì)棧的應(yīng)用?！緦?shí)訓(xùn)內(nèi)容】將非負(fù)十進(jìn)制整數(shù)轉(zhuǎn)換成八進(jìn)制?！緦?shí)訓(xùn)要求】

1.要求設(shè)計(jì)一個(gè)程序，滿足下列要求：對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。

2.用順序棧實(shí)現(xiàn)。【算法分析】十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題，其解決方法有很多，其中一個(gè)簡(jiǎn)單算法基于下列原理：N?=?(NDIVd)?×?d?+?NMODd其中，DIV為整除運(yùn)算，MOD為求余運(yùn)算(取模)，d為進(jìn)制數(shù)。一個(gè)非負(fù)十進(jìn)制整數(shù)轉(zhuǎn)換成八進(jìn)制，即(1348)10?=?(2504)8，其運(yùn)算過(guò)程見(jiàn)表3-1。表3-1非負(fù)十進(jìn)制整數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)的運(yùn)算過(guò)程基于上述原理，計(jì)算過(guò)程是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位，而打印輸出一般來(lái)說(shuō)應(yīng)該從高位到低位進(jìn)行，恰好和計(jì)算過(guò)程相反。因此，如果將計(jì)算過(guò)程中得到的八進(jìn)制數(shù)的各位順序進(jìn)棧，則按照出棧序列打印輸出的就是對(duì)應(yīng)的八進(jìn)制數(shù)?？梢杂梅沁f歸算法實(shí)現(xiàn)本操作，即采用棧結(jié)構(gòu)，將待轉(zhuǎn)換的十進(jìn)制整數(shù)除以基數(shù)8得到的余數(shù)壓入棧中，再將商除以基數(shù)8得到的余數(shù)壓入棧中，如此繼續(xù)下去，直到商為0為止。最后從棧中彈出的數(shù)據(jù)就是本題的結(jié)果。這是利用棧的“后進(jìn)先出”特性的最簡(jiǎn)單的例子?！境绦蚯鍐巍?defineElemtypeint#defineMAXSIZE100#include<stdio.h>typedefstruct{ Elemtypedata[MAXSIZE]; inttop;}SeqStack;voidinitStack(SeqStack*s){/*順序棧初始化*/ s->top=0;}ElemtypegetTop(SeqStack*s){/*返回棧頂元素*/

Elemtypex;

if(s->top==0)

{printf("?？誠(chéng)n");

x=0;

}

else x=(s->data)[s->top];returnx;}intpush(SeqStack*s,Elemtypex){/*元素x入棧*/ if(s->top==MAXSIZE-1)

{

printf("棧滿\n");

return0;}

else{

s->top++; (s->data)[s->top]=x; return1;

}}Elemtypepop(SeqStack*s){/*返回棧頂元素并刪除棧頂元素*/ Elemtypex; if(s->top==0)

{

printf("?？誠(chéng)n");

x=0;} else {

x=(s->data)[s->top]; ?s->top--;

}returnx;}main(){ SeqStackstack,*s; intn; s=&stack; initStack(s); n=0; printf("輸入一非負(fù)整數(shù)(十進(jìn)制)："); scanf("%d",&n); push(s,'#'); while(n!=0) {

push(s,n%8);/*%為求余數(shù)運(yùn)算符,余數(shù)入棧*/ n=n/8;

} /*/為求整數(shù)商運(yùn)算符,商不為零,繼續(xù)運(yùn)行*/ printf("\n\n對(duì)應(yīng)的八進(jìn)制數(shù)為："); while(getTop(s)!='#') printf("%d",pop(s)); printf("\n");

}如果將上面的算法用遞歸算法來(lái)實(shí)現(xiàn)，算法描述如下：#include<stdio.h>voidd_to_or(intx){/*非負(fù)十進(jìn)制整數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)的遞歸算法*/if(x/8!=0)d_to_or(x/8);printf("%d",x%8);}main(){

intx;

printf("輸入一非負(fù)整數(shù)(十進(jìn)制)：");

scanf("%d",&x);

printf("\n\n對(duì)應(yīng)的八進(jìn)制數(shù)為：");