數(shù)據(jù)結(jié)構(gòu)_堆棧和隊列的基本應(yīng)用與原理

1、CH3 棧和隊列棧和隊列n教學(xué)內(nèi)容：教學(xué)內(nèi)容：n本章介紹應(yīng)用廣泛的數(shù)據(jù)結(jié)構(gòu)本章介紹應(yīng)用廣泛的數(shù)據(jù)結(jié)構(gòu) 棧棧(stack)和隊和隊列列(queue)，將分別給出這兩種結(jié)構(gòu)的定義、基本將分別給出這兩種結(jié)構(gòu)的定義、基本運算、存儲結(jié)構(gòu)以及一些基本運算的具體實現(xiàn)，運算、存儲結(jié)構(gòu)以及一些基本運算的具體實現(xiàn)，并給出一些應(yīng)用實例。并給出一些應(yīng)用實例。n教學(xué)重點與難點教學(xué)重點與難點n重點是掌握棧和隊列在兩種存儲結(jié)構(gòu)上實現(xiàn)的基重點是掌握棧和隊列在兩種存儲結(jié)構(gòu)上實現(xiàn)的基本運算本運算n難點是應(yīng)用棧解決一些實際問題，以及循環(huán)隊列難點是應(yīng)用棧解決一些實際問題，以及循環(huán)隊列中對邊界條件的處理。中對邊界條件的處理。n教學(xué)目標(biāo)

2、教學(xué)目標(biāo)n掌握棧和隊列這兩種數(shù)據(jù)結(jié)構(gòu)的特點，了解在什么問題中掌握棧和隊列這兩種數(shù)據(jù)結(jié)構(gòu)的特點，了解在什么問題中應(yīng)該使用哪種結(jié)構(gòu)。應(yīng)該使用哪種結(jié)構(gòu)。n熟悉幾個關(guān)系：熟悉幾個關(guān)系：n棧（隊列）和線性表的關(guān)系；棧（隊列）和線性表的關(guān)系；n順序棧（順序隊列）和順序表的關(guān)系；順序棧（順序隊列）和順序表的關(guān)系；n鏈棧（鏈隊列）和鏈表的關(guān)系。鏈棧（鏈隊列）和鏈表的關(guān)系。n重點掌握在順序棧和鏈棧上實現(xiàn)的棧的七種基本運算，特重點掌握在順序棧和鏈棧上實現(xiàn)的棧的七種基本運算，特別注意棧滿和棧空的條件及它們的描述。別注意棧滿和?？盏臈l件及它們的描述。n重點掌握在循環(huán)隊列和鏈隊列上實現(xiàn)的七種基本運算，特重點掌握在循環(huán)隊

3、列和鏈隊列上實現(xiàn)的七種基本運算，特別注意隊滿和隊空的描述方法。別注意隊滿和隊空的描述方法。n熟悉棧和隊列的下溢和上溢的概念；順序隊列中產(chǎn)生假上熟悉棧和隊列的下溢和上溢的概念；順序隊列中產(chǎn)生假上溢的原因；循環(huán)隊列消除假上溢的方法。溢的原因；循環(huán)隊列消除假上溢的方法。 3.1 棧棧n棧的定義棧的定義n棧棧(Stack)是僅限制在表的一端進(jìn)是僅限制在表的一端進(jìn)行插入和刪除運算的線性表。通行插入和刪除運算的線性表。通常稱允許插入、刪除這一端為常稱允許插入、刪除這一端為棧棧頂頂（top），），另一端稱為另一端稱為棧底棧底(bottom)。n棧的修改是按后進(jìn)先出的原則進(jìn)棧的修改是按后進(jìn)先出的原則進(jìn)行的，故

4、又稱棧為行的，故又稱棧為LIFO表表(Last In First Out)。n棧的特征棧的特征n棧的邏輯結(jié)構(gòu)和我們先前學(xué)過的棧的邏輯結(jié)構(gòu)和我們先前學(xué)過的線性表相同。線性表相同。n棧的運算規(guī)則與線性表相比有更棧的運算規(guī)則與線性表相比有更多的限制。多的限制。ana2a1棧底棧底棧頂棧頂入棧入棧出棧出棧3.1.1 棧的抽象數(shù)據(jù)類型定義棧的抽象數(shù)據(jù)類型定義ADT Stack數(shù)據(jù)對象：數(shù)據(jù)對象：D=ai|aiElemSet;1in,n0; 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R=| ai,ai+1D,i=1,2,n-1 基本操作：基本操作： InitStack(&S) DestroyStack(&S)

5、StackEmpty(S) StackLength(S) GetTop(G,&e) Push(&S,e) Pop(&S,&e) StackTraverse(S,visit()/ ADT Stack3.1.2 棧的順序存儲表示和實現(xiàn)棧的順序存儲表示和實現(xiàn)n1.棧的順序存儲表示棧的順序存儲表示#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct ElemType *base; ElemType *top; int stacksize;SqStack;basetopana2a1n.基本操作

6、的算法表示基本操作的算法表示n初始化一個空棧初始化一個空棧n判棧空判?？課取棧頂元素取棧頂元素n入棧入棧n出棧出棧1)初始化一個空棧初始化一個空棧Status InitStack(SqStack &S) S.base=(ElemType*) malloc(STACK_INIT_SIZE*sizeof(ElemType); if (!S.base) exit OVERFLOW; S.top=S.base; S.StackSize=STACK_INIT_SIZE; return OK;s.bases.top2)取棧頂元素和元素出棧取棧頂元素和元素出棧Status GetTop(SqStac

7、k S,ElemType &e) if (S.base=S.top) return ERROR; e=*(S.top-1); return OK;Status Pop(SqStack &S,ElemType &e) if (S.base=S.top) return ERROR; e=*- -S.top; /- -S.top;e=*S.top; return OK;s.bases.topana2a13)元素入棧元素入棧Status Push(SqStack &S,ElemType e) if (S.top- S.base=S.stacksize) newbase=

8、(ElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(ElemType); if (!newbase) exit (OVERFLOW); S.base=newbase; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; /*S.top=e;S.top+; return OK;s.bases.topana2a1思考題：思考題：n一個棧的入棧序列為：一個棧的入棧序列為：1 2 3，那么可能得到的出棧，那么可能得到的出棧序列是什么？序列是什么？n答

9、：答：3 2 1，2 3 1，2 1 3 ，1 3 2 ，1 2 3。n2.設(shè)將整數(shù)設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，但只要出棧時棧依次進(jìn)棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回非空，則可將出棧操作按任何次序夾入其中，請回答下述問題：答下述問題： n(1)若入、出棧次序為若入、出棧次序為Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數(shù)字序列為何？則出棧的數(shù)字序列為何？ n(2) 能否得到出棧序列能否得到出棧序列1423和和1432?并說明為什么不能得到并說明為什么不能得到或者如何得到?；蛘?/p>

10、如何得到。 n(3)請分析請分析 1，2 ，3 ，4 的的24種排列中，哪些序列是可以通種排列中，哪些序列是可以通過相應(yīng)的入出棧操作得到的。過相應(yīng)的入出棧操作得到的。 3.1.3 棧的共享存儲單元棧的共享存儲單元n引言引言n思考：兩個棧如何共享存儲空間？思考：兩個棧如何共享存儲空間？“底設(shè)兩端、相向而動、迎面增長底設(shè)兩端、相向而動、迎面增長”3.1.4 鏈棧的表示和實現(xiàn)鏈棧的表示和實現(xiàn)n1.棧的鏈?zhǔn)酱鎯Ρ硎緱５逆準(zhǔn)酱鎯Ρ硎総ypedef struct SNode ElemType data; struct SNode *next;SNode,*LinkStack;n問：問： 鏈棧中為何不設(shè)置頭

11、結(jié)點鏈棧中為何不設(shè)置頭結(jié)點?n答：鏈棧不需要在頭部附加頭結(jié)點，因答：鏈棧不需要在頭部附加頭結(jié)點，因為棧都是在頭部進(jìn)行操作的，如果加了為棧都是在頭部進(jìn)行操作的，如果加了頭結(jié)點，等于要對頭結(jié)點之后的結(jié)點進(jìn)頭結(jié)點，等于要對頭結(jié)點之后的結(jié)點進(jìn)行操作，反而使算法更復(fù)雜，所以只要行操作，反而使算法更復(fù)雜，所以只要有鏈表的首指針就可以了。有鏈表的首指針就可以了。 anan-1ai+1aia1棧頂棧頂棧底棧底n3.鏈?；静僮鞯膶崿F(xiàn)鏈?；静僮鞯膶崿F(xiàn)n初始化初始化S=NULL；n入棧入棧申請結(jié)點申請結(jié)點p； p-data=e;p-next=S;S=p;n判空：判空：n S=NULLn出棧：出棧：if (S=N

12、ULL) return ERROR;else p=S; S=p-next; e=p-data; free(p); anan-1ai+1aia1棧頂棧頂棧底棧底練習(xí)練習(xí)n(1) 棧是限定在棧是限定在_處進(jìn)行插入或刪除處進(jìn)行插入或刪除操作的線性表。操作的線性表。 nA. 端點端點 B. 棧底棧底 C. 棧頂棧頂 D. 中間中間n(2) 4個元素按個元素按A、B、C、D順序連續(xù)進(jìn)順序連續(xù)進(jìn)S棧，棧， 進(jìn)行進(jìn)行Pop(S,x)運算后，運算后，x的值是的值是_。nA.A B. B C. C D. Dn(3) 棧的特點是棧的特點是_。nA. 先進(jìn)先出先進(jìn)先出 B. 后進(jìn)先出后進(jìn)先出 nC. 后進(jìn)后出后進(jìn)后

13、出 D. 不進(jìn)不出不進(jìn)不出n(4) 棧與一般線性表的區(qū)別主要在棧與一般線性表的區(qū)別主要在_方面。方面。nA. 元素個數(shù)元素個數(shù) B. 元素類型元素類型nC. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) D. 插入、刪除元素的位置插入、刪除元素的位置n(5) 一個棧的輸入序列為一個棧的輸入序列為1，2，3，4，5，則下，則下列序列中不可能是棧的輸出序列的是列序列中不可能是棧的輸出序列的是_。nA. 2，3，4，1，5，nB. 5，4，1，3，2，nC. 2，3，1，4，5， nD. 1，5，4，3，23. 2 棧的應(yīng)用舉例棧的應(yīng)用舉例n3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 void conversion() InitStack(

14、S); scanf( %d ,&N); while (N) Push(S,N%8); N=N/8; /while while(!StackEmpty(S) Pop (S,e); printf( %d ,e); 將除將除8的余數(shù)依次入棧的余數(shù)依次入棧S，先得的先得的余數(shù)為低位，后得的余數(shù)為高位余數(shù)為低位，后得的余數(shù)為高位。從棧頂?shù)綏５自匾来纬鰲?，從棧頂?shù)綏５自匾来纬鰲?，得到對?yīng)的得到對應(yīng)的8進(jìn)制數(shù)進(jìn)制數(shù)3. 2 棧的應(yīng)用舉例棧的應(yīng)用舉例n3.2.2 括號匹配的檢查括號匹配的檢查n例如：n（）n（ ）n（ ）n（ ）n（）n算法的設(shè)計思想：算法的設(shè)計思想：n1）凡出現(xiàn)左括弧，則進(jìn)棧；）

15、凡出現(xiàn)左括弧，則進(jìn)棧；n2）凡出現(xiàn)右括弧，首先檢查棧是否空）凡出現(xiàn)右括弧，首先檢查棧是否空n若?？眨瑒t表明該若?？?，則表明該“右括弧右括弧”多余多余n否則和棧頂元素比較，否則和棧頂元素比較，n若相匹配，則若相匹配，則“左括弧出棧左括弧出?！眓否則表明不匹配否則表明不匹配n3）表達(dá)式檢驗結(jié)束時，）表達(dá)式檢驗結(jié)束時，n若棧空，則表明表達(dá)式中匹配正確若棧空，則表明表達(dá)式中匹配正確n否則表明否則表明“左括弧左括弧”有余有余Status Compare( ) InitStack(S); flag=TURE; while （ch= getchar( )）！）！=#） & flag ） switch

16、 (ch) case ( :case :caxe :Push(S,ch);break;case ) :if ( Pop(S,e)=ERROR | e!=( ) flag=FALSE;break;case :if ( Pop(S,e)=ERROR | e!=) flag=FALSE;break; case :if ( Pop(S,e)=ERROR | e!=) flag=FALSE;break; /switch if (flag & ch=# & StackEmpty(S) return TRUE; else return FALSE; 3.2.3 迷宮求解迷宮求解出出口口入入口

17、口n求迷宮路徑算法的基本思想是：求迷宮路徑算法的基本思想是：n若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入路徑，繼續(xù)前進(jìn)，則納入路徑，繼續(xù)前進(jìn);n若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則后退，換方向繼續(xù)探，則后退，換方向繼續(xù)探索索;n若四周若四周“均無通路均無通路”，則將當(dāng)前位置從路徑中刪，則將當(dāng)前位置從路徑中刪除出去。除出去。n求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法：設(shè)定當(dāng)前位置的初值為入口位置；設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通，若當(dāng)前位置可通， 則將當(dāng)前位置插入棧頂；則將當(dāng)前位置插入棧頂； 若該位置是出口位置，則算法結(jié)束；若該位置是出口位

18、置，則算法結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置； 否則否則 while (棧不空）；棧不空）；3.2.4 表達(dá)式求值表達(dá)式求值n運算規(guī)則運算規(guī)則n實現(xiàn)思想實現(xiàn)思想n設(shè)置兩個工作棧設(shè)置兩個工作棧n運算符棧運算符棧n操作數(shù)棧操作數(shù)棧n算法描述算法描述 2 1（）#（error ）error運算規(guī)則運算規(guī)則 OperandType Evaluateexpress()InitStack(OPTR); Push(OPTR,#);InitStack(OPND); c=getchar( );while (c!=# | GetTop(OPTR)!=#) i

19、f （c為操作數(shù)）為操作數(shù)） Push(OPND,c);c=getchar(); else switch Precede(GetTop(OPTR),c) case :Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b);break; /switch/while/ Evaluateexpressn有關(guān)思考與提示有關(guān)思考與提示n算符優(yōu)先表的存儲和表示算符優(yōu)先表的存儲和表示;n棧的選擇（靜態(tài)順序棧棧的選擇（靜態(tài)順序棧-用數(shù)組表示）用數(shù)組表示）n判斷判斷c是否為算符。是否為算符。nOperate(a,theta,b)

20、 的實現(xiàn)的實現(xiàn)Int change(char c)Switch c ofcase +:i=0;break;case -:i=1;break;case *:i=2;break;case /:i=3;break;case (:i=4;break;case ):i=5;break;case #:i=6;break;Return i;nChar Precede(char c1,char c2)Char a77=, , , ,0long fact(long n) if (n=0) return 1; else return n*fact(n-1);n例如：例如：fact(4)fact(3)fact(2)

21、fact(1)fact(0)112624函數(shù)函數(shù)調(diào)用與返回調(diào)用與返回 返回值返回值n2.遞歸的數(shù)據(jù)結(jié)構(gòu)遞歸的數(shù)據(jù)結(jié)構(gòu)n例例1：線性鏈表結(jié)構(gòu)：線性鏈表結(jié)構(gòu)打印非空鏈表打印非空鏈表f的最后一個結(jié)點的數(shù)據(jù)值的最后一個結(jié)點的數(shù)據(jù)值void find (Linklist f) if (f-next=NULL) printf(f-data); else find(f-next);n例例2：樹型結(jié)構(gòu)：樹型結(jié)構(gòu)n-1n-1個個3.問題的解法是遞歸的問題的解法是遞歸的例：例：Hanoi塔問題塔問題分析：分析：n n個個 X Y Z 1. 將將X軸上的軸上的n1個盤子借助個盤子借助Z軸移到軸移到Y(jié)軸上；軸上；2.

22、將將X軸上的余下的軸上的余下的1個盤子移到個盤子移到Z軸上；軸上；3. 將將Y軸上的軸上的n1個盤子借助個盤子借助X軸移到軸移到Z軸上軸上 X求解算法及調(diào)用示意圖求解算法及調(diào)用示意圖void hanoi(int n,char x,char y,char z) if (n=1) move (x,1,z); else hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z); Hanoi(3,a,b,c)Hanoi(1,a,b,c)Hanoi(1,b,c,a)Hanoi(1,c,a,b)Hanoi(1,a,b,c)Hanoi(2,a,c,b)Hanoi(2,b

23、,a,c)move(a,c)move(a,c)move(b,c)move(b,a)move(c,b)move(a,b)move(a,c)n=3的調(diào)用示意圖的調(diào)用示意圖1.遞歸過程遞歸過程調(diào)用過程調(diào)用過程回推過程回推過程2.遞歸工作棧遞歸工作棧 目的目的：保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)設(shè)立工作棧：保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)設(shè)立工作棧作為遞歸函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū)。作為遞歸函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū)。 內(nèi)容內(nèi)容： 函數(shù)返回地址函數(shù)返回地址 本次調(diào)用時與形參結(jié)合的實參本次調(diào)用時與形參結(jié)合的實參 本層的局部變量值本層的局部變量值3.3.2 遞歸過程與遞歸工作棧遞歸過程與遞歸工作棧n遞歸算法的優(yōu)點和

24、缺點遞歸算法的優(yōu)點和缺點n利用遞歸算法（函數(shù)、過程、子程序等）編寫利用遞歸算法（函數(shù)、過程、子程序等）編寫的程序具有的程序具有結(jié)構(gòu)簡潔清晰、易讀易理解結(jié)構(gòu)簡潔清晰、易讀易理解等優(yōu)點。等優(yōu)點。n然而由于使用棧來實現(xiàn)這種然而由于使用棧來實現(xiàn)這種“調(diào)用調(diào)用返回返回”的的遞歸過程，無論在遞歸過程，無論在時間時間上還是在上還是在空間空間上都比相上都比相應(yīng)的非遞歸程序的開銷要大。應(yīng)的非遞歸程序的開銷要大。3.4 隊列隊列n隊列的定義隊列的定義n隊列隊列(Queue)是僅限制在表的一端進(jìn)行插入，另是僅限制在表的一端進(jìn)行插入，另一端進(jìn)行刪除運算的線性表。通常稱允許插入一端進(jìn)行刪除運算的線性表。通常稱允許插入一

25、端為一端為隊尾隊尾（rear），），另一端稱為另一端稱為隊頭隊頭(front)。n隊列的修改是按先進(jìn)先出的原則進(jìn)行的，故又隊列的修改是按先進(jìn)先出的原則進(jìn)行的，故又稱棧為稱棧為FIFO表表(Fast In First Out)。隊頭隊頭隊尾隊尾入隊列入隊列出隊列出隊列anan-1a3a2a1n例如：例如：n到醫(yī)院看病，首先需要到掛號處掛號，然后，按到醫(yī)院看病，首先需要到掛號處掛號，然后，按號碼順序救診。號碼順序救診。n乘坐公共汽車，應(yīng)該在車站排隊，車來后，按順乘坐公共汽車，應(yīng)該在車站排隊，車來后，按順序上車。序上車。n在在Windows這類多任務(wù)的操作系統(tǒng)環(huán)境中，每個這類多任務(wù)的操作系統(tǒng)環(huán)境中，

26、每個應(yīng)用程序響應(yīng)一系列的應(yīng)用程序響應(yīng)一系列的“消息消息”，像用戶點擊鼠，像用戶點擊鼠標(biāo)；拖動窗口這些操作都會導(dǎo)致向應(yīng)用程序發(fā)送標(biāo)；拖動窗口這些操作都會導(dǎo)致向應(yīng)用程序發(fā)送消息。為此，系統(tǒng)將為每個應(yīng)用程序創(chuàng)建一個隊消息。為此，系統(tǒng)將為每個應(yīng)用程序創(chuàng)建一個隊列，用來存放發(fā)送給該應(yīng)用程序的所有消息，應(yīng)列，用來存放發(fā)送給該應(yīng)用程序的所有消息，應(yīng)用程序的處理過程就是不斷地從隊列中讀取消息，用程序的處理過程就是不斷地從隊列中讀取消息，并依次給予響應(yīng)。并依次給予響應(yīng)。3.4.1 隊列的抽象數(shù)據(jù)類型定義隊列的抽象數(shù)據(jù)類型定義ADT Queue數(shù)據(jù)對象：數(shù)據(jù)對象：D=ai|aiElemSet;1in,n0;數(shù)據(jù)關(guān)

27、系：數(shù)據(jù)關(guān)系：R=| ai,ai+1D,i=1,2,n-1， 約定約定a1端為隊列頭，端為隊列頭，an端為隊列尾端為隊列尾基本操作：基本操作： InitQueue(&Q) DestroyQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q,&e) EnQueue(&Q,e) DelQueue(&Q,&e)ADT Queue 3.4.2 鏈隊列的表示和實現(xiàn)鏈隊列的表示和實現(xiàn)n單鏈隊列的定義單鏈隊列的定義typedef struct QnodeElemType data; struct Qnode *nex

28、t;Qnode,*QueuePtr;typedef struct QueuePtr front； QueuePtr rear;LinkQueuen帶頭結(jié)點的鏈隊列示意圖：帶頭結(jié)點的鏈隊列示意圖： a1a2anQ.front Q.rear 1. 隊列的初始化隊列的初始化Status InitQueue(LinkQueue &Q) Q.front=Q.rear= (QueuePtr)malloc(sizeof(Qnode); if (!Q.front) exit OVERFLOW; Q.front-next=NULL; return OK;Q.frontQ.rear2. 隊列的銷毀隊列的銷

29、毀Status DestroyQueue(LinkQueue &Q) while (Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return OK;a1a2anQ.frontQ.rear3. 入隊列入隊列Status EnQueue(LinkQueue &Q, ElemType e) p=(QueuePtr)malloc (sizeof(Qnode); if (!p) exit OVERFLOW; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; retu

30、rn OK;n說明：說明：n所謂入隊列即在隊尾之后插入一個新結(jié)點，并讓新所謂入隊列即在隊尾之后插入一個新結(jié)點，并讓新結(jié)點成為新的隊列尾結(jié)點成為新的隊列尾.a1a2anQ.frontQ.rearpe Q.rear4. 出隊列出隊列Status DeQueue(LinkQueue &Q, ElemType &e) if (Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if (Q.rear=p) Q.rear=Q.front; free(p); return OK; 注意注意：

31、p指向被刪除結(jié)點，需要考慮指向被刪除結(jié)點，需要考慮p是否為隊尾結(jié)點指針。是否為隊尾結(jié)點指針。 a1a2anQ.frontQ.rearp 5. 取隊首取隊首Status GetHead(LinkQueue Q, ElemType &e) if (Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; return OK; a1a2anQ.frontQ.rear 3.4.3 隊列順序存儲的表示和實現(xiàn)隊列順序存儲的表示和實現(xiàn)（1）空隊列）空隊列J1J2J3J4（2）J1、J2、J3、J4依次入隊列依次入隊列J4（3）J1、J2、J3依依

32、次出隊列次出隊列J4J5J6（4）J5、J6依次依次入隊列入隊列順序隊列的特點順序隊列的特點1. 設(shè)立兩棵指針設(shè)立兩棵指針Q.front和和 Q.rear2. 隊空的判定條件隊空的判定條件:Q.front= Q.rear3. 隊滿的判定條件隊滿的判定條件:Q.rearQ.Maxsize隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)n存儲結(jié)構(gòu)定義存儲結(jié)構(gòu)定義#define MAXQSIZE 100typedef struct ElemType *base; int front; int rear;SqQueue;n順序隊列的順序隊列的“溢出溢出”問題問題n(1)真溢出真溢出nQ.rear Q.front

33、Q.Maxsizen(2)假溢出假溢出n順序隊列因多次入隊和出隊操作后出現(xiàn)的有存儲空間順序隊列因多次入隊和出隊操作后出現(xiàn)的有存儲空間但不能進(jìn)行入隊操作的溢出。但不能進(jìn)行入隊操作的溢出。n問題：問題：n如何解決順序隊列的如何解決順序隊列的“假溢出假溢出”問題？問題？n答：答：n按最大可能的進(jìn)隊操作次數(shù)設(shè)置順序隊列的最大按最大可能的進(jìn)隊操作次數(shù)設(shè)置順序隊列的最大元素個數(shù)；元素個數(shù)；n修改出隊算法，使每次出隊列后都把隊列中剩余修改出隊算法，使每次出隊列后都把隊列中剩余數(shù)據(jù)元素向隊頭方向移動一個位置；數(shù)據(jù)元素向隊頭方向移動一個位置；n修改入隊算法，增加判斷條件，當(dāng)假溢出時，把修改入隊算法，增加判斷條件

34、，當(dāng)假溢出時，把隊列中的數(shù)據(jù)元素向隊頭移動，然后方完成入隊隊列中的數(shù)據(jù)元素向隊頭移動，然后方完成入隊操作。操作。n采用循環(huán)隊列；采用循環(huán)隊列；循環(huán)隊列循環(huán)隊列n1.基本思想基本思想n2.示意圖示意圖順序隊列順序隊列J1J2J3Q.frontQ.rear6 5 4 3 210 J3J2J10123Q.rearQ.front 循環(huán)隊列循環(huán)隊列循環(huán)隊列循環(huán)隊列n一個新一個新問題問題：n在循環(huán)隊列中，隊空特征是在循環(huán)隊列中，隊空特征是Q.frontQ.rear；隊隊滿時也會有滿時也會有Q.frontQ.rear ；判決條件將出現(xiàn)二判決條件將出現(xiàn)二義性！義性！n解決方案有三：解決方案有三：n使用一個計數(shù)

35、器記錄隊列中元素個數(shù)（即隊列使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；長度）；n判隊滿：判隊滿：countMAXQSIZEn判隊空：判隊空：count=0n加設(shè)標(biāo)志位加設(shè)標(biāo)志位n判隊滿：判隊滿：tag=1 & Q.rear=Q.frontn判隊空：判隊空：tag=0 & Q.rear=Q.frontn 少用一個存儲單元少用一個存儲單元n判隊滿：判隊滿： Q.front=(Q.rear+1)%MAXQSIZEn判隊空：判隊空： Q.rear=Q.front循環(huán)隊列循環(huán)隊列n4.基本操作的算法分析與實現(xiàn)基本操作的算法分析與實現(xiàn)n初始化初始化n求隊列的長度求隊列的長度n入隊列入

36、隊列n出隊列出隊列循環(huán)隊列循環(huán)隊列n1.隊列的初始化隊列的初始化Status InitQueue(SqQueue &Q) Q.base(ElemType*) malloc(MAXQSIZE*sizeof(ElemType); if (!Q.base) exit OVERFLOW; Q.frontQ.rear0; return OK;（1）空隊列）空隊列循環(huán)隊列循環(huán)隊列n2.求隊列的長度求隊列的長度int QueueLength(SqQueue Q)return (Q.rearQ.front+MAXQSIZE) % MAXQSIZE;循環(huán)隊列循環(huán)隊列n2.入隊列入隊列Status EnQ

37、ueue(SqQueue &Q, ElemType e) if (Q.rear+1)% MAXQSIZE=Q.front) return ERROR; Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK;n3.出隊列出隊列Status DeQueue(SqQueue &Q,ElemType &e) if (Q.rear=Q.front) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK;3.5 隊列應(yīng)用隊列應(yīng)用n1.判斷一個字符序列是否是回文。判斷一個字符序列是否是回文。n基本思想：基本思想：n將輸入字符逐個分別存入隊列和棧，然后逐個將輸入字符逐個分別存入隊列和棧，然后逐個出隊列和退棧并比較出隊列的字符和退棧的字出隊列和退棧并比較出隊列的字符和退棧的字符是否相等，若全部相