數(shù)據(jù)結構_堆棧和隊列的基本應用與原理

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

2、教學目標n掌握棧和隊列這兩種數(shù)據(jù)結構的特點，了解在什么問題中掌握棧和隊列這兩種數(shù)據(jù)結構的特點，了解在什么問題中應該使用哪種結構。應該使用哪種結構。n熟悉幾個關系：熟悉幾個關系：n棧（隊列）和線性表的關系；棧（隊列）和線性表的關系；n順序棧（順序隊列）和順序表的關系；順序棧（順序隊列）和順序表的關系；n鏈棧（鏈隊列）和鏈表的關系。鏈棧（鏈隊列）和鏈表的關系。n重點掌握在順序棧和鏈棧上實現(xiàn)的棧的七種基本運算，特重點掌握在順序棧和鏈棧上實現(xiàn)的棧的七種基本運算，特別注意棧滿和?？盏臈l件及它們的描述。別注意棧滿和?？盏臈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)是僅限制在表的一端進是僅限制在表的一端進行插入和刪除運算的線性表。通行插入和刪除運算的線性表。通常稱允許插入、刪除這一端為常稱允許插入、刪除這一端為棧棧頂頂（top），），另一端稱為另一端稱為棧底棧底(bottom)。n棧的修改是按后進先出的原則進棧的修改是按后進先出的原則進行的，故

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

5、ty(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.基本操作的算法表示基本操作的算法表示n初始化一個空棧初始

6、化一個空棧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(SqStack S,ElemType &e) if (S.base=

7、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=(ElemType*)realloc(S.base, (S.stacksize+STAC

8、KINCREMENT)*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答：答：3 2 1，2 3 1，2 1 3 ，1 3 2 ，1 2 3。n2.設將整數(shù)設將

9、整數(shù)1，2，3，4依次進棧，但只要出棧時棧依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回非空，則可將出棧操作按任何次序夾入其中，請回答下述問題：答下述問題： n(1)若入、出棧次序為若入、出棧次序為Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數(shù)字序列為何？則出棧的數(shù)字序列為何？ n(2) 能否得到出棧序列能否得到出棧序列1423和和1432?并說明為什么不能得到并說明為什么不能得到或者如何得到?；蛘呷绾蔚玫健?n(3)請分析請分析 1，2 ，3 ，4 的的24種排列中，哪些序列是可以通

10、種排列中，哪些序列是可以通過相應的入出棧操作得到的。過相應的入出棧操作得到的。 3.1.3 棧的共享存儲單元棧的共享存儲單元n引言引言n思考：兩個棧如何共享存儲空間？思考：兩個棧如何共享存儲空間？“底設兩端、相向而動、迎面增長底設兩端、相向而動、迎面增長”3.1.4 鏈棧的表示和實現(xiàn)鏈棧的表示和實現(xiàn)n1.棧的鏈式存儲表示棧的鏈式存儲表示typedef struct SNode ElemType data; struct SNode *next;SNode,*LinkStack;n問：問： 鏈棧中為何不設置頭結點鏈棧中為何不設置頭結點?n答：鏈棧不需要在頭部附加頭結點，因答：鏈棧不需要在頭部附加

11、頭結點，因為棧都是在頭部進行操作的，如果加了為棧都是在頭部進行操作的，如果加了頭結點，等于要對頭結點之后的結點進頭結點，等于要對頭結點之后的結點進行操作，反而使算法更復雜，所以只要行操作，反而使算法更復雜，所以只要有鏈表的首指針就可以了。有鏈表的首指針就可以了。 anan-1ai+1aia1棧頂棧頂棧底棧底n3.鏈?；静僮鞯膶崿F(xiàn)鏈棧基本操作的實現(xiàn)n初始化初始化S=NULL；n入棧入棧申請結點申請結點p； p-data=e;p-next=S;S=p;n判空：判空：n S=NULLn出棧：出棧：if (S=NULL) return ERROR;else p=S; S=p-next; e=p-da

12、ta; free(p); anan-1ai+1aia1棧頂棧頂棧底棧底練習練習n(1) 棧是限定在棧是限定在_處進行插入或刪除處進行插入或刪除操作的線性表。操作的線性表。 nA. 端點端點 B. 棧底棧底 C. 棧頂棧頂 D. 中間中間n(2) 4個元素按個元素按A、B、C、D順序連續(xù)進順序連續(xù)進S棧，棧， 進行進行Pop(S,x)運算后，運算后，x的值是的值是_。nA.A B. B C. C D. Dn(3) 棧的特點是棧的特點是_。nA. 先進先出先進先出 B. 后進先出后進先出 nC. 后進后出后進后出 D. 不進不出不進不出n(4) 棧與一般線性表的區(qū)別主要在棧與一般線性表的區(qū)別主要在

13、_方面。方面。nA. 元素個數(shù)元素個數(shù) B. 元素類型元素類型nC. 邏輯結構邏輯結構 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 棧的應用舉例棧的應用舉例n3.2.1 數(shù)制轉換數(shù)制轉換 void conversion() InitStack(S); scanf( %d ,&N); while (N) Push(S,N%8); N

14、=N/8; /while while(!StackEmpty(S) Pop (S,e); printf( %d ,e); 將除將除8的余數(shù)依次入棧的余數(shù)依次入棧S，先得的先得的余數(shù)為低位，后得的余數(shù)為高位余數(shù)為低位，后得的余數(shù)為高位。從棧頂?shù)綏５自匾来纬鰲?，從棧頂?shù)綏５自匾来纬鰲＃玫綄牡玫綄?進制數(shù)進制數(shù)3. 2 棧的應用舉例棧的應用舉例n3.2.2 括號匹配的檢查括號匹配的檢查n例如：n（）n（ ）n（ ）n（ ）n（）n算法的設計思想：算法的設計思想：n1）凡出現(xiàn)左括弧，則進棧；）凡出現(xiàn)左括弧，則進棧；n2）凡出現(xiàn)右括弧，首先檢查棧是否空）凡出現(xiàn)右括弧，首先檢查棧是否空n若棧

15、空，則表明該若?？?，則表明該“右括弧右括弧”多余多余n否則和棧頂元素比較，否則和棧頂元素比較，n若相匹配，則若相匹配，則“左括弧出棧左括弧出?！眓否則表明不匹配否則表明不匹配n3）表達式檢驗結束時，）表達式檢驗結束時，n若?？眨瑒t表明表達式中匹配正確若?？?，則表明表達式中匹配正確n否則表明否則表明“左括弧左括弧”有余有余Status Compare( ) InitStack(S); flag=TURE; while （ch= getchar( )）?。?#） & flag ） switch (ch) case ( :case :caxe :Push(S,ch);break;case ) :i

16、f ( 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 迷宮求解迷宮求解出出口口入入口口n求迷宮路徑算法的基本思想是：求迷宮路徑算法的基本思想是：n若當前位置若當前位置“可通可通”，則納入路徑，繼續(xù)前進，則

17、納入路徑，繼續(xù)前進;n若當前位置若當前位置“不可通不可通”，則后退，換方向繼續(xù)探，則后退，換方向繼續(xù)探索索;n若四周若四周“均無通路均無通路”，則將當前位置從路徑中刪，則將當前位置從路徑中刪除出去。除出去。n求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法：設定當前位置的初值為入口位置；設定當前位置的初值為入口位置； do 若當前位置可通，若當前位置可通， 則將當前位置插入棧頂；則將當前位置插入棧頂； 若該位置是出口位置，則算法結束；若該位置是出口位置，則算法結束； 否則切換當前位置的東鄰方塊為新的當前位置；否則切換當前位置的東鄰方塊為新的當前位置； 否則否則 whi

18、le (棧不空）；棧不空）；3.2.4 表達式求值表達式求值n運算規(guī)則運算規(guī)則n實現(xiàn)思想實現(xiàn)思想n設置兩個工作棧設置兩個工作棧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)!=#) if （c為操作數(shù)）為操作數(shù)） Push(OPND,c);c=getchar(); else switch Precede

19、(GetTop(OPTR),c) case :Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b);break; /switch/while/ Evaluateexpressn有關思考與提示有關思考與提示n算符優(yōu)先表的存儲和表示算符優(yōu)先表的存儲和表示;n棧的選擇（靜態(tài)順序棧棧的選擇（靜態(tài)順序棧-用數(shù)組表示）用數(shù)組表示）n判斷判斷c是否為算符。是否為算符。nOperate(a,theta,b) 的實現(xiàn)的實現(xiàn)Int change(char c)Switch c ofcase +:i=0;break;case -:

20、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)fact(1)fact(0)112624函數(shù)函數(shù)調用與返回調用與返回 返回值返回值n2.遞歸的數(shù)據(jù)結構遞歸的數(shù)據(jù)結構n例

21、例1：線性鏈表結構：線性鏈表結構打印非空鏈表打印非空鏈表f的最后一個結點的數(shù)據(jù)值的最后一個結點的數(shù)據(jù)值void find (Linklist f) if (f-next=NULL) printf(f-data); else find(f-next);n例例2：樹型結構：樹型結構n-1n-1個個3.問題的解法是遞歸的問題的解法是遞歸的例：例：Hanoi塔問題塔問題分析：分析：n n個個 X Y Z 1. 將將X軸上的軸上的n1個盤子借助個盤子借助Z軸移到軸移到Y軸上；軸上；2.將將X軸上的余下的軸上的余下的1個盤子移到個盤子移到Z軸上；軸上；3. 將將Y軸上的軸上的n1個盤子借助個盤子借助X軸移

22、到軸移到Z軸上軸上 X求解算法及調用示意圖求解算法及調用示意圖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,a,c)move(a,c)move(a,c)move(b,c)move(b,a)move(c,b)move(a,b)m

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

24、序具有結構簡潔清晰、易讀易理解結構簡潔清晰、易讀易理解等優(yōu)點。等優(yōu)點。n然而由于使用棧來實現(xiàn)這種然而由于使用棧來實現(xiàn)這種“調用調用返回返回”的的遞歸過程，無論在遞歸過程，無論在時間時間上還是在上還是在空間空間上都比相上都比相應的非遞歸程序的開銷要大。應的非遞歸程序的開銷要大。3.4 隊列隊列n隊列的定義隊列的定義n隊列隊列(Queue)是僅限制在表的一端進行插入，另是僅限制在表的一端進行插入，另一端進行刪除運算的線性表。通常稱允許插入一端進行刪除運算的線性表。通常稱允許插入一端為一端為隊尾隊尾（rear），），另一端稱為另一端稱為隊頭隊頭(front)。n隊列的修改是按先進先出的原則進行的，故

25、又隊列的修改是按先進先出的原則進行的，故又稱棧為稱棧為FIFO表表(Fast In First Out)。隊頭隊頭隊尾隊尾入隊列入隊列出隊列出隊列anan-1a3a2a1n例如：例如：n到醫(yī)院看病，首先需要到掛號處掛號，然后，按到醫(yī)院看病，首先需要到掛號處掛號，然后，按號碼順序救診。號碼順序救診。n乘坐公共汽車，應該在車站排隊，車來后，按順乘坐公共汽車，應該在車站排隊，車來后，按順序上車。序上車。n在在Windows這類多任務的操作系統(tǒng)環(huán)境中，每個這類多任務的操作系統(tǒng)環(huán)境中，每個應用程序響應一系列的應用程序響應一系列的“消息消息”，像用戶點擊鼠，像用戶點擊鼠標；拖動窗口這些操作都會導致向應用程

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

27、尾基本操作：基本操作： 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 *next;Qnode,*QueuePtr;typedef struct QueuePtr front； QueuePtr rear;LinkQueuen帶頭結點的鏈隊列示意圖

28、：帶頭結點的鏈隊列示意圖： 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. 隊列的銷毀隊列的銷毀Status DestroyQueue(LinkQueue &Q) while (Q.front) Q.rear=Q.front-next; free(Q.front); Q

29、.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; return OK;n說明：說明：n所謂入隊列即在隊尾之后插入一個新結點，并讓新所謂入隊列即在隊尾之后插入一個新結點，并讓新結點成為新的隊列尾結點成為新的隊列尾.a1a2anQ.frontQ.rear

30、pe 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; 注意注意：p指向被刪除結點，需要考慮指向被刪除結點，需要考慮p是否為隊尾結點指針。是否為隊尾結點指針。 a1a2anQ.frontQ.rearp 5. 取隊首取隊首Status GetHead(LinkQueue Q,

31、 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依依次出隊列次出隊列J4J5J6（4）J5、J6依次依次入隊列入隊列順序隊列的特點順序隊列的特點1. 設立兩棵指針設立兩棵指針Q.front和和 Q.rear2. 隊空的判定條件隊空的判定條件:Q.front= Q.re

32、ar3. 隊滿的判定條件隊滿的判定條件:Q.rearQ.Maxsize隊列的順序存儲結構隊列的順序存儲結構n存儲結構定義存儲結構定義#define MAXQSIZE 100typedef struct ElemType *base; int front; int rear;SqQueue;n順序隊列的順序隊列的“溢出溢出”問題問題n(1)真溢出真溢出nQ.rear Q.front Q.Maxsizen(2)假溢出假溢出n順序隊列因多次入隊和出隊操作后出現(xiàn)的有存儲空間順序隊列因多次入隊和出隊操作后出現(xiàn)的有存儲空間但不能進行入隊操作的溢出。但不能進行入隊操作的溢出。n問題：問題：n如何解決順序隊列

33、的如何解決順序隊列的“假溢出假溢出”問題？問題？n答：答：n按最大可能的進隊操作次數(shù)設置順序隊列的最大按最大可能的進隊操作次數(shù)設置順序隊列的最大元素個數(shù)；元素個數(shù)；n修改出隊算法，使每次出隊列后都把隊列中剩余修改出隊算法，使每次出隊列后都把隊列中剩余數(shù)據(jù)元素向隊頭方向移動一個位置；數(shù)據(jù)元素向隊頭方向移動一個位置；n修改入隊算法，增加判斷條件，當假溢出時，把修改入隊算法，增加判斷條件，當假溢出時，把隊列中的數(shù)據(jù)元素向隊頭移動，然后方完成入隊隊列中的數(shù)據(jù)元素向隊頭移動，然后方完成入隊操作。操作。n采用循環(huán)隊列；采用循環(huán)隊列；循環(huán)隊列循環(huán)隊列n1.基本思想基本思想n2.示意圖示意圖順序隊列順序隊列J

34、1J2J3Q.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ù)器記錄隊列中元素個數(shù)（即隊列使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；長度）；n判隊滿：判隊滿：countMAXQSIZEn判隊空：判隊空：count=0n加設標志位加設標志位n判隊滿：判隊滿：tag=1 &

35、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入隊列入隊列n出隊列出隊列循環(huán)隊列循環(huán)隊列n1.隊列的初始化隊列的初始化Status InitQueue(SqQueue &Q) Q.base(ElemType*) malloc(MAXQSIZE*sizeof(ElemType); if

36、(!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 EnQueue(SqQueue &Q, ElemType e) if (Q.rear+1)% MAXQSIZE=Q.front) return ERROR; Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE;

37、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 隊列應用隊列應用n1.判斷一個字符序列是否是回文。判斷一個字符序列是否是回文。n基本思想：基本思想：n將輸入字符逐個分別存入隊列和棧，然后逐個將輸入字符逐個分別存入隊列和棧，然后逐個出隊列和退棧并比較出隊列的字符和退棧的字出隊列和退棧并比較出隊列的字符和退棧的字符是否相等，若全部相等則該字符序列是回文，符是