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

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

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

3、列和鏈隊(duì)列上實(shí)現(xiàn)的七種基本運(yùn)算，特別注意隊(duì)滿和隊(duì)空的描述方法。別注意隊(duì)滿和隊(duì)空的描述方法。n熟悉棧和隊(duì)列的下溢和上溢的概念；順序隊(duì)列中產(chǎn)生假上熟悉棧和隊(duì)列的下溢和上溢的概念；順序隊(duì)列中產(chǎn)生假上溢的原因；循環(huán)隊(duì)列消除假上溢的方法。溢的原因；循環(huán)隊(duì)列消除假上溢的方法。 3.1 棧棧n棧的定義棧的定義n棧棧(Stack)是僅限制在表的一端進(jìn)是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。通行插入和刪除運(yù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棧的運(yùn)算規(guī)則與線性表相比有更棧的運(yùn)算規(guī)則與線性表相比有更多的限制。多的限制。ana2a1棧底棧底棧頂棧頂入棧入棧出棧出棧3.1.1 棧的抽象數(shù)據(jù)類型定義棧的抽象數(shù)據(jù)類型定義ADT Stack數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：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 棧的順序存儲(chǔ)表示和實(shí)現(xiàn)棧的順序存儲(chǔ)表示和實(shí)現(xiàn)n1.棧的順序存儲(chǔ)表示棧的順序存儲(chǔ)表示#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct ElemType *base; ElemType *top; int stacksize;SqStack;basetopana2a1n.基本操作

6、的算法表示基本操作的算法表示n初始化一個(gè)空棧初始化一個(gè)空棧n判?？张袟？課取棧頂元素取棧頂元素n入棧入棧n出棧出棧1)初始化一個(gè)空棧初始化一個(gè)空棧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一個(gè)棧的入棧序列為：一個(gè)棧的入棧序列為：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)棧，但只要出棧時(shí)棧依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下述問題：答下述問題： n(1)若入、出棧次序?yàn)槿羧搿⒊鰲４涡驗(yàn)镻ush(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數(shù)字序列為何？則出棧的數(shù)字序列為何？ n(2) 能否得到出棧序列能否得到出棧序列1423和和1432?并說明為什么不能得到并說明為什么不能得到或者如何得到?；蛘?/p>

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

11、結(jié)點(diǎn)鏈棧中為何不設(shè)置頭結(jié)點(diǎn)?n答：鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因答：鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了為棧都是在頭部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要對(duì)頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)頭結(jié)點(diǎn)，等于要對(duì)頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行操作，反而使算法更復(fù)雜，所以只要行操作，反而使算法更復(fù)雜，所以只要有鏈表的首指針就可以了。有鏈表的首指針就可以了。 anan-1ai+1aia1棧頂棧頂棧底棧底n3.鏈?；静僮鞯膶?shí)現(xiàn)鏈棧基本操作的實(shí)現(xiàn)n初始化初始化S=NULL；n入棧入棧申請(qǐng)結(jié)點(diǎn)申請(qǐng)結(jié)點(diǎn)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. 端點(diǎn)端點(diǎn) B. 棧底棧底 C. 棧頂棧頂 D. 中間中間n(2) 4個(gè)元素按個(gè)元素按A、B、C、D順序連續(xù)進(jìn)順序連續(xù)進(jìn)S棧，棧， 進(jìn)行進(jìn)行Pop(S,x)運(yùn)算后，運(yùn)算后，x的值是的值是_。nA.A B. B C. C D. Dn(3) 棧的特點(diǎn)是棧的特點(diǎn)是_。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. 元素個(gè)數(shù)元素個(gè)數(shù) B. 元素類型元素類型nC. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) D. 插入、刪除元素的位置插入、刪除元素的位置n(5) 一個(gè)棧的輸入序列為一個(gè)棧的輸入序列為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ù)綏５自匾来纬鰲?，得到?duì)應(yīng)的得到對(duì)應(yīng)的8進(jìn)制數(shù)進(jìn)制數(shù)3. 2 棧的應(yīng)用舉例棧的應(yīng)用舉例n3.2.2 括號(hào)匹配的檢查括號(hào)匹配的檢查n例如：n（）n（ ）n（ ）n（ ）n（）n算法的設(shè)計(jì)思想：算法的設(shè)計(jì)思想：n1）凡出現(xiàn)左括弧，則進(jìn)棧；）

15、凡出現(xiàn)左括弧，則進(jìn)棧；n2）凡出現(xiàn)右括弧，首先檢查棧是否空）凡出現(xiàn)右括弧，首先檢查棧是否空n若棧空，則表明該若?？眨瑒t表明該“右括弧右括弧”多余多余n否則和棧頂元素比較，否則和棧頂元素比較，n若相匹配，則若相匹配，則“左括弧出棧左括弧出棧”n否則表明不匹配否則表明不匹配n3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，）表達(dá)式檢驗(yàn)結(jié)束時(shí)，n若棧空，則表明表達(dá)式中匹配正確若?？眨瑒t表明表達(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運(yùn)算規(guī)則運(yùn)算規(guī)則n實(shí)現(xiàn)思想實(shí)現(xiàn)思想n設(shè)置兩個(gè)工作棧設(shè)置兩個(gè)工作棧n運(yùn)算符棧運(yùn)算符棧n操作數(shù)棧操作數(shù)棧n算法描述算法描述 2 1（）#（error ）error運(yùn)算規(guī)則運(yùn)算規(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)先表的存儲(chǔ)和表示算符優(yōu)先表的存儲(chǔ)和表示;n棧的選擇（靜態(tài)順序棧棧的選擇（靜態(tài)順序棧-用數(shù)組表示）用數(shù)組表示）n判斷判斷c是否為算符。是否為算符。nOperate(a,theta,b)

20、 的實(shí)現(xiàn)的實(shí)現(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的最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)值的最后一個(gè)結(jié)點(diǎn)的數(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個(gè)個(gè)3.問題的解法是遞歸的問題的解法是遞歸的例：例：Hanoi塔問題塔問題分析：分析：n n個(gè)個(gè) X Y Z 1. 將將X軸上的軸上的n1個(gè)盤子借助個(gè)盤子借助Z軸移到軸移到Y(jié)軸上；軸上；2.

22、將將X軸上的余下的軸上的余下的1個(gè)盤子移到個(gè)盤子移到Z軸上；軸上；3. 將將Y軸上的軸上的n1個(gè)盤子借助個(gè)盤子借助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ù)運(yùn)行期間使用的數(shù)據(jù)存儲(chǔ)區(qū)。作為遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲(chǔ)區(qū)。 內(nèi)容內(nèi)容： 函數(shù)返回地址函數(shù)返回地址 本次調(diào)用時(shí)與形參結(jié)合的實(shí)參本次調(diào)用時(shí)與形參結(jié)合的實(shí)參 本層的局部變量值本層的局部變量值3.3.2 遞歸過程與遞歸工作棧遞歸過程與遞歸工作棧n遞歸算法的優(yōu)點(diǎn)和

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

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

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

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

28、t;Qnode,*QueuePtr;typedef struct QueuePtr front； QueuePtr rear;LinkQueuen帶頭結(jié)點(diǎn)的鏈隊(duì)列示意圖：帶頭結(jié)點(diǎn)的鏈隊(duì)列示意圖： a1a2anQ.front Q.rear 1. 隊(duì)列的初始化隊(duì)列的初始化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. 隊(duì)列的銷毀隊(duì)列的銷

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. 入隊(duì)列入隊(duì)列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所謂入隊(duì)列即在隊(duì)尾之后插入一個(gè)新結(jié)點(diǎn)，并讓新所謂入隊(duì)列即在隊(duì)尾之后插入一個(gè)新結(jié)點(diǎn)，并讓新結(jié)點(diǎn)成為新的隊(duì)列尾結(jié)點(diǎn)成為新的隊(duì)列尾.a1a2anQ.frontQ.rearpe Q.rear4. 出隊(duì)列出隊(duì)列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é)點(diǎn)，需要考慮指向被刪除結(jié)點(diǎn)，需要考慮p是否為隊(duì)尾結(jié)點(diǎn)指針。是否為隊(duì)尾結(jié)點(diǎn)指針。 a1a2anQ.frontQ.rearp 5. 取隊(duì)首取隊(duì)首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 隊(duì)列順序存儲(chǔ)的表示和實(shí)現(xiàn)隊(duì)列順序存儲(chǔ)的表示和實(shí)現(xiàn)（1）空隊(duì)列）空隊(duì)列J1J2J3J4（2）J1、J2、J3、J4依次入隊(duì)列依次入隊(duì)列J4（3）J1、J2、J3依依

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

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

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

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

36、隊(duì)列n出隊(duì)列出隊(duì)列循環(huán)隊(duì)列循環(huán)隊(duì)列n1.隊(duì)列的初始化隊(duì)列的初始化Status InitQueue(SqQueue &Q) Q.base(ElemType*) malloc(MAXQSIZE*sizeof(ElemType); if (!Q.base) exit OVERFLOW; Q.frontQ.rear0; return OK;（1）空隊(duì)列）空隊(duì)列循環(huán)隊(duì)列循環(huán)隊(duì)列n2.求隊(duì)列的長度求隊(duì)列的長度int QueueLength(SqQueue Q)return (Q.rearQ.front+MAXQSIZE) % MAXQSIZE;循環(huán)隊(duì)列循環(huán)隊(duì)列n2.入隊(duì)列入隊(duì)列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.出隊(duì)列出隊(duì)列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 隊(duì)列應(yīng)用隊(duì)列應(yīng)用n1.判斷一個(gè)字符序列是否是回文。判斷一個(gè)字符序列是否是回文。n基本思想：基本思想：n將輸入字符逐個(gè)分別存入隊(duì)列和棧，然后逐個(gè)將輸入字符逐個(gè)分別存入隊(duì)列和棧，然后逐個(gè)出隊(duì)列和退棧并比較出隊(duì)列的字符和退棧的字出隊(duì)列和退棧并比較出隊(duì)列的字符和退棧的字符是否相等，若全部相