第3章 數(shù)據(jù)結(jié)構(gòu)（Ｃ＋＋版）棧和隊列

數(shù)據(jù)結(jié)構(gòu)第3章棧和隊列第2講1本章分為（3）講第1講

3.1棧

3.2棧的順序存儲結(jié)構(gòu)及實現(xiàn)

3.3棧的鏈表存儲結(jié)構(gòu)及實現(xiàn)

3.4棧的應(yīng)用3.4.1表達(dá)式計算第3講3.7隊列的鏈表存儲結(jié)構(gòu)及實現(xiàn)3.8隊列的應(yīng)用第2講

3.4.2子程序的嵌套調(diào)用

3.4.3遞歸調(diào)用

3.5隊列

3.6隊列的順序存儲結(jié)構(gòu)及實現(xiàn)供教師參考23.4.2

子程序的嵌套調(diào)用

在各種程序設(shè)計語言中都有子程序（或稱函數(shù)、過程）調(diào)用功能。一個子函數(shù)還可以調(diào)用另一函數(shù)。在系統(tǒng)軟件中會自動使用棧，將返回地址管理起來。下圖所示為由主程序開始的三層嵌套調(diào)用關(guān)系，以及返回地址棧的情況。33.4.3

遞歸調(diào)用一個子程序可以直接或問接地調(diào)用自身。這就是遞歸調(diào)用。在一層層遞歸調(diào)用時，其返回地址和所在每一調(diào)用層的形參變量數(shù)據(jù)都需一一記下進棧。返回時，它們一一出棧并且被采用。現(xiàn)以求階乘的遞歸方法為例分析棧在遞歸中的應(yīng)用。這樣可以加深對遞歸調(diào)用的理解，提高運用遞歸方法進行程序設(shè)計的能力。43.4.3

遞歸調(diào)用

求n!的遞歸方法思路是：

n!=

與之相應(yīng)的Ｃ函數(shù)框架是：

floatfac(intn){floatp;if(n==0||n==1)p=1;elsep=n*fac(n-1);//遞歸調(diào)用

returnp;}5//求階乘的遞歸函數(shù)

floatfac(intn)

{floatp;

if(n==0)p=1;

elsep=n*fac(n-1);

return(p);

}軟件內(nèi)部會自動用到兩個棧，一個遞歸調(diào)用的返回地址棧(略)，一個是調(diào)用時函數(shù)參數(shù)棧如圖(b).

63.5

隊列

隊列(Queue)也是一種特殊的線性表。在現(xiàn)實中例子很多，如客戶到銀行辦理業(yè)務(wù)往往需要排隊，先來的先辦理，晚來的則排在隊尾等待，如圖(a)所示。抽象成邏輯圖如圖(b)所示。73.5.1隊列的定義

隊列(Queue)是特殊的線性表,其所有的插入均限定在表的一端,而所有的刪除則限定在表的另一端。

允許插入的一端稱隊尾(Rear),

允許刪除的一端稱隊頭(Front)。

特點：先進先出(FirstInFirstOut)FIFO

使用隊尾指針rear，隊頭指針front。83.5.2

隊列的抽象數(shù)據(jù)類型ADTQueue{

數(shù)據(jù)對象：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}

約定a1端為隊頭，an

端為隊尾?；静僮鳎撼跏蓟粋€空隊列；判隊空，空隊返回True,否則返回False；入隊，在隊尾插入一個元素；出隊，在隊頭刪除一個元素；取隊頭數(shù)據(jù)元素值；置隊列為空狀態(tài)；銷毀隊列；等等；

}ADTQueue;93.6

隊列的順序存儲結(jié)構(gòu)及實現(xiàn)

常用一維數(shù)組來存儲隊列中的元素。并約定：頭指針front指向隊列頭元素的前一位置；

尾指針rear指向隊尾元素。隊列順序存儲結(jié)構(gòu)：typedef

int

ElemType;struct

SeQueuestr

{ElemType

elem[MAXSIZE];//一維數(shù)組

intfront,rear; //頭、尾指針

};10注意：

(d)因尾指針rear已到最后位置,所以再進隊a7會發(fā)生假“溢出”。

(a)和(c)隊列為空,均有：

rear==front。3.6.1

隊列的順序存儲結(jié)構(gòu)

假設(shè)有個隊列能容納6個元素，如圖:（a）初始空狀態(tài)，

rear

=

front

=

?1；（b）3個元素相繼入隊；（c）a1,a2,a3先后出隊；空狀態(tài)，rear

=

front

=

2；（d）a4,a5,a6依次入隊；假溢出狀態(tài)。??11

采用平移元素的方法,即一旦發(fā)生“假溢出”就把整個隊列的元素平移到存儲區(qū)的首部。如圖,將a4,a5,a6平移到elem[0]至elem[2],而將a7插到第3個位置上,顯然,平移元素的方法效率是很低的。解決“假溢出”方法（1）:12圖(a)

設(shè)想elem[0]接在elem[5]之后,發(fā)生假溢出時,可把a7插入到第0個位置上。

圖(b)元素a8和a9進隊后隊列已滿（真）,若還要插入元素就會發(fā)生上溢（真）。此時有：front=rear=2。

圖(C)隊列為空狀態(tài),有：front=rear=0。

隊列只憑rear==front,無法判別隊空還是隊滿，矛盾？解決“假溢出”方法（2）:13解決矛盾方的法：循環(huán)隊列

①設(shè)置一個布爾變量來區(qū)分隊空和隊滿；②不設(shè)布爾變量，而使有MAXSIZE個空間的數(shù)組僅存儲MAXSIZE-1個數(shù)據(jù)，即空閑一個空間。這樣，可以把尾指針加1后是否等于頭指針作為隊滿的標(biāo)志。實踐證明②更加方便好用，這就是所謂循環(huán)隊列。

循環(huán)隊列判斷隊空條件：rear==front循環(huán)隊列判斷隊滿條件：

(rear+1)%MAXSIZE==front14循環(huán)隊列的進隊：在隊列循環(huán)中,每插入一個新元素時,就把尾指針rear沿順時針方向移動，即:

rear=(rear+1)%MAXSIZE;

elem[rear]=x;

假設(shè)：MAXSIZE是6x是

a7rear=(5+1)%6=0elem[0]=a715循環(huán)隊列的出隊：同樣,每刪除一個新元素時,就把頭指針front沿順時針方向移動一個位置,即:

front=(front+1)%MAXSIZEx=elem[front];假設(shè)：MAXSIZE是6front=(5+1)%6=0出隊elem[0]即a7，最終隊列的頭元素就是a8。163.6.2

循環(huán)隊列類定義

循環(huán)隊列實質(zhì)上是順序存儲結(jié)構(gòu)。類的數(shù)據(jù)成員包括：一個一維數(shù)組，一個頭指針，一個尾指針:

ElemType

elem[MAXSIZE];

int

front,rear;

各種操作的處理可以作為類的函數(shù)成員。討論循環(huán)隊列的各種操作，重點是進隊和出隊操作：

voidAddQ(ElemTypex); //進隊

ElemType

DelQ(); //出隊17classSeQueue{private:

ElemType

elem[MAXSIZE];

int

front,rear;public:

SeQueue(){front=0;rear=0;} //初始化空隊列

~SeQueue(){};

intEmpty();voidDisplay(); //輸出隊列

voidAddQ(ElemTypex); //進隊

ElemType

DelQ(); //出隊

ElemType

GetFront();};1.循環(huán)隊列的類定義：18

int

SeQueue::Empty()//判斷循環(huán)隊列是否為空

{if(rear==front)return1;elsereturn0;}

ElemType

SeQueue::GetFront()//取隊首元素，不出隊

{ElemTypex;

if(front==rear)//判斷隊列是否為空{(diào)cout<<"\nQueuisEmpty!"<<endl;x=-1;}elsex=elem[(front+1)%MAXSIZE];returnx;}循環(huán)隊列類的函數(shù)：19進隊是在隊列尾指針處插入。首先判斷當(dāng)前循環(huán)隊列是否已滿，如果隊列已滿，則輸出提示信息；否則讓尾指針rear加1對MAXSIZE取模后，x進隊。voidSeQueue::AddQ(ElemTypex){if((rear+1)%MAXSIZE==front)//判斷是否滿隊

cout<<"\nQueuisFull!"<<endl;else{rear=(rear+1)%MAXSIZE;//尾指針加1

elem[rear]=x;//x進隊列

}}

2.循環(huán)隊列的進隊-算法3.720首先判斷隊列是否為空，如果隊列為空，不能出隊，輸出提示信息，返回異常數(shù)據(jù)；否則讓頭指針front加1對MAXSIZE取模后，返回elem[front]值。ElemType

SeQueue::DelQ(){if(front==rear)//判斷隊列是否為空{(diào)cout<<"\nQueueisEmpty!"<<endl;return-1; //表明隊空，未曾出隊

}else{front=(front+1)%MAXSIZE;//出隊操作

returnelem[front];}}3.循環(huán)隊列的出隊-算法3.821創(chuàng)建循環(huán)隊列對象Q，調(diào)用進隊、出隊和輸出函數(shù)。int

main(int

argc,char*argv[]){ElemTypee;intj;

SeQueueQ;

cout<<"\n隊列順序存儲結(jié)構(gòu)演示";

cout<<"進隊data=?";cin>>e;

Q.AddQ(e); //進