1、第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.1棧棧3.2 棧棧的應(yīng)用的應(yīng)用3.3 隊(duì)列隊(duì)列3.4 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用3.5 棧與遞歸棧與遞歸教學(xué)內(nèi)容教學(xué)內(nèi)容1.1.掌握棧和隊(duì)列的掌握棧和隊(duì)列的特點(diǎn)特點(diǎn)，并能在相應(yīng)的應(yīng)用問，并能在相應(yīng)的應(yīng)用問題中正確選用題中正確選用2.2.熟練掌握棧的熟練掌握棧的兩種存儲結(jié)構(gòu)兩種存儲結(jié)構(gòu)的基本操作實(shí)現(xiàn)的基本操作實(shí)現(xiàn)算法，特別應(yīng)注意算法，特別應(yīng)注意棧滿和棧空棧滿和?？盏臈l件的條件3.3.熟練掌握熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)的基本操作實(shí)現(xiàn)算法，特別注意算法，特別注意隊(duì)滿和隊(duì)空隊(duì)滿和隊(duì)空的的條件條件4.4.理解理解遞歸算法遞歸算法執(zhí)行過程中棧的狀態(tài)

2、變化過程執(zhí)行過程中棧的狀態(tài)變化過程 教學(xué)目標(biāo)教學(xué)目標(biāo)3.1 3.1 棧棧1. 1. 定義定義用順序存儲結(jié)構(gòu)用順序存儲結(jié)構(gòu)（順序棧）（順序棧）或鏈?zhǔn)酱鎯Y(jié)或鏈?zhǔn)酱鎯Y(jié)構(gòu)構(gòu)（鏈棧）（鏈棧）存儲均可，但順序棧更常見存儲均可，但順序棧更常見3. 3. 存儲結(jié)構(gòu)存儲結(jié)構(gòu)與線性表相同，仍為與線性表相同，仍為一對一一對一關(guān)系關(guān)系2. 2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)只能在只能在表的一端表的一端（表尾表尾）進(jìn)行插入和刪）進(jìn)行插入和刪除運(yùn)算的除運(yùn)算的線性表線性表a1a2an棧底棧底棧頂棧頂出棧出棧進(jìn)棧進(jìn)棧術(shù)語：術(shù)語：棧頂、棧底、棧頂、棧底、進(jìn)棧、出棧、進(jìn)棧、出棧、空?？諚Ｖ荒茉谥荒茉跅ｍ敆ｍ斶\(yùn)算運(yùn)算后進(jìn)先出后進(jìn)先出（LI

3、FOLIFO）或或先進(jìn)后出先進(jìn)后出（FILOFILO）4.4.運(yùn)算規(guī)則運(yùn)算規(guī)則基本操作有基本操作有入棧、出棧、讀棧頂元素值、入棧、出棧、讀棧頂元素值、初始化棧、判斷?？粘跏蓟瘲?、判斷棧空等等入棧入棧和和出棧出棧函數(shù)最關(guān)鍵，具體實(shí)現(xiàn)依順函數(shù)最關(guān)鍵，具體實(shí)現(xiàn)依順序棧或鏈棧的不同而不同序?；蜴湕５牟煌煌?.5.實(shí)現(xiàn)方式實(shí)現(xiàn)方式棧是一種特殊的線性表，它只能在表的一端（棧頂）棧是一種特殊的線性表，它只能在表的一端（棧頂）進(jìn)行插入和刪除運(yùn)算進(jìn)行插入和刪除運(yùn)算棧與一般線性表的區(qū)別：僅在于棧與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則運(yùn)算規(guī)則不同不同一般線性表一般線性表 邏輯結(jié)構(gòu)：一對一邏輯結(jié)構(gòu)：一對一 存儲結(jié)構(gòu)：

4、順序表、鏈表存儲結(jié)構(gòu)：順序表、鏈表 運(yùn)算規(guī)則：隨機(jī)運(yùn)算規(guī)則：隨機(jī)、順序存取順序存取棧棧邏輯結(jié)構(gòu)：一對一邏輯結(jié)構(gòu)：一對一 存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：順序棧棧、鏈、鏈棧棧運(yùn)算規(guī)則：運(yùn)算規(guī)則：后進(jìn)先出后進(jìn)先出棧與一般線性表的區(qū)別棧與一般線性表的區(qū)別ADT Stack 數(shù)據(jù)對象：數(shù)據(jù)對象：D=ai|aiElemSet, i=1,2,.,n, n=0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R= |ai,ai+1D, i=1,2,.,n-1 基本操作：基本操作： InitStack(StackType &S) DestroyStack(StackType &S) ClearStack (StackType

5、&S) StackEmpty (StackType S) StackLength(StackType S) Push(StackType &S, ElemType e) Pop(StackType &S, ElemType &e) GetTop(SqStack S) StackTraverse(StackType S)ADT Stack棧的抽象數(shù)據(jù)類型棧的抽象數(shù)據(jù)類型1.有有6個元素個元素A、B、C、D、E、F依次進(jìn)棧，允許依次進(jìn)棧，允許任何時候出棧，能否得到下列的出棧序列：任何時候出棧，能否得到下列的出棧序列：(1) CDBEFA (2) ABEDFC(3)

6、DCEABF (4) BAEFCD2.有有3個元素個元素a、b、c依次進(jìn)棧，任何時候都可以依次進(jìn)棧，任何時候都可以出棧，請寫出所有可能的出棧序列。出棧，請寫出所有可能的出棧序列。棧操作運(yùn)算棧操作運(yùn)算5種種順序棧的表示順序棧的表示空?？諚ase = top 是棧空是?？諛?biāo)志標(biāo)志stacksize = 4topAbasebasetopABABCtopbasetopbaseABCDbasetop3120top top 指示真正的指示真正的棧頂元素之上棧頂元素之上的地址的地址棧滿時的處理方法：棧滿時的處理方法：1 1、報(bào)錯報(bào)錯, ,返回操作系統(tǒng)。返回操作系統(tǒng)。2 2、分配更大的空間分配更大的空間，作

7、為棧的存儲空，作為棧的存儲空間間, ,將原棧的內(nèi)容移入新棧。將原棧的內(nèi)容移入新棧。#define MAXSIZE 100typedef structSElemType *base;SElemType *top; int stacksize;SqStack;順序棧的表示順序棧的表示空棧判斷條件：空棧判斷條件：base = top 棧滿判斷條件：棧滿判斷條件： top = base + stacksizebasetop3120topbaseABCD 構(gòu)造一個空棧構(gòu)造一個空棧 步驟：步驟：(1)(1)分配空間并檢查空間是否分配空間并檢查空間是否分配失敗，若失敗則返回分配失敗，若失敗則返回錯誤錯誤順序

8、棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)-初始化初始化basestacksizetops(2)(2)設(shè)置棧頂指針設(shè)置棧頂指針 S.top = S.base;(3)(3)設(shè)置棧大小設(shè)置棧大小void InitStack( SqStack &S ) S.base =new SElemTypeMAXSIZE；if( !S.base ) exit(OVERFLOW);S.top = S.base;S.stacksize = MAXSIZE;順序棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)-判斷棧是否為空判斷棧是否為空bool StackEmpty( SqStack S )if (S.top = S.base) return true;

9、else return false;basetop3120順序棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)-求棧的長度求棧的長度int StackLength( SqStack S ) return S.top S.base;basetopABvoid ClearStack( SqStack &S ) S.top = S.base;順序棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)-清空清空basetop3120void DestroyStack( SqStack &S ) if( S.base ) delete S.base;S.stacksize = 0;S.base = S.top = NULL; 順序棧的實(shí)現(xiàn)順序棧的實(shí)

10、現(xiàn)-銷毀銷毀(1)(1)判斷是否棧滿，若滿則重新分配空間判斷是否棧滿，若滿則重新分配空間(2)(2)元素元素e e壓入棧頂壓入棧頂(3)(3)棧頂指針加棧頂指針加1 1順序棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)-進(jìn)棧進(jìn)棧void Push( SqStack &S, SElemType e) if ( S.top - S.base= S.stacksize ) / 棧滿棧滿 S.base = (SElemType *) realloc( S.base, 2*S.stacksize *sizeof(SElemType) ); S.top = S.base+ S.stacksize; S.stacksize

11、= 2*S.stacksize;*S.top+=e;*S.top=e;S.top+;ABCtopbase(1)(1)判斷是否?？?，若空則出錯判斷是否?？眨艨談t出錯(2)(2)獲取棧頂元素獲取棧頂元素e e(3)(3)棧頂指針減棧頂指針減1 1順序棧的實(shí)現(xiàn)順序棧的實(shí)現(xiàn)-出棧出棧void Pop( SqStack &S, SElemType &e) if ( S.top = S.base ) / ?？諚？?cerr“棧已空無數(shù)據(jù)元素出棧！棧已空無數(shù)據(jù)元素出棧！”data=e; p-next=S; S=p; pSpSe鏈棧的實(shí)現(xiàn)鏈棧的實(shí)現(xiàn)-進(jìn)棧進(jìn)棧void Push(LinkSta

12、ck &S , SElemType e) StackNode *p; p=new StackNode; /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; pSe鏈棧的實(shí)現(xiàn)鏈棧的實(shí)現(xiàn)-進(jìn)棧進(jìn)棧void Push(LinkStack &S , SElemType e) StackNode *p; p=new StackNode; /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; pSeS鏈棧的實(shí)現(xiàn)鏈棧的實(shí)現(xiàn)-進(jìn)棧進(jìn)棧void Push(

13、LinkStack &S , SElemType e) StackNode *p; p=new StackNode; /生成新結(jié)點(diǎn)生成新結(jié)點(diǎn)p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; 鏈棧的實(shí)現(xiàn)鏈棧的實(shí)現(xiàn)-出棧出棧SAe = Avoid Pop (LinkStack &S, SElemType &e) StackNode *p; if (S=NULL) cerr“棧已空無數(shù)據(jù)元素出棧！棧已空無數(shù)據(jù)元素出棧！” data; p = S; S = S- next; delete p; SAe = Ap鏈棧的實(shí)現(xiàn)鏈棧的

14、實(shí)現(xiàn)-出棧出棧void Pop (LinkStack &S, SElemType &e) StackNode *p; if (S=NULL) cerr“棧已空無數(shù)據(jù)元素出棧！棧已空無數(shù)據(jù)元素出棧！” data; p = S; S = S- next; delete p; SAe = ApS鏈棧的實(shí)現(xiàn)鏈棧的實(shí)現(xiàn)-出棧出棧void Pop (LinkStack &S, SElemType &e) StackNode *p; if (S=NULL) cerr“棧已空無數(shù)據(jù)元素出棧！棧已空無數(shù)據(jù)元素出棧！” data; p = S; S = S- next; delet

15、e p; e = AS鏈棧的實(shí)現(xiàn)鏈棧的實(shí)現(xiàn)-出棧出棧void Pop (LinkStack &S, SElemType &e) StackNode *p; if (S=NULL) cerr“棧已空無數(shù)據(jù)元素出棧！棧已空無數(shù)據(jù)元素出棧！” data; p = S; S = S- next; delete p; 鏈棧的實(shí)現(xiàn)鏈棧的實(shí)現(xiàn)-取棧頂元素取棧頂元素SElemType GetTop(LinkStack S) if (S!=NULL) / 棧非空棧非空 return S- data;SA3.2 3.2 棧的應(yīng)用棧的應(yīng)用例例1 1：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N N）用棧暫存余數(shù)

16、低位值用棧暫存余數(shù)低位值例例2 2：括號匹配的檢驗(yàn)括號匹配的檢驗(yàn) 用棧暫存左括號用棧暫存左括號例例3 3：表達(dá)式求值：表達(dá)式求值用棧暫存運(yùn)算符和操作數(shù)用棧暫存運(yùn)算符和操作數(shù)1、數(shù)制轉(zhuǎn)換、數(shù)制轉(zhuǎn)換 把一個十進(jìn)制數(shù)轉(zhuǎn)換成其他進(jìn)制數(shù)（把一個十進(jìn)制數(shù)轉(zhuǎn)換成其他進(jìn)制數(shù)（29進(jìn)進(jìn)制）。制）。1348816882148205 (1348)10 = (2504)8802把余數(shù)依次入棧，最后再依次出棧。把余數(shù)依次入棧，最后再依次出棧。既可使用順序棧，也可使用鏈棧，我們采用順序棧。既可使用順序棧，也可使用鏈棧，我們采用順序棧。#include #include #define MAXSIZE 100typedef

17、 int SElemType;typedef structSElemType *base;SElemType *top; int stacksize;SqStack;#include “SeqStack.h” void Transform ( long num, int r) / 轉(zhuǎn)換轉(zhuǎn)換num為為r進(jìn)制數(shù)，并輸出進(jìn)制數(shù)，并輸出 SqStack a; SElemType e; InitStack(a) ; while (num) Push( a , num % r ); / 取余并入棧取余并入棧 num = num / r; / 整除整除 while ( !StackEmpty (a) ) P

18、op(a, e); coute; / 出棧并輸出出棧并輸出 coutendl; DestroyStack(a); void main() cout“3425的八進(jìn)制數(shù)為的八進(jìn)制數(shù)為: ”; Transform(3425, 8); cout“3425的二進(jìn)制數(shù)為的二進(jìn)制數(shù)為: ”; Transform(3425, 2);2、括號匹配的檢驗(yàn)、括號匹配的檢驗(yàn) 棧常被用于在計(jì)算機(jī)語言的編譯過程中進(jìn)行語法檢查。如：棧常被用于在計(jì)算機(jī)語言的編譯過程中進(jìn)行語法檢查。如：檢查程序中的大括號、方括號、圓括號是否配對。檢查程序中的大括號、方括號、圓括號是否配對。如如: ( x + y ) * 8 / (a-b)

19、; ( x + y ) * 8 / a-b) ; ( x + y ) )* 8 / (a-b) ; ( ( x + y ) * 8 / (a-b) ; 順序掃描表達(dá)式，當(dāng)讀入字符為：順序掃描表達(dá)式，當(dāng)讀入字符為： 左括號：進(jìn)棧；左括號：進(jìn)棧； 右括號：若棧頂元素與之配對，則出棧，繼續(xù)讀下一個；右括號：若棧頂元素與之配對，則出棧，繼續(xù)讀下一個； 若棧頂元素與之不配對，則配對次序不正確，若棧頂元素與之不配對，則配對次序不正確， 程序終止；程序終止； 若?？眨瑒t若?？眨瑒t 左括號左括號 右括號，程序終止右括號，程序終止;bool Matching() Stack S; char e; int fla

20、g=1; char ch; InitStack(S) ; cinch; while (ch!=# & flag) switch(ch) case | (: Push( S,ch ); break; case ): if (!StackEmpty (S) & GetTop(S)=( ) Pop(S, e); else flag=0; break; case : if (!StackEmpty (S) & GetTop(S)= ) Pop(S, e); else flag=0; break; /switch cinch; /while if ( StackEmpty(S)

21、& flag ) return true; else return false;3、表達(dá)式求值表達(dá)式求值表達(dá)式表達(dá)式常數(shù)常數(shù)標(biāo)識符標(biāo)識符操作數(shù)操作數(shù)(operand)(operand)運(yùn)算符運(yùn)算符(operator)(operator)界限符界限符(delimiter)(delimiter)算術(shù)算術(shù)邏輯邏輯關(guān)系關(guān)系括號括號結(jié)束符結(jié)束符只考慮只考慮算術(shù)運(yùn)算算術(shù)運(yùn)算，算術(shù)四則運(yùn)算規(guī)則，算術(shù)四則運(yùn)算規(guī)則: :(1) (1) 先乘除先乘除, ,后加減后加減(2) (2) 從左算到右從左算到右(3) (3) 先括號內(nèi)先括號內(nèi), ,后括號外后括號外12+-*/()#+-*/()#x=xx 算符間的

22、優(yōu)先關(guān)系算符間的優(yōu)先關(guān)系【算法思想算法思想】（1）初始化）初始化OPTR棧和棧和OPND棧，將棧，將 “#”壓入壓入OPTR（2）讀入第一個字符）讀入第一個字符ch，當(dāng)，當(dāng)OPTR的棧頂元素和的棧頂元素和 ch均為均為“#”時，表達(dá)式求值完畢，時，表達(dá)式求值完畢，OPND棧頂元素為表達(dá)式的值，棧頂元素為表達(dá)式的值，否則循環(huán)執(zhí)行以下操作：否則循環(huán)執(zhí)行以下操作：設(shè)定兩棧設(shè)定兩棧 ：OPND-OPND-操作數(shù)操作數(shù), OPTR-, OPTR-運(yùn)算符運(yùn)算符（ 3） if (ch是操作數(shù)是操作數(shù)) 則則ch進(jìn)進(jìn)OPND，讀入下一字符，讀入下一字符ch else 比較比較OPTR棧頂元素和棧頂元素和ch的

23、優(yōu)先級的優(yōu)先級case : 棧頂運(yùn)算符退棧、計(jì)算，結(jié)果進(jìn)棧頂運(yùn)算符退棧、計(jì)算，結(jié)果進(jìn)OPNDOPTROPNDINPUTOPERATE3*(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)# 為

24、簡化問題，只考慮一位數(shù)為簡化問題，只考慮一位數(shù)int EvaluateExpression( ) InitStack (OPND); InitStack (OPTR); Push(OPTR, #); ch = getchar(); while ( !(ch=# & GetTop(OPTR)=#) ) if (! In(ch) / ch不是運(yùn)算符則進(jìn)棧不是運(yùn)算符則進(jìn)棧 Push(OPND, ch); ch = getchar(); else switch (Precede( GetTop(OPTR),ch) ) /比較優(yōu)先權(quán)比較優(yōu)先權(quán) case : /彈出彈出OPTR棧頂?shù)倪\(yùn)算符棧頂?shù)倪\(yùn)

25、算符,運(yùn)算后將結(jié)果入棧運(yùn)算后將結(jié)果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b) ); break; case = : /脫括號并接收下一字符脫括號并接收下一字符 Pop(OPTR, x); ch = getchar(); break; / switch / while return GetTop(OPND); 3.3 3.3 隊(duì)列隊(duì)列隊(duì)列也是一種操作受限的線性表，只允許在表的一隊(duì)列也是一種操作受限的線性表，只允許在表的一端進(jìn)行插入（表尾），在表的另一端進(jìn)行刪除（表端進(jìn)行插入（表尾

26、），在表的另一端進(jìn)行刪除（表頭）。頭）。a1a2a3an.入隊(duì)列入隊(duì)列隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾先進(jìn)先出先進(jìn)先出(FIFO)的線性表的線性表術(shù)語：術(shù)語：隊(duì)頭、隊(duì)尾、入隊(duì)頭、隊(duì)尾、入隊(duì)列、出隊(duì)列、空隊(duì)列。隊(duì)列、出隊(duì)列、空隊(duì)列。出隊(duì)列出隊(duì)列ADT Queue 數(shù)據(jù)對象：數(shù)據(jù)對象： D=ai|aiElemSet, i=1,2,.,n, n=0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R= |ai,ai+1D, i=1,2,.,n-1 基本操作：基本操作： InitQueue (&Q) /構(gòu)造空隊(duì)列構(gòu)造空隊(duì)列 DestroyQueue (&Q) /銷毀隊(duì)列銷毀隊(duì)列 ClearQueue (&Q) /清空隊(duì)

27、列清空隊(duì)列 QueueEmpty(Q) /判空判空 QueueLength(Q) /取隊(duì)列長度取隊(duì)列長度 GetHead (Q) /取隊(duì)頭元素取隊(duì)頭元素 EnQueue (&Q,e) /入隊(duì)列入隊(duì)列 DeQueue (&Q,&e) /出隊(duì)列出隊(duì)列 QueueTraverse(Q) /遍歷遍歷ADT Queue隊(duì)列的抽象數(shù)據(jù)類型隊(duì)列的抽象數(shù)據(jù)類型順序存儲結(jié)構(gòu)的隊(duì)列稱為順序存儲結(jié)構(gòu)的隊(duì)列稱為順序隊(duì)列順序隊(duì)列#define MAXQSIZE 100 /初始初始最大隊(duì)列長度最大隊(duì)列長度typedef struct QElemType *base; /初始化的動態(tài)分配存儲空間初始

28、化的動態(tài)分配存儲空間 int front; /頭指針頭指針，指向隊(duì)頭元素的位置，指向隊(duì)頭元素的位置 int rear; /尾指針，指向隊(duì)尾元素的下一個位置尾指針，指向隊(duì)尾元素的下一個位置 int queuesize; /最大隊(duì)列長度最大隊(duì)列長度SqQueue; 隊(duì)列的順序表示隊(duì)列的順序表示a1a2a3a4a5 0 1 2 3 4 queuesize -1 front rear base隊(duì)列的順序表示隊(duì)列的順序表示frontfront0 01 12 23 34 45 5rearrearfrontfrontrearrearJ J1 1J J2 2J J3 3frontfrontrearrearJ

29、J3 3frontfrontrearrearJ J5 5J J6 6front=rear=0空隊(duì)標(biāo)志：空隊(duì)標(biāo)志：front= =rear入隊(duì)：入隊(duì)：baserear+=x;出隊(duì)：出隊(duì)：x=basefront+;base frontfrontrearrearJ5J5J6J6frontfront0 01 12 23 34 45 5rearrearJ5J5J6J6J1J1J2J2J3J3J4J4存在的問題存在的問題數(shù)組大小為數(shù)組大小為queuesizefront=0rear=queuesize時時再入隊(duì)再入隊(duì)真溢出真溢出front 0rear=queuesize時時再入隊(duì)再入隊(duì)假溢出假溢出解決的方法

30、循環(huán)隊(duì)列解決的方法循環(huán)隊(duì)列1 10 0Q.rearQ.rearQ.frontQ.front.base0接在接在basequeuesize-1之之后后實(shí)現(xiàn)：利用實(shí)現(xiàn)：利用“模?！边\(yùn)算運(yùn)算入隊(duì)：入隊(duì)： baserear=x; rear=(rear+1)%queuesize;出隊(duì)：出隊(duì)： x=basefront; front=(front+1)%queuesize; 順序隊(duì)列存在一個順序隊(duì)列存在一個假溢出問題，假溢出問題，解決辦法是構(gòu)造解決辦法是構(gòu)造一個邏輯上首尾相連的循環(huán)空間，稱為一個邏輯上首尾相連的循環(huán)空間，稱為循環(huán)隊(duì)列循環(huán)隊(duì)列J4J4J5J5J6J60 01 12 23 34 45 5rear

31、rearfrontfrontJ9J9J8J8J7J7J7,J8,J9J7,J8,J9入隊(duì)入隊(duì)隊(duì)空：隊(duì)空：front=rearfront=rear隊(duì)滿：隊(duì)滿：front=rearfront=rearJ4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfront0 01 12 23 34 45 5frontfrontJ4,J5,J6J4,J5,J6出隊(duì)出隊(duì)rearrear如何判斷如何判斷循環(huán)隊(duì)列的隊(duì)滿與隊(duì)空情況？循環(huán)隊(duì)列的隊(duì)滿與隊(duì)空情況？J4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfrontJ8J8J7J7循環(huán)隊(duì)列的隊(duì)滿與

32、隊(duì)空判斷問題解決辦法：循環(huán)隊(duì)列的隊(duì)滿與隊(duì)空判斷問題解決辦法：1. 設(shè)置一個長度變量設(shè)置一個長度變量len，用以統(tǒng)計(jì)隊(duì)列的元素個數(shù)，用以統(tǒng)計(jì)隊(duì)列的元素個數(shù) 當(dāng)有元素入隊(duì)時當(dāng)有元素入隊(duì)時: len+ ; 元素出隊(duì)時：元素出隊(duì)時：len- 隊(duì)滿條件：隊(duì)滿條件： len= queuesize 隊(duì)空條件隊(duì)空條件: len=0 2.少用一個元素空間少用一個元素空間： 隊(duì)空：隊(duì)空：front=rear 隊(duì)滿：隊(duì)滿：(rear+1)% queuesize=front0 01 12 23 34 45 5frontfrontrearrearvoid InitQueue (SqQueue &Q) Q.bas

33、e =new QElemTypeMAXQSIZE; if (!Q.base) exit(OVERFLOW); Q.queuesize= MAXQSIZE; Q.front=Q.rear=0;循環(huán)隊(duì)列實(shí)現(xiàn)循環(huán)隊(duì)列實(shí)現(xiàn)-初始化初始化typedef struct QElemType *base; int front, rear; int queuesize; SqQueue; bool QueueEmpty(SqQueue Q) return Q.front=Q.rear; 循環(huán)隊(duì)列實(shí)現(xiàn)循環(huán)隊(duì)列實(shí)現(xiàn)-判斷是否為空判斷是否為空循環(huán)隊(duì)列實(shí)現(xiàn)循環(huán)隊(duì)列實(shí)現(xiàn)-求長度求長度int QueueLength (Sq

34、Queue Q) return (Q.rear-Q.front+Q.queuesize)%Q.queuesize;J4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfrontJ8J8J7J70 01 12 23 34 45 5frontfrontrearrearJ4J4J5J5首先判斷隊(duì)列是否已滿，若滿，重新分配更大的空間首先判斷隊(duì)列是否已滿，若滿，重新分配更大的空間循環(huán)隊(duì)列實(shí)現(xiàn)循環(huán)隊(duì)列實(shí)現(xiàn)-入隊(duì)入隊(duì)EFCDrear=2front=34321098765CDrear=7front=343210EF98765EFCDrear=2front=343210隊(duì)列已滿

35、隊(duì)列已滿EFHrear=4front=043210 Gvoid EnQueue(SqQueue &Q, QElemType e) if (Q.rear+1)% Q.queuesize =Q.front) /若隊(duì)列已滿，重新分配若隊(duì)列已滿，重新分配 Q.base = (QElemType *) realloc (Q.base, 2* Q.queuesize *sizeof(QElemType); if (Q.rear != Q.queuesize-1) /原隊(duì)列尾部內(nèi)容向后移原隊(duì)列尾部內(nèi)容向后移 for ( int i=0; i=Q.rear-1; i+) Q.base i+Q. que

36、uesize = Q.basei; Q.rear = Q.rear + Q. queuesize; Q. queuesize = 2*Q. queuesize; Q.baseQ.rear=e; Q.rear=(Q.rear+1)% Q.queuesize;循環(huán)隊(duì)列實(shí)現(xiàn)循環(huán)隊(duì)列實(shí)現(xiàn)-入隊(duì)入隊(duì)CDrear=7front=343210EF98765void DeQueue (SqQueue &Q, QElemType &e) if (Q.front=Q.rear) cerr“隊(duì)列已空無數(shù)據(jù)元素出棧！隊(duì)列已空無數(shù)據(jù)元素出棧！”next=NULL;鏈隊(duì)列實(shí)現(xiàn)鏈隊(duì)列實(shí)現(xiàn)-初始化初始化fro

37、ntreartypedef struct QueuePtr front; QueuePtr rear; LinkQueue; void DestroyQueue (LinkQueue &Q) while(Q.front) Q.rear=Q.front-next; delete Q.front; Q.front=Q.rear; 鏈隊(duì)列實(shí)現(xiàn)鏈隊(duì)列實(shí)現(xiàn)-銷毀銷毀fronta1a2a3 rear bool QueueEmpty(LinkQueue Q) return Q.front=Q.rear; 鏈隊(duì)列實(shí)現(xiàn)鏈隊(duì)列實(shí)現(xiàn)-判斷是否為空判斷是否為空QElemType GetHead (LinkQu

38、eue Q) if (Q.front!=Q.rear) return Q.front-next-data;鏈隊(duì)列實(shí)現(xiàn)鏈隊(duì)列實(shí)現(xiàn)-求隊(duì)頭元素求隊(duì)頭元素fronta1a2a3 rearvoid EnQueue(LinkQueue &Q, QElemType e) p= new QNode; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p;鏈隊(duì)列實(shí)現(xiàn)鏈隊(duì)列實(shí)現(xiàn)-入隊(duì)入隊(duì)fronta1a2a3 rearPevoid DeQueue (LinkQueue &Q, QElemType &e) if(Q.front=Q.rear) cer

39、r 隊(duì)列已空，無法刪除隊(duì)列已空，無法刪除! next; e=p-data; Q.front-next=p-next; if (Q.rear=p) Q.rear=Q.front; delete p;鏈隊(duì)列實(shí)現(xiàn)鏈隊(duì)列實(shí)現(xiàn)-出隊(duì)出隊(duì)fronta1a2a3 rearp1棧和隊(duì)列是一種特殊的線性表，其特殊性體現(xiàn)在棧和隊(duì)列是一種特殊的線性表，其特殊性體現(xiàn)在它們是它們是 的線性表。設(shè)現(xiàn)有元素的線性表。設(shè)現(xiàn)有元素e1,e2,e3,e4,e5和和e6依次進(jìn)棧，若出棧的序列是依次進(jìn)棧，若出棧的序列是e2,e4,e3,e6,e5,e1，則棧，則棧S的容量至少是的容量至少是 。 2順序循環(huán)隊(duì)列中，設(shè)隊(duì)頭指針為順序循環(huán)

40、隊(duì)列中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針，隊(duì)尾指針為為rear，隊(duì)中最多可有，隊(duì)中最多可有MAX個元素，采用少用一個個元素，采用少用一個存儲單元的方法區(qū)分隊(duì)滿與隊(duì)空問題，則元素入隊(duì)列存儲單元的方法區(qū)分隊(duì)滿與隊(duì)空問題，則元素入隊(duì)列時隊(duì)尾指針的變化為時隊(duì)尾指針的變化為 ；元素；元素出隊(duì)列時隊(duì)頭指針的變化為出隊(duì)列時隊(duì)頭指針的變化為 ；隊(duì)滿的判別條件為為隊(duì)滿的判別條件為為 ，隊(duì)，隊(duì)空的判別條件為空的判別條件為 。操作受限操作受限3rear=(rear+1)%MAXfront=(front+1)%MAX(rear+1)%MAX=frontrear=front練習(xí)練習(xí)-填空題填空題用一維數(shù)組用一維數(shù)組a7

41、 順序存儲一個循環(huán)隊(duì)列，隊(duì)首和隊(duì)尾順序存儲一個循環(huán)隊(duì)列，隊(duì)首和隊(duì)尾指針分別用指針分別用front和和rear表示，當(dāng)前隊(duì)列中已有表示，當(dāng)前隊(duì)列中已有5個元個元素：素：22，30，16，36，58，其中，其中22是隊(duì)首，是隊(duì)首， front值值為為5，請畫出對應(yīng)的存儲狀態(tài)圖，當(dāng)連續(xù)做兩次出隊(duì)，請畫出對應(yīng)的存儲狀態(tài)圖，當(dāng)連續(xù)做兩次出隊(duì)運(yùn)算后，再做兩次入隊(duì)運(yùn)算，讓元素運(yùn)算后，再做兩次入隊(duì)運(yùn)算，讓元素80，55依次進(jìn)隊(duì)，依次進(jìn)隊(duì)，請?jiān)佼嫵鰧?yīng)的存儲狀態(tài)圖。請?jiān)佼嫵鰧?yīng)的存儲狀態(tài)圖。0123456163658223001234561636588055初始狀態(tài)：初始狀態(tài)：front=5,rear=3操作后

42、：操作后：front=0,rear=5練習(xí)練習(xí)-解答解答題題【例例】編程判斷一個字符序列是否是回文。編程判斷一個字符序列是否是回文。如：如：“ABCDEDCBA” 是回文，是回文，“ABCDEDBAC”不不是回文。是回文。算法思想算法思想: 使用棧和隊(duì)列。使用棧和隊(duì)列。 把字符依次進(jìn)棧和進(jìn)隊(duì)列；把字符依次進(jìn)棧和進(jìn)隊(duì)列； 然后逐個出棧和出隊(duì)列，并比較每兩個是否相同；然后逐個出棧和出隊(duì)列，并比較每兩個是否相同； 若全部相同，則說明是回文。若全部相同，則說明是回文。 可以用順序結(jié)構(gòu)也可以用鏈結(jié)構(gòu)，這里用順序結(jié)構(gòu)?？梢杂庙樞蚪Y(jié)構(gòu)也可以用鏈結(jié)構(gòu)，這里用順序結(jié)構(gòu)。3.4 3.4 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用#in

43、clude #include typedef char ElemType;typedef struct ElemType *base; ElemType *top; int stacksize; SqStack；typedef struct ElemType *base; int front, rear; int queuesize; SqQueue;#include “SeqStack.h”#include “SeqQueue.h”void HuiWen(char str ) SqQueue myQueue; SqStack myStack; char x, y; int i, length; length = strlen(str); InitQueue (myQueue); InitStack (myStack); for ( i=0; ilength; i+ ) EnQueue ( myQueue, stri ); Push( myStack, stri ); w