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

第3章棧和隊列3.1棧3.2隊列本章小結(jié)習題三實訓3-1棧的應用實訓3-2隊列的應用

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

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

(4)?IsFull(S)。操作前提：棧S已經(jīng)存在。操作結(jié)果：判棧滿函數(shù)，若S棧已滿，則函數(shù)值為TRUE或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棧的順序存儲結(jié)構(gòu)順序棧是用順序存儲結(jié)構(gòu)實現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時由于棧的操作的特殊性，還必須附設一個位置指針top(棧頂指針)來動態(tài)地指示棧頂元素在順序棧中的位置。通常以top=-1表示空棧。順序棧的存儲結(jié)構(gòu)可以用C語言中的一維數(shù)組來表示。棧的順序存儲結(jié)構(gòu)定義用C語言描述如下：#defineMAXSIZE50#defineElemtypeint /*棧中元素類型，此處以int為例*/typedefstruct{Elemtypedata[MAXSIZE]; /*用來存放棧中元素的一維數(shù)組*/inttop; /*用來存放棧頂元素的下標*/}SeqStack;SeqStack*S； /*定義指向棧的指針*/

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

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

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

(2)判?？?。intisEmpty(SeqStack*S)

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

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

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

/*元素x入棧*/{

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

{printf(“棧滿\n”);

/*棧上溢，提示出錯*/

return(0);}

else

{

S->top++;

/*棧頂指針加1*/

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

/*給棧頂元素賦值*/

return(1);

}}

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

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

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

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

else

{

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

return(1);

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

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

Elemtypedata;

structsnode*next;

｝LinkStackNode；typedefLinkStackNode*LinkStack;

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

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

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

LinkStackNode*p;

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

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

return(0);

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

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

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

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

(1)遞推就是將復雜問題的求解“推到”對較簡單問題的求解，如將求n!推到求(n-1)!，(n-2)!……使用遞推時應注意到，遞推應有終止之時，如求n!時，以n=0，0!＝1為遞推的終止條件。

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

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

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

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

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

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

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

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

3)設計遞歸算法的方法

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

(2)設計遞歸出口，確定遞歸終止條件(例如求解n!，當n?=?1時，n!=?1)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

/*隊列的最大長度*/typedefstruct{

Elemtypedata[MAXSIZE]；

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

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

q->front=-1;

q->rear=-1;｝

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

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

return(0);

else{

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

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

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

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

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

else

{

(q->rear)++;

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

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

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

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

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

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

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

return1;

else

return0;}

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

if(queueEmpty(q))

{

printf("SeqQueueisempty");

return0;}else{

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

return1;}}

(4)入隊操作。

intenterQueue(SeqQueue*q,Elemtype*x)

/*將新元素x插入隊列*q的隊尾*/

{

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

{

printf("SeqQueueisfull");return0；

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

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

intdeleteQueue(SeqQueue*q,Elemtype*x)

{

if(queueEmpty(q))

{

printf("SeqQueueisempty");

return0;

}else{

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

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

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

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

{

Elemtypedata;

structnode*next;

}Node;typedefstruct{

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

(1)初始化。

intinitQueue(LinkQueue*q)

/*將q初始化為一個空的鏈隊列*/

{

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

if(q->front!=NULL)

{

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

(2)判空隊。

intqueueEmpty(LinkQueue*q){

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

return(1);elsereturn(0);

｝

(3)入隊操作。intenterQueue(LinkQueue*q,Elemtypex) /*將數(shù)據(jù)元素x插入到隊列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)出隊操作。intdeleteQueue(LinkQueue*q,Elemtype*x)

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

Node*s;

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

return(0);

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

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

一、填空題

1.棧是限定僅在表尾進行

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

，表尾端稱為

，棧的操作特性是

。

2.隊列是限定僅在表尾進行

和在表頭端進行

的線性表，隊列的操作特性是

。

3.以下定義了一個順序棧：

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

，棧滿的條件是：

；棧頂元素的表達式是：

，棧底元素的表達式是：

。

二、簡答題

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

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

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

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

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

三、算法設計題

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

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

1.掌握棧“后進先出”的特點。

2.學會棧的應用?！緦嵱杻?nèi)容】將非負十進制整數(shù)轉(zhuǎn)換成八進制?！緦嵱栆蟆?/p>

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

2.用順序棧實現(xiàn)。【算法分析】十進制數(shù)N和其它d進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題，其解決方法有很多，其中一個簡單算法基于下列原理：N?=?(NDIVd)?×?d?+?NMODd其中，DIV為整除運算，MOD為求余運算(取模)，d為進制數(shù)。一個非負十進制整數(shù)轉(zhuǎn)換成八進制，即(1348)10?=?(2504)8，其運算過程見表3-1。表3-1非負十進制整數(shù)轉(zhuǎn)換成八進制數(shù)的運算過程基于上述原理，計算過程是從低位到高位順序產(chǎn)生八進制數(shù)的各個數(shù)位，而打印輸出一般來說應該從高位到低位進行，恰好和計算過程相反。因此，如果將計算過程中得到的八進制數(shù)的各位順序進棧，則按照出棧序列打印輸出的就是對應的八進制數(shù)?？梢杂梅沁f歸算法實現(xiàn)本操作，即采用棧結(jié)構(gòu)，將待轉(zhuǎn)換的十進制整數(shù)除以基數(shù)8得到的余數(shù)壓入棧中，再將商除以基數(shù)8得到的余數(shù)壓入棧中，如此繼續(xù)下去，直到商為0為止。最后從棧中彈出的數(shù)據(jù)就是本題的結(jié)果。這是利用棧的“后進先出”特性的最簡單的例子。【程序清單】#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("?？誠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("棧空\n");

x=0;} else {

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

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

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

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

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

intx;

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

scanf("%d",&x);

printf("\n\n對應的八進制數(shù)為：");