第3章 棧和隊(duì)列

1、內(nèi)容回顧n線性表 n定義n表示/實(shí)現(xiàn)方式（2種）n操作（3個(gè)）n順序表和鏈表各自特點(diǎn)（優(yōu)缺點(diǎn)，2方面）n鏈表類型（3種）第三章第三章 棧和隊(duì)列棧和隊(duì)列n本章內(nèi)容本章內(nèi)容3.1 棧棧3.1.1 棧的定義及基本運(yùn)算棧的定義及基本運(yùn)算3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.1.3 棧的應(yīng)用棧的應(yīng)用3.2 隊(duì)列隊(duì)列3.2.1 隊(duì)列的定義及基本運(yùn)算隊(duì)列的定義及基本運(yùn)算3.2.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.2.3 隊(duì)列的應(yīng)用隊(duì)列的應(yīng)用3.1.1 棧的定義及基本運(yùn)算棧的定義及基本運(yùn)算n棧棧(Stack)的定義的定義 棧棧(Stack)是限制在表的一端是限制在表的一端進(jìn)行插入和刪

2、除運(yùn)算的線性表，進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為通常稱插入、刪除的這一端為棧頂棧頂(top),另一端為棧底另一端為棧底(bottom)。當(dāng)表中沒(méi)有元素。當(dāng)表中沒(méi)有元素時(shí)稱為空棧。時(shí)稱為空棧。anan-1 .a2a1棧底棧底棧頂棧頂入棧入棧出棧出棧棧的特點(diǎn)棧的特點(diǎn)棧的修改是按后進(jìn)先出的原棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為后進(jìn)先則進(jìn)行的。因此，棧稱為后進(jìn)先出表（出表（LIFO）。）。3.1.1 棧的定義及基本運(yùn)算棧的定義及基本運(yùn)算n棧的運(yùn)算演示棧的運(yùn)算演示(1)A、B、C、D四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出棧，得到一個(gè)輸出序列棧，得

3、到一個(gè)輸出序列DCBA。DCBAABCDDCBA 3.1.1 棧的定義及基本運(yùn)算棧的定義及基本運(yùn)算n棧的運(yùn)算演示棧的運(yùn)算演示(1)A、B、C、D四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出棧，得到一個(gè)輸出序列棧，得到一個(gè)輸出序列DCBA。(2)能否由入棧序列能否由入棧序列A、B、C、D、E得到出棧序列得到出棧序列CBDAE？ABCDE操作序列：操作序列：出棧序列：出棧序列： 元素元素A入棧入棧A A 元素元素B入棧入棧B B 元素元素C入棧入棧C C3.1.1 棧的定義及基本運(yùn)算棧的定義及基本運(yùn)算n棧的運(yùn)算演示棧的運(yùn)算演示(1)A、B、C、D四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出

4、四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出棧，得到一個(gè)輸出序列棧，得到一個(gè)輸出序列DCBA。(2)能否由入棧序列能否由入棧序列A、B、C、D、E得到出棧序列得到出棧序列CBDAE？ DE操作序列：操作序列：出棧序列：出棧序列： 元素元素A入棧入棧A 元素元素B入棧入棧B 元素元素C入棧入棧 元素元素C出棧出棧CC 元素元素B出棧出棧B3.1.1 棧的定義及基本運(yùn)算棧的定義及基本運(yùn)算n棧的運(yùn)算演示棧的運(yùn)算演示(1)A、B、C、D四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出棧，得到一個(gè)輸出序列棧，得到一個(gè)輸出序列DCBA。(2)能否由入棧序列能否由入棧序列A、B、C、D、E得到出棧序列得

5、到出棧序列CBDAE？ DE操作序列：操作序列：出棧序列：出棧序列： 元素元素A入棧入棧A 元素元素B入棧入棧 元素元素C入棧入棧 元素元素C出棧出棧C 元素元素B出棧出棧B 元素元素D入棧入棧D D 元素元素D出棧出棧D 元素元素A出棧出棧A3.1.1 棧的定義及基本運(yùn)算棧的定義及基本運(yùn)算n棧的運(yùn)算演示棧的運(yùn)算演示(1)A、B、C、D四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出棧，得到一個(gè)輸出序列棧，得到一個(gè)輸出序列DCBA。(2)能否由入棧序列能否由入棧序列A、B、C、D、E得到出棧序列得到出棧序列CBDAE？ E操作序列：操作序列：出棧序列：出棧序列： 元素元素A入棧

6、入棧 元素元素B入棧入棧 元素元素C入棧入棧 元素元素C出棧出棧C 元素元素B出棧出棧B 元素元素D入棧入棧 元素元素D出棧出棧D 元素元素A出棧出棧A 元素元素E入棧入棧EE 元素元素E出棧出棧En棧的基本運(yùn)算棧的基本運(yùn)算InitStack(&S): InitStack(&S): 初始化棧初始化棧S SStackEmpty(): StackEmpty(): 判斷棧是否為空判斷棧是否為空Push(e): Push(e): 將元素將元素e e放入棧頂放入棧頂Pop(e): Pop(e): 移走棧頂?shù)脑?，同時(shí)由移走棧頂?shù)脑?，同時(shí)由e e帶回該元帶回該元素的值素的值Gettop(

7、): Gettop(): 獲取棧頂?shù)脑兀粡臈Ｖ幸谱攉@取棧頂?shù)脑?，但不從棧中移?.1.1 棧的定義及基本運(yùn)算棧的定義及基本運(yùn)算3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)anan-1 .a2a1棧棧basetop3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)n順序棧的類型定義順序棧的類型定義/ -棧的順序存儲(chǔ)表示棧的順序存儲(chǔ)表示-# define STACK_INIT_SIZE 100;# define STACKINCREMENT 10;typedef struct ElemType *base; /棧底指針，棧構(gòu)造前和銷毀后為空

8、棧底指針，棧構(gòu)造前和銷毀后為空 ElemType *top; /棧頂指針，指向棧頂元素的下一位置棧頂指針，指向棧頂元素的下一位置 int stacksize; /當(dāng)前分配的棧的存儲(chǔ)空間數(shù)當(dāng)前分配的棧的存儲(chǔ)空間數(shù)SqStack; 2.2 線性表的順序表示和實(shí)現(xiàn)線性表的順序表示和實(shí)現(xiàn)(對(duì)應(yīng)對(duì)應(yīng))n順序表存儲(chǔ)的語(yǔ)言實(shí)現(xiàn)順序表存儲(chǔ)的語(yǔ)言實(shí)現(xiàn)由于由于C C語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類型來(lái)描述順序表。下面我們用示，故可以用數(shù)組類型來(lái)描述順序表。下面我們用結(jié)構(gòu)類型來(lái)定義順序表類型。結(jié)構(gòu)類型來(lái)定義順序表類型。/-/-動(dòng)態(tài)分配動(dòng)態(tài)分配-#defineLI

9、ST_INIT_SIZE100 /空間初始分配量空間初始分配量#defineLISTINCREMENT10 /空間分配增量空間分配增量typedefstruct ElemType*elem;/存儲(chǔ)空間基址存儲(chǔ)空間基址intlength;/當(dāng)前長(zhǎng)度當(dāng)前長(zhǎng)度intlistsize;/當(dāng)前分配的存儲(chǔ)容量當(dāng)前分配的存儲(chǔ)容量 SqList；3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)(2)判斷?？张袛鄺？読nt StackEmpty(SqStack *S) return(S.base=S.top);(3)判斷棧滿判斷棧滿int StackFull(Sq

10、Stack *S) return(S.top-S.base=S.stacksize);3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)Status Push(SqStack &S, ElemType e)/插入元素插入元素e為新的棧頂元素為新的棧頂元素if (S.top S.base = S.stacksize) return ERROR; /棧滿棧滿*S.top = e;S.top+;return OK;/Push3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)n鏈棧鏈棧anan-1 .a

11、2a1棧棧棧底棧底棧頂棧頂S棧的鏈?zhǔn)酱鎯?chǔ)棧的鏈?zhǔn)酱鎯?chǔ)an an-1 a1a2 思考思考 鏈棧是否需要另外設(shè)置頭指針？鏈棧是否需要另外設(shè)置頭指針？ 建立鏈棧適合用哪種插入法？建立鏈棧適合用哪種插入法？ 鏈棧的基本操作的實(shí)現(xiàn)。鏈棧的基本操作的實(shí)現(xiàn)。 鏈棧的基本操作鏈棧的基本操作 置空棧置空棧void InitStack(SqStack *p) ptop=NULL; 判斷棧空判斷?？読nt StackEmpty(linkstack *p) return ptop=NULL;3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧

12、的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)被除數(shù)被除數(shù)除數(shù)除數(shù)商商余數(shù)余數(shù)432211212101102505221221012010 輸出輸出void conversion( ) InitStack(S); /構(gòu)造空棧構(gòu)造空棧scanf (“%d”,&n);while(n)Push(S,n%2);n=n/2; while(! StackEmpty(S)Pop(S,e);printf(“%d”,e); n括號(hào)匹配括號(hào)匹配設(shè)一個(gè)表達(dá)式中可以包含三種括號(hào)：設(shè)一個(gè)表達(dá)式中可以包含三種括號(hào)：“(”和和“)”、“”和和“”、“”和和“”，并且這三種括號(hào)可以按照任意，并且這三

13、種括號(hào)可以按照任意的次序的次序嵌套嵌套使用，考查表達(dá)式中的括號(hào)是否匹配。例如：使用，考查表達(dá)式中的括號(hào)是否匹配。例如： .(.).).n例：例：a=b+(c-d)*(e-f);while (m(a8+t) m=m+1; t=t-1;n實(shí)現(xiàn)方法利用棧進(jìn)行表達(dá)式中的括號(hào)匹配實(shí)現(xiàn)方法利用棧進(jìn)行表達(dá)式中的括號(hào)匹配自左至右掃描表達(dá)式，若遇左括號(hào)，則將左括號(hào)入自左至右掃描表達(dá)式，若遇左括號(hào)，則將左括號(hào)入棧，若遇右括號(hào)，則將其與棧頂?shù)淖罄ㄌ?hào)進(jìn)行匹配，若棧，若遇右括號(hào)，則將其與棧頂?shù)淖罄ㄌ?hào)進(jìn)行匹配，若配對(duì)，則棧頂?shù)淖罄ㄌ?hào)出棧，否則出現(xiàn)括號(hào)不匹配錯(cuò)誤。配對(duì)，則棧頂?shù)淖罄ㄌ?hào)出棧，否則出現(xiàn)括號(hào)不匹配錯(cuò)誤。思考：匹配

14、的充要條件？思考：匹配的充要條件？n迷宮問(wèn)題迷宮問(wèn)題尋找一條從入口到出口的通路。尋找一條從入口到出口的通路。81 2 3 4 5 6 781234567入口入口出口出口前進(jìn)方向：前進(jìn)方向： 上上(北北)、下、下(南南)、左、左(西西)、右、右(東東)東東南南北北西西n 走步規(guī)則：走步規(guī)則：首先從向下開(kāi)始，按首先從向下開(kāi)始，按照逆時(shí)針?lè)较蛩阉飨乱徊秸漳鏁r(shí)針?lè)较蛩阉飨乱徊娇赡芮斑M(jìn)的位置可能前進(jìn)的位置棧棧n迷宮問(wèn)題迷宮問(wèn)題81 2 3 4 5 6 781234567(1,1)(1,1)i(2,1)(2,1)i(3,1)(3,1)i(4,1)(4,1)i(5,1)(5,1)i(6,1)(6,1)(7,

15、1)(7,1)i棧棧n迷宮問(wèn)題迷宮問(wèn)題81 2 3 4 5 6 781234567(1,1)(1,1)i(2,1)(2,1)i(3,1)(3,1)i(4,1)(4,1)i(5,1)(5,1)i(6,1)(6,1)(7,1)(7,1)i (5,2)(5,2)i(5,3)(5,3)i(6,3)(6,3)i(6,4)(6,4)i(8,8)(8,8)iiiiiin迷宮問(wèn)題迷宮問(wèn)題n迷宮的表示迷宮的表示const int N=8;struct PosType int x, y;char mazeNN; /位置上的標(biāo)識(shí)，是否可通過(guò)位置上的標(biāo)識(shí)，是否可通過(guò)n迷宮初始化迷宮初始化用二層嵌套循環(huán)對(duì)迷宮賦值用二層

16、嵌套循環(huán)對(duì)迷宮賦值n迷宮求解迷宮求解(見(jiàn)教材算法見(jiàn)教材算法)n輸出棧中的路徑輸出棧中的路徑Status MazePath(maze, start, end) /若迷宮中存在一條從入口若迷宮中存在一條從入口start到出口到出口end的通道，則求出這樣的一條通路的通道，則求出這樣的一條通路 InitStack(S); curpos = start; curstep = 1; do if (pass(curpos) /當(dāng)前位置可以通過(guò)當(dāng)前位置可以通過(guò) Mark(maze,curpos); /留下記號(hào)留下記號(hào) e = (curstep,curpos,1); push(S,e); /加入路徑加入路徑

17、if (curpos=end) return true; /到達(dá)出口到達(dá)出口 curpos = NextPos(curpos,1) ;/下一個(gè)位置下一個(gè)位置 curstep+; else /當(dāng)前位置不能通過(guò)當(dāng)前位置不能通過(guò) if (!StackEmpty(S) pop(S,e); /退回一步退回一步 while(e.di=4 & ! !StackEmpty(S) /當(dāng)前位置是死胡同當(dāng)前位置是死胡同 Markdead(maze,e.seat)；pop(S,e); /留下記號(hào)，沿來(lái)路返回留下記號(hào)，沿來(lái)路返回 if (e.di4) /當(dāng)前位置還有其他方向沒(méi)有探索，繼續(xù)試探當(dāng)前位置還有其他方向

18、沒(méi)有探索，繼續(xù)試探 e.di+; push(S,e); curpos =NextPos(e.seat, e.di); while (!StackEmpty(S); return false; 表達(dá)式求值表達(dá)式求值算符優(yōu)先法算符優(yōu)先法 4+23-10/5 先乘除先乘除,后加減后加減; 從左算到右從左算到右 先括號(hào)內(nèi)先括號(hào)內(nèi),后括號(hào)外后括號(hào)外 4+23-10/5=4+6-10/5=10-10/5=10-2=8 表達(dá)式由表達(dá)式由操作數(shù)操作數(shù)(operand)、運(yùn)算符運(yùn)算符(operator)和和界限符界限符(delimiter)組成的。組成的。 將運(yùn)算符和界限符統(tǒng)稱為將運(yùn)算符和界限符統(tǒng)稱為算符算符。

19、它們構(gòu)成的集合命名為。它們構(gòu)成的集合命名為OP OperandType EvaluateExpression() InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c = getchar(); while(c != #|GetTop(OPTR)!=#) if(!In(c,OP運(yùn)算符運(yùn)算符) Push(OPND,c); c=getchar(); else /不是運(yùn)算符則進(jìn)棧不是運(yùn)算符則進(jìn)棧 switch(Precede(GetTop(OPTR),c) case : /退棧并將運(yùn)算結(jié)果入棧退棧并將運(yùn)算結(jié)果入棧 Pop(OPTR,theta); Pop(

20、OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; /switch/while return GetTop(OPND);/EvaluateExpression3.3 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn)n棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn)用棧結(jié)構(gòu)實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言中函數(shù)的嵌套調(diào)用和遞歸用棧結(jié)構(gòu)實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言中函數(shù)的嵌套調(diào)用和遞歸調(diào)用調(diào)用例：例： long f(int n) if (n1) return n*f(n-1); else return 1; void main( ) int n=4; printf(“%ld”,f(n); 棧與遞歸3

21、.3 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn)棧與遞歸3.3 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn) n階階Hanoi塔問(wèn)題塔問(wèn)題Base case: n = 1 X Z棧與遞歸3.3 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn) n階階Hanoi塔問(wèn)題塔問(wèn)題Base case: n = 1 X Z棧與遞歸3.3 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn) n階階Hanoi塔問(wèn)題塔問(wèn)題Recursion: n 1 前前n-1 個(gè)盤個(gè)盤: X Y棧與遞歸3.3 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn) n階階Hanoi塔問(wèn)題塔問(wèn)題Recursion: n 1 前前n-1 個(gè)盤個(gè)盤: X Y棧與遞歸3.3 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn) n階階Hanoi塔問(wèn)題塔

22、問(wèn)題Recursion: n 1 最大盤最大盤: X Z棧與遞歸3.3 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn) n階階Hanoi塔問(wèn)題塔問(wèn)題Recursion: n 1 最大盤最大盤: X Z棧與遞歸3.3 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn) n階階Hanoi塔問(wèn)題塔問(wèn)題Recursion: n 1 前前n-1個(gè)盤個(gè)盤: Y Z棧與遞歸3.3 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn) n階階Hanoi塔問(wèn)題塔問(wèn)題Recursion: n 1 前前n-1個(gè)盤個(gè)盤: Y Z棧與遞歸3.4.1 隊(duì)列的定義及基本運(yùn)算隊(duì)列的定義及基本運(yùn)算n隊(duì)列隊(duì)列(Queue)的定義的定義隊(duì)列是僅限定在隊(duì)列是僅限定在表尾進(jìn)行插入表尾進(jìn)行插入和和表

23、頭進(jìn)行刪除操作表頭進(jìn)行刪除操作的線性表。的線性表。n術(shù)語(yǔ)術(shù)語(yǔ)隊(duì)頭隊(duì)頭(front)隊(duì)列的表頭，即只允許刪除的一端。隊(duì)列的表頭，即只允許刪除的一端。隊(duì)尾隊(duì)尾(rear) 隊(duì)列的表尾隊(duì)列的表尾，即只允許插入的一端。即只允許插入的一端。入隊(duì)入隊(duì)(EnQueue) 向隊(duì)尾插入元素。向隊(duì)尾插入元素。出隊(duì)出隊(duì)(DeQueue) 從隊(duì)頭刪除元素。從隊(duì)頭刪除元素。隊(duì)列的特點(diǎn)隊(duì)列的特點(diǎn)隊(duì)列的修改是按隊(duì)列的修改是按先進(jìn)先出先進(jìn)先出的原則進(jìn)行的。因此，隊(duì)的原則進(jìn)行的。因此，隊(duì)列稱為先進(jìn)先出表（列稱為先進(jìn)先出表（FIFO）。）。a1 a2 ai an隊(duì)頭隊(duì)頭front隊(duì)尾隊(duì)尾rear出隊(duì)出隊(duì)入隊(duì)入隊(duì)3.4.1 隊(duì)列的

24、定義及基本運(yùn)算隊(duì)列的定義及基本運(yùn)算n隊(duì)列的基本運(yùn)算隊(duì)列的基本運(yùn)算InitQueue(&Q): 初始化隊(duì)列初始化隊(duì)列QQueueEmpty(): 判斷隊(duì)列是否為空判斷隊(duì)列是否為空EnQueue(e): 將元素將元素e放入隊(duì)尾放入隊(duì)尾DeQueue(e): 移走隊(duì)頭元素，由移走隊(duì)頭元素，由e帶回該元帶回該元素的值素的值GetFront(): 獲取隊(duì)頭元素的值，但不從隊(duì)列獲取隊(duì)頭元素的值，但不從隊(duì)列中移走該元素中移走該元素Length(): 計(jì)算并返回隊(duì)列中元素的個(gè)數(shù)計(jì)算并返回隊(duì)列中元素的個(gè)數(shù)3.4.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)n鏈隊(duì)列鏈隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)

25、構(gòu) 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)a1 a2 anai Q.frontQ.reara1 a2 ai an隊(duì)頭隊(duì)頭front隊(duì)尾隊(duì)尾rear出隊(duì)出隊(duì)入隊(duì)入隊(duì)3.4.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)n鏈隊(duì)列的鏈隊(duì)列的C語(yǔ)言實(shí)現(xiàn)語(yǔ)言實(shí)現(xiàn) /-單鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)單鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)-typedef struct QNode /鏈表結(jié)點(diǎn)類型鏈表結(jié)點(diǎn)類型 QElemType data; struct QNode *next;QNode,*QueuePtr; typedef struct /隊(duì)列類型隊(duì)列類型 QueuePtr front; /隊(duì)頭指針隊(duì)頭指針 QueuePtr rear; /隊(duì)尾指針

26、隊(duì)尾指針LinkQueue;data Q.frontQ.rearStatus InitQueue(LinkQueue &Q) /構(gòu)造一個(gè)空隊(duì)列構(gòu)造一個(gè)空隊(duì)列QQ.front= Q.rear = (QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next = NULL;return OK;(2) 入隊(duì)入隊(duì)Status EnQueue(LinkQueue &Q, QElemType e)/將元素將元素e插入到隊(duì)列插入到隊(duì)列Q中中p = (QueuePtr)malloc(sizeof(QNode);i

27、f (!p) exit(OVERFLOW);p-data = e;p-next=NULL;Q.rear-next = p; Q.rear = p;return OK;3.4.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)n鏈隊(duì)列基本操作的實(shí)現(xiàn)鏈隊(duì)列基本操作的實(shí)現(xiàn)(1) 初始化初始化 Q.frontQ.rearStatus DeQueue(LinkQueue &Q, QElemType &e)/若隊(duì)列不空，則隊(duì)頭元素出隊(duì)列，用若隊(duì)列不空，則隊(duì)頭元素出隊(duì)列，用e返回其值，返回返回其值，返回OK /否則返回否則返回ERROR if (Q.rear = Q.front) return E

28、RROR; p = Q.front - next; e = p - data; Q.front-next = p - next; if (Q.rear = p) Q.rear = Q.front; free(p); return OK;3.4.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)n鏈隊(duì)列基本操作的實(shí)現(xiàn)鏈隊(duì)列基本操作的實(shí)現(xiàn)(1) 初始化初始化 (2) 入隊(duì)列入隊(duì)列 (3) 出隊(duì)列出隊(duì)列 Q.frontQ.rear思考：思考：如果不設(shè)置頭結(jié)點(diǎn)，如果不設(shè)置頭結(jié)點(diǎn)，需要考慮那些特殊情需要考慮那些特殊情況？況？3.4.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)n循環(huán)隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)循環(huán)隊(duì)

29、列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)a1 a2 ai an隊(duì)頭隊(duì)頭front隊(duì)尾隊(duì)尾rear出隊(duì)出隊(duì)入隊(duì)入隊(duì)6F36an6F26ai . .6F02a26F00a1Q.frontQ.reara1a2a3Q.frontanQ.rear012nn+1m-1循環(huán)隊(duì)列循環(huán)隊(duì)列n循環(huán)隊(duì)列的循環(huán)隊(duì)列的C語(yǔ)言實(shí)現(xiàn)語(yǔ)言實(shí)現(xiàn)/-循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)-#define MAXSIZE 100typedef struct QElemType *base; int front; int rear; SqQueue;3.4.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)n循環(huán)隊(duì)列基本操作的實(shí)現(xiàn)循環(huán)隊(duì)列基本操作的實(shí)現(xiàn)(1) 初始化初始化Status InitQueue(SqQueue &Q)Q.base=(QEl