數(shù)據(jù)結(jié)構(gòu) 第三章 棧和隊(duì)列

13.1棧（Stack）第三章棧和隊(duì)列1.定義2.邏輯結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式23.2隊(duì)列（Queue）第三章棧和隊(duì)列1.定義2.邏輯結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式3數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容41.定義3.1棧與線性表相同，仍為一對(duì)一(1:1)關(guān)系。用順序?；蜴湕４鎯?chǔ)均可，但以順序棧更常見(jiàn)3.存儲(chǔ)結(jié)構(gòu)2.邏輯結(jié)構(gòu)限定只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。即棧頂53.1棧只能在棧頂運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則。關(guān)鍵是編寫入棧和出棧函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５拇鎯?chǔ)結(jié)構(gòu)有別而不同。4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式

基本操作有：建棧、判斷棧滿或棧空、入棧、出棧、讀棧頂元素值，等等。6棧是僅在表尾進(jìn)行插入、刪除操作的線性表。表尾(即an端)稱為棧頂

/top;表頭(即a1端)稱為棧底/base例如：棧S=(a1,a2,a3,……….,an-1,an

)插入元素到棧頂?shù)牟僮?，稱為入棧。從棧頂刪除最后一個(gè)元素的操作，稱為出棧。an稱為棧頂元素a1稱為棧底元素想一想：要從棧中取出a1，應(yīng)當(dāng)如何操作？強(qiáng)調(diào)：插入和刪除都只能在表的一端（棧頂）進(jìn)行！1、棧是一種特殊的線性表7Q1：堆棧是什么？它與一般線性表有什么不同？

堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進(jìn)行插入和刪除運(yùn)算。與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同。一般線性表堆棧邏輯結(jié)構(gòu)：1:1邏輯結(jié)構(gòu)：1:1存儲(chǔ)結(jié)構(gòu)：順序表、鏈表存儲(chǔ)結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：隨機(jī)存取運(yùn)算規(guī)則：后進(jìn)先出(LIFO)“進(jìn)”＝插入=壓入=PUSH（an+1)“出”＝刪除=彈出=POP(an)8a1a2……an順序棧Sai……Q2：順序表和順序棧的操作有何區(qū)別？表頭表尾低地址高地址寫入：S[i]=ai讀出：e=S[i]壓入(PUSH):S[top++]=an+1彈出(POP):e=S[--top]低地址高地址S[i]a1a2aian……順序表S……an+1以線性表

S=(a1,a2,….,an-1,an)為例棧底base棧頂top前提：一定要預(yù)設(shè)棧頂指針top棧頂top9棧不存在的條件：base=NULL;棧為空的條件：base=top;棧滿的條件：top-base=stacksize;a1a2……an順序棧Sai……低地址高地址棧底base棧頂topQ2：順序表和順序棧的操作有何區(qū)別？10若入棧動(dòng)作使地址向高端增長(zhǎng)，稱為“向上生成”的棧；若入棧動(dòng)作使地址向低端增長(zhǎng)，稱為“向下生成”的棧；

對(duì)于向上生成的堆棧:入?？谠E：堆棧指針top“先壓后加”:S[top++]=an+1出?？谠E：堆棧指針top“先減后彈”:e=S[--top]Q3：什么叫“向上生成”的棧？“向下生成”又是何意？11Q4：為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？調(diào)用函數(shù)或子程序非它莫屬；遞歸運(yùn)算的有力工具；用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；簡(jiǎn)化了程序設(shè)計(jì)的問(wèn)題。下面用4個(gè)例子來(lái)幫助理解堆棧：12voidtest(int&sum){①intx;②scanf(x);if(x==0)③sum=0;else{④test(sum);⑤sum+=x;}⑥printf(sum);⑦}斷點(diǎn)地址入棧例1

閱讀下列遞歸過(guò)程，說(shuō)明其功能。輸入x1≠0輸入x5＝0輸入x2輸入x3輸入x4輸出sum＝0輸出sum＝0+x4輸出sum＝x4+x3輸出sum＝x4+x3+x2輸出sum＝x4+x3+x2+x1注意：最先輸入的數(shù)據(jù)x1

最后才被累加程序功能：對(duì)鍵盤輸入數(shù)據(jù)求和，直到輸入0結(jié)束2、堆棧舉例13答：可以通過(guò)窮舉所有可能性來(lái)求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入，3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合計(jì)有5種可能性。例2

一個(gè)棧的輸入序列為1,2,3，若在入棧的過(guò)程中允許出棧，則可能得到的出棧序列是什么？14例3：一個(gè)棧的輸入序列是12345，若在入棧的過(guò)程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？答：43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)；12345的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即可。思考：有無(wú)通用的判別原則？2、堆棧舉例15例4：設(shè)依次進(jìn)入一個(gè)棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，b

Ｃ）b，c，d，aＤ）a，c，d，bA）、D）可以，

B）、C）不行。討論：有無(wú)通用的判別原則？有！若輸入序列是…,Pi…Pj…Pk…(i<j<k,輸入序號(hào))，一定不存在這樣的輸出序列

…,Pk…Pi…Pj…答：即對(duì)于輸入序列1，2，3，不存在輸出序列3，1，22、堆棧舉例16棧的抽象數(shù)據(jù)類型定義:(教材P44-45）ADTStack{數(shù)據(jù)對(duì)象：D=……數(shù)據(jù)關(guān)系：R=……基本操作：……}ADTStack入棧、出棧、建棧初始化、判斷棧滿或棧空、讀棧頂元素值等。本節(jié)重點(diǎn)：順序棧和鏈棧的基本操作17

#defineSTACK-INIT-SIZE100

//存儲(chǔ)空間初始分配量

#defineSTACKINCREMENT10

//存儲(chǔ)空間分配增量

typedefstruct{

SElemType*base;

//棧的基址即棧底指針

SElemType*top;

//棧頂指針

intstacksize;

//當(dāng)前分配的空間

}SqStack;SqStacks;動(dòng)態(tài)數(shù)組3、順序棧的存儲(chǔ)表示（教材P46)

18順序棧的入棧操作——例如用堆棧存放（A，B，C，D）AACBABAtop核心語(yǔ)句：top=L;

順序棧入棧函數(shù)PUSH（）見(jiàn)教材Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD19順序棧出棧操作——例如從棧中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心語(yǔ)句：Pop();順序棧出棧函數(shù)POP()見(jiàn)教材Pop();Printf(Pop());20鏈棧的入棧操作和出棧操作（教材省略）(1)鏈棧的構(gòu)造方式——以頭指針為棧頂，在頭指針處插入或刪除.Node*st,*p;intm=sizeof(Node);棧頂棧底棧也可以用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示，用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示的棧就是鏈棧sta1a2an-1annextdata鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：data域和next域，其定義為：typedefStructSNode{SElemTypedata;StructSNode*next;}Node;21Push(SElemTypee){p=(Node*)malloc(m);if(!p){上溢}else{p->data=e;p->link=st;st=p;}}StatusPop(){if(st==NULL){下溢}else{e=st->data;p=st;st=st->link; free(p);return(e);}}鏈棧入棧函數(shù)（包括建棧）鏈棧出棧函數(shù)插入表頭從表頭刪除(2)入、出棧操作由此可以看出：一個(gè)鏈棧由其棧頂指針唯一指定設(shè)st指向棧頂元素，則st=NULL表示?？?2鏈棧不必設(shè)頭結(jié)點(diǎn)，因?yàn)闂ｍ敚ū眍^）操作頻繁；鏈棧一般不會(huì)出現(xiàn)棧滿情況，除非沒(méi)有空間導(dǎo)致malloc分配失敗。鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。采用鏈棧存儲(chǔ)方式的優(yōu)點(diǎn)是，可使多個(gè)棧共享空間；當(dāng)棧中元素個(gè)數(shù)變化較大，且存在多個(gè)棧的情況下，鏈棧是棧的首選存儲(chǔ)方式。幾點(diǎn)說(shuō)明:23例1：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N）——見(jiàn)教材設(shè)計(jì)思路：用棧暫存低位值例2：括號(hào)匹配的檢驗(yàn)————見(jiàn)教材設(shè)計(jì)思路：用棧暫存左括號(hào)例3

：表達(dá)式求值—-————見(jiàn)教材設(shè)計(jì)思路：用棧暫存運(yùn)算符例4：漢諾（Hanoi）塔-———見(jiàn)教材設(shè)計(jì)思路：用棧實(shí)現(xiàn)遞歸調(diào)用4、棧的應(yīng)用舉例24例3

表達(dá)式求值(這是棧應(yīng)用的典型例子)

這里，表達(dá)式求值的算法是

“算符優(yōu)先法”。例如：編寫算法，用棧實(shí)現(xiàn)表達(dá)式3*（7–2）求值。一個(gè)算術(shù)表達(dá)式是由操作數(shù)（x，y，z…）和算符（*，/，+，-，（，），#）組成.表達(dá)式的起止符號(hào)棧的應(yīng)用舉例25例3

表達(dá)式求值(這是棧應(yīng)用的典型例子)

這里，表達(dá)式求值的算法是

“算符優(yōu)先法”。教材表3.1給出了算符之間的優(yōu)先級(jí)專為計(jì)算機(jī)處理而設(shè)計(jì)的表!(1)

表達(dá)式求值必須滿足算術(shù)四則運(yùn)算規(guī)則：

a.從左算到右

b.先乘除，后加減

c.先括號(hào)內(nèi)，后括號(hào)外棧的應(yīng)用舉例為了實(shí)現(xiàn)算符優(yōu)先算法，可以設(shè)定兩個(gè)工作棧，OPND—存放操作數(shù)或運(yùn)算結(jié)果，OPTR—存放運(yùn)算符號(hào)。26(2)算法思想1）首先置操作數(shù)棧OPND為空棧，表達(dá)式的起始符#為運(yùn)算符棧OPTR的棧底元素2）依次讀入表達(dá)式中的每個(gè)字符，若運(yùn)算符是‘#’或棧頂是‘#’，結(jié)束計(jì)算，返回OPND棧頂值。

if（是操作數(shù)）→則PUSH（OPND，操作數(shù)）；

if（是運(yùn)算符）→則與OPTR棧頂元素進(jìn)行比較，按優(yōu)先級(jí)(規(guī)定詳見(jiàn)表3.1）進(jìn)行操作；if棧頂元素<輸入算符，則算符壓入OPTR棧，并接收下一字符

if棧頂元素=運(yùn)算符但≠‘#’，則脫括號(hào)(彈出左括號(hào))并收下一字；if棧頂元素>運(yùn)算符，則退棧、按棧頂計(jì)算，將結(jié)果壓入OPND棧。且該未入棧的運(yùn)算符要保留，繼續(xù)與下一個(gè)棧頂元素比較！棧的應(yīng)用舉例273）直到整個(gè)表達(dá)式求值完畢（當(dāng)前讀入的字符和OPTR棧的棧頂元素均為#

）

(2)算法思想棧的應(yīng)用舉例28問(wèn)：教材表3.1中，1和2哪個(gè)對(duì)應(yīng)棧頂元素，哪個(gè)對(duì)應(yīng)鍵盤輸入值？答：根據(jù)Precede()函數(shù)可知，1對(duì)應(yīng)棧頂元素由表3.1可看出，右括號(hào))

和井號(hào)

#作為2時(shí)級(jí)別最低；由c規(guī)則得出：*，/，+，-為1時(shí)的優(yōu)先權(quán)低于‘（’，高于‘）’由a規(guī)則得出：‘（’=‘）’表明括號(hào)內(nèi)的運(yùn)算已完成；‘#’=‘#’表明表達(dá)式求值完畢。附：棧的應(yīng)用舉例29表達(dá)式求值過(guò)程的描述：OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,－3,72)#Push(opnd,’2’)#,*,(,－3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3*（7–2）30StatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)&&(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(precede(GetTop(OPTR),c)){case‘<’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR);c=getchar();break;

case‘>’:Pop(OPTR,theta);Pop(OPND,b);a=Pop();Push(OPND,Operate(a,theta,b));break;;}//switch}//while

result=GetTop(OPND);}//EvaluateExpressionOperate=abC是操作符嗎？運(yùn)算符與棧頂比較并查3.1表程序清單遞歸算法的設(shè)計(jì)步驟第一步驟（遞歸步驟）：將規(guī)模較大的原問(wèn)題分解為一個(gè)或多個(gè)規(guī)模更小、但具有類似于原問(wèn)題特性的子問(wèn)題。即較大的問(wèn)題遞歸地用較小的子問(wèn)題來(lái)描述，解原問(wèn)題的方法同樣可用來(lái)解這些子問(wèn)題。第二步驟：確定一個(gè)或多個(gè)無(wú)須分解、可直接求解的最小子問(wèn)題（稱為遞歸的終止條件）?！纠糠秦?fù)整數(shù)n的階乘可遞歸定義為：31

32傳說(shuō)在創(chuàng)世紀(jì)時(shí)，在一個(gè)叫Brahma的寺廟里，有三個(gè)柱子，其中一柱上有64個(gè)盤子從小到大依次疊放，僧侶的工作是將這64個(gè)盤子從一根柱子移到另一個(gè)柱子上。xyznn–1移動(dòng)時(shí)的規(guī)則：每次只能移動(dòng)一個(gè)盤子；只能小盤子在大盤子上面；可以使用任一柱子。當(dāng)工作做完之后，就標(biāo)志著世界末日到來(lái)。例4漢諾（Hanoi）塔33分析：設(shè)三根柱子分別為x,y,z,盤子在x柱上，要移到z柱上。1、當(dāng)n=1時(shí)，盤子直接從x柱移到z柱上；2、當(dāng)n>1

時(shí),則:①

設(shè)法將前n–1個(gè)盤子從x移到y(tǒng)柱上（借助z），則盤子n就能從x移到z柱上；②再設(shè)法把n–1個(gè)盤子從y移到z柱上(這又是一個(gè)與原來(lái)相同的問(wèn)題，只是規(guī)模少１了）。xyznn–1例4漢諾（Hanoi）塔34VoidHanoi(intn,charx,chary,charz){//將n個(gè)編號(hào)從上到下為1…n的盤子從x柱，借助y柱移到z柱if(n==1)move(x,1,z);//將編號(hào)為1的盤子從x柱移到z柱

else{//將n-1個(gè)編號(hào)從上到下為1…n-1的盤子從x柱，借助y柱移到z柱

Hanoi(n-1,x,z,y);move(x,n,z);//將編號(hào)為n的盤子從x柱移到z柱

//將n-1個(gè)編號(hào)從上到下為1…n-1的盤子從y柱，借助x柱移到z柱

Hanoi(n-1,y,x,z);}}//Hanoi程序設(shè)計(jì)如下誰(shuí)能畫出Hanoi塔的遞歸函數(shù)運(yùn)行示意圖？棧在遞歸算法的內(nèi)部實(shí)現(xiàn)中所起的作用①調(diào)用函數(shù)時(shí)：系統(tǒng)將會(huì)為調(diào)用者構(gòu)造一個(gè)由返回地址、參數(shù)表（實(shí)參）和中間變量組成的活動(dòng)記錄，并將其壓入到由系統(tǒng)提供的運(yùn)行時(shí)刻棧的棧頂，然后將程序的控制權(quán)轉(zhuǎn)移到被調(diào)函數(shù)。若被調(diào)函數(shù)有局部變量，則在運(yùn)行時(shí)刻棧的棧頂也要為其分配相應(yīng)的空間。因此，活動(dòng)記錄和這些局部變量形成了一個(gè)可供被調(diào)函數(shù)使用的活動(dòng)結(jié)構(gòu)。

35棧在遞歸算法的內(nèi)部實(shí)現(xiàn)中所起的作用注意：

參數(shù)表的內(nèi)容為實(shí)參，返回地址是函數(shù)調(diào)用語(yǔ)句的下一指令的位置。②被調(diào)函數(shù)執(zhí)行完畢時(shí)：系統(tǒng)將運(yùn)行時(shí)刻棧棧頂?shù)幕顒?dòng)結(jié)構(gòu)退棧，并根據(jù)退棧的活動(dòng)結(jié)構(gòu)中所保存的返回地址將程序的控制權(quán)轉(zhuǎn)移給調(diào)用者繼續(xù)執(zhí)行。36遞歸算法的執(zhí)行過(guò)程是不斷地自調(diào)用，直到到達(dá)遞歸出口才結(jié)束自調(diào)用過(guò)程；到達(dá)遞歸出口后，遞歸算法開始按最后調(diào)用的過(guò)程最先返回的次序返回；返回到最外層的調(diào)用語(yǔ)句時(shí)遞歸算法執(zhí)行過(guò)程結(jié)束。37堆棧遞歸調(diào)用總結(jié)383.2隊(duì)列與線性表相同，仍為一對(duì)一關(guān)系。順序隊(duì)或鏈隊(duì)，以循環(huán)順序隊(duì)更常見(jiàn)。存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。尾部插入首部刪除隊(duì)列定義393.2隊(duì)列只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照先進(jìn)先出（FIFO）的原則。關(guān)鍵是掌握入隊(duì)和出隊(duì)操作，具體實(shí)現(xiàn)依順序隊(duì)或鏈隊(duì)的不同而不同。運(yùn)算規(guī)則實(shí)現(xiàn)方式基本操作：入隊(duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。40隊(duì)列（Queue）是僅在表尾進(jìn)行插入操作，在表頭進(jìn)行刪除操作的線性表。它是一種先進(jìn)先出（ＦＩＦＯ）的線性表。例如：隊(duì)列Q=(a1

,a2,a3,……….,an-1,an)在隊(duì)尾插入元素稱為入隊(duì)；在隊(duì)首刪除元素稱為出隊(duì)。隊(duì)首隊(duì)尾1、隊(duì)列是一種特殊線性表41問(wèn)：為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？離散事件的模擬（模擬事件發(fā)生的先后順序,例如CPU芯片中的指令譯碼隊(duì)列）；操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè)CPU執(zhí)行多個(gè)作業(yè)）；3.簡(jiǎn)化程序設(shè)計(jì)。答：3.2.1、隊(duì)列是一種特殊線性表42隊(duì)的實(shí)現(xiàn)方式是本節(jié)重點(diǎn)，關(guān)鍵是掌握入隊(duì)和出隊(duì)操作。

具體實(shí)現(xiàn)依存儲(chǔ)結(jié)構(gòu)（鏈隊(duì)或順序隊(duì)）的不同而不同。隊(duì)的抽象數(shù)據(jù)類型定義：ADTQueue{數(shù)據(jù)對(duì)象：D=……數(shù)據(jù)關(guān)系：R=……基本操作：……}ADTQueue建隊(duì)、入隊(duì)或出隊(duì)、判隊(duì)空或隊(duì)滿等，教材P59-60羅列了9種基本操作。3.2.2、隊(duì)列實(shí)現(xiàn)方式隊(duì)列存儲(chǔ)方式431、鏈隊(duì)列2、順序隊(duì)44鏈隊(duì)列類型定義：

typedefstruct{QueuePtrfront;//隊(duì)首指針

QueuePtr

rear;//隊(duì)尾指針

}LinkQueue;結(jié)點(diǎn)類型定義：

typedefStructQNode{QElemTypedata;//元素StructQNode*next;//指向下一結(jié)點(diǎn)的指針}Qnode,*QueuePtr;關(guān)于整個(gè)鏈隊(duì)的總體描述鏈隊(duì)中任一結(jié)點(diǎn)的結(jié)構(gòu)1.鏈隊(duì)列45討論：空鏈隊(duì)的特征？Q(隊(duì)尾)(隊(duì)首)fronta1a2a3^rearpfront^rear③怎樣實(shí)現(xiàn)鏈隊(duì)的入隊(duì)和出隊(duì)操作？②鏈隊(duì)會(huì)滿嗎？front=rear一般不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足！入隊(duì)（尾部插入）：rear->next=s;rear=s;出隊(duì)（頭部刪除）：front->next=front->next->next;SD^鏈隊(duì)示意圖：完整操作函數(shù)見(jiàn)教材46采用動(dòng)態(tài)分配空間的形式順序隊(duì)類型定義：建隊(duì)核心語(yǔ)句：q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);

//分配空間關(guān)于整個(gè)順序隊(duì)的總體描述#defineQUEUE-MAXSIZE100//最大隊(duì)列長(zhǎng)度

typedefstruct{QElemType*base;//隊(duì)列的基址

intfront;//隊(duì)首指針

intrear;//隊(duì)尾指針

}SqQueue2.順序隊(duì)47Q(隊(duì)尾)(隊(duì)首)fronta1a2a3dataa40.......99rear②隊(duì)列會(huì)滿嗎？極易裝滿！因?yàn)閿?shù)組通常有長(zhǎng)度限制，而其前端空間無(wú)法釋放。①空隊(duì)列的特征？約定：front=rear隊(duì)尾后地址入隊(duì)(尾部插入)：Q[rear]=e;rear++

;

出隊(duì)(頭部刪除)：e=Q[front];front++;

討論：假溢出！有缺陷③怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？核心語(yǔ)句如下：用base做數(shù)組名e順序隊(duì)示意圖：48解決假溢出的途徑———采用循環(huán)隊(duì)列答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。問(wèn)：什么叫“假溢出”？如何解決？2.順序隊(duì)49a3a2a10123N-1rearfront循環(huán)隊(duì)列（臆造）順序隊(duì)列a3a2a1frontrear0123..N-1順序隊(duì)列轉(zhuǎn)化為循環(huán)隊(duì)列50新問(wèn)題：在循環(huán)隊(duì)列中，空隊(duì)特征是front=rear；隊(duì)滿時(shí)也會(huì)有front=rear；判決條件將出現(xiàn)二義性！解決方案有三：①使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；②加設(shè)標(biāo)志位，刪除時(shí)置1,插入時(shí)置0,則可識(shí)別當(dāng)前front=rear屬于何種情況③人為浪費(fèi)一個(gè)單元，則隊(duì)滿特征可改為front=(rear+1)%N；順序隊(duì)列轉(zhuǎn)化為循環(huán)隊(duì)列51隊(duì)空條件:front=rear(初始化時(shí)：front=rear)隊(duì)滿條件：front=(rear+1)%N(N=maxsize)隊(duì)列長(zhǎng)度（即數(shù)據(jù)元素個(gè)數(shù)）：L=（N＋rear－front）%NJ2J3 J1J4

J5frontrear

實(shí)際中常選用方案3（人為浪費(fèi)一個(gè)單元）：即front和rear二者之一指向?qū)嵲兀硪粋€(gè)指向空閑元素。

問(wèn)3：在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？N-1個(gè)6

問(wèn)1：左圖中隊(duì)列maxsizeN=？問(wèn)2：左圖中隊(duì)列長(zhǎng)度L=？5順序隊(duì)列轉(zhuǎn)化為循環(huán)隊(duì)列52（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n要分析4種公式哪種最合理？當(dāng)r≥f時(shí)（A）合理；當(dāng)r<f時(shí)（C）合理；答：綜合2種情況，以（D）的表達(dá)最為合理例2：在一個(gè)循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。那么，從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先移動(dòng)隊(duì)首指針取出元素√，后。例1：數(shù)組Ｑ[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置。假定隊(duì)列中元素的個(gè)數(shù)小于n，計(jì)算隊(duì)列中元素的公式為:示例53例3：一循環(huán)隊(duì)列如下圖所示，若先刪除4個(gè)元素，接著再插入4個(gè)元素，請(qǐng)問(wèn)隊(duì)頭和隊(duì)尾指針?lè)謩e指向哪個(gè)位置?J2J3 J1J4

J5front=1rear=0解：由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為front=1和rear=0。刪除4個(gè)元素后f=5；再插入4個(gè)元素后，r=(0+4)%6=4

front=5J6J5J7J8J9rear=4rear=0front=554討論：循環(huán)隊(duì)列的基本操作如何實(shí)現(xiàn)？以建隊(duì)、入隊(duì)和出隊(duì)三種基本操作為例1）初始化一個(gè)空隊(duì)列算法要求：生成一空隊(duì)列算法操作：為隊(duì)列分配基本容量空間設(shè)置隊(duì)列為空隊(duì)列，其特征即：

front=rear=0（也可為任意單元，如1，2，…甚至-1）循環(huán)隊(duì)列操作551)建隊(duì)的完整算法StatusInitQueue(SqQueue&q)//初始化空循環(huán)隊(duì)列q{q.base=(QElemType*)malloc(sizeof(QElemType）*QUEUE_MAXSIZE);//分配空間if(!q.base)exit(OVERFLOW);//內(nèi)存分配失敗，退出程序q.front=q.rear=0;//置空隊(duì)列returnOK;}//InitQueue;56算法說(shuō)明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素分析：(1)插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿？

if((q.rear+1)%QUEUE_MAXSIZE)==q.front)retur