1、 通常稱，棧和隊(duì)列是限定插入和刪除只通常稱，棧和隊(duì)列是限定插入和刪除只能在表的能在表的“端點(diǎn)進(jìn)展的線性表。端點(diǎn)進(jìn)展的線性表。 線性表線性表 棧棧 隊(duì)列隊(duì)列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) Delete(L, i) Delete(S, n) Delete(Q, 1) 1in 1in棧和隊(duì)列是兩種常用的數(shù)據(jù)類型棧和隊(duì)列是兩種常用

2、的數(shù)據(jù)類型學(xué)習(xí)提要：學(xué)習(xí)提要：1.1.掌握棧和隊(duì)列這兩種籠統(tǒng)數(shù)據(jù)類型的特點(diǎn)，掌握棧和隊(duì)列這兩種籠統(tǒng)數(shù)據(jù)類型的特點(diǎn)， 并能在相應(yīng)的運(yùn)用問題中正確選用它們。并能在相應(yīng)的運(yùn)用問題中正確選用它們。2.2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法，特別應(yīng)熟練掌握棧類型的兩種實(shí)現(xiàn)方法，特別應(yīng) 留意棧滿和棧空的條件以及它們的描畫方法。留意棧滿和棧空的條件以及它們的描畫方法。3.3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的根本操作實(shí)現(xiàn)熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的根本操作實(shí)現(xiàn) 算法，特別留意隊(duì)滿和隊(duì)空的描畫方法。算法，特別留意隊(duì)滿和隊(duì)空的描畫方法。4.4.了解遞歸算法執(zhí)行過程中棧的形狀變化過程。了解遞歸算法執(zhí)行過程中棧的形狀變化過程。重難

3、點(diǎn)內(nèi)容：重難點(diǎn)內(nèi)容： 順序棧的相關(guān)操作、循環(huán)隊(duì)列的判空判滿順序棧的相關(guān)操作、循環(huán)隊(duì)列的判空判滿 棧的定義：限定僅在表尾進(jìn)展插入或刪棧的定義：限定僅在表尾進(jìn)展插入或刪除操作的線性表。不含元素的空表稱空除操作的線性表。不含元素的空表稱空棧。棧。ana1a2.棧底棧頂.出棧進(jìn)棧棧s=(a1,a2,an)特點(diǎn)：后進(jìn)先出特點(diǎn)：后進(jìn)先出LIFO表尾表尾棧頂棧頂 表頭表頭棧底棧底 ADT Stack 數(shù)據(jù)對象：數(shù)據(jù)對象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 商定商定an 端為棧頂，端為棧頂，a1 端為棧底。端

4、為棧底。 根本操作：根本操作： ADT Stack棧的籠統(tǒng)數(shù)據(jù)類型定義：棧的籠統(tǒng)數(shù)據(jù)類型定義：InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit( )一、順序棧一、順序棧/- 棧的順序存儲(chǔ)表示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct S

5、ElemType *base; /棧底指針 SElemType *top; /棧頂指針 int stacksize; SqStack;實(shí)現(xiàn)：一維數(shù)組實(shí)現(xiàn)：一維數(shù)組sMtop123450進(jìn)棧進(jìn)棧Push(&S, e)A棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=base,?？?，此時(shí)出棧，那么下溢underflow)top=M,棧滿，此時(shí)入棧，那么上溢overflow)toptoptoptoptop123450空棧空棧topbasebasetoptop出棧出棧Pop(&S,&e)123450ABCDEFtoptoptoptop?？誦asetoptop棧底指針base,一直指向棧底位

6、置；棧頂指針top,其初值指向棧底，一直在棧頂元素的下一個(gè)位置 Status InitStack (SqStack &S) / 構(gòu)造一個(gè)空棧S S.base=(SElemType*)malloc(STACK_INIT_SIZE* sizeof(SElemType); if (!S.base) exit (OVERFLOW); /存儲(chǔ)分配失敗 S = S.base; S.stacksize = STACK_INIT_SIZE; return OK; Status Push (SqStack &S, SElemType e) if (S - S.base = S.stacksize

7、) /棧滿，追加存儲(chǔ)空間棧滿，追加存儲(chǔ)空間 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType); if (!S.base) exit (OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 S = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S + + = e; return OK; Status Pop (SqStack &S, SElemType &e) / 假設(shè)棧不空，那么刪除假設(shè)

8、棧不空，那么刪除S的棧頂元素，的棧頂元素， / 用用e前往其值，并前往前往其值，并前往OK； / 否那么前往否那么前往ERROR if ( S = S.base ) return ERROR; e = *- -S; return OK;0M-1棧棧1底底棧棧1頂頂棧棧2底底棧棧2頂頂在一個(gè)程序中同時(shí)運(yùn)用兩個(gè)棧在一個(gè)程序中同時(shí)運(yùn)用兩個(gè)棧二、鏈棧二、鏈棧 棧的鏈?zhǔn)酱鎯?chǔ)構(gòu)造。棧的鏈?zhǔn)酱鎯?chǔ)構(gòu)造。 棧頂指針就是鏈表的頭指針棧頂指針就是鏈表的頭指針。留意留意: 鏈棧中鏈棧中指針的方向指針的方向棧頂指針棧頂指針a1anan-1v入棧操作入棧操作push(&S, e)v 出棧操作出棧操作pop(&am

9、p;S,&e) .棧底toptopxptop .棧底topqp-next=top ; top=p q=top ; top=top-next 3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換十進(jìn)制十進(jìn)制N和其他和其他d進(jìn)制數(shù)的轉(zhuǎn)換原理進(jìn)制數(shù)的轉(zhuǎn)換原理: N=( N div d )*d + N mod d 其中：其中：div為整除運(yùn)算，為整除運(yùn)算， mod為求余運(yùn)算為求余運(yùn)算toptop4top40top405 例如：例如： (1348)10=(2504)8，其運(yùn)算過程如下：，其運(yùn)算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計(jì)算順序輸出順序

10、top4052 void conversion( ) /對于輸入的恣意一個(gè)非負(fù)十進(jìn)制整數(shù)， /打印輸出與其等值的八進(jìn)制數(shù) initstack ( S ); scanf (“%d,N); while ( N ) push (S，N%8); N = N / 8; while ( ! Stackempty(s) ) pop ( S,e ); printf ( “%d, e ); /conversion3.3.2 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn) 那么那么 檢驗(yàn)括號(hào)能否匹配的方法可用檢驗(yàn)括號(hào)能否匹配的方法可用“等待的急迫程度這個(gè)概念來描畫。等待的急迫程度這個(gè)概念來描畫。假設(shè)在表達(dá)式中假設(shè)在表達(dá)式中或或 等

11、為正確的格式，等為正確的格式， 或或 或或 )均均為不正確的格式。為不正確的格式。分析能夠出現(xiàn)的不匹配的情況分析能夠出現(xiàn)的不匹配的情況: :到來的右括弧并非是所到來的右括弧并非是所“等待的；等待的；例如：思索以下括號(hào)序列：例如：思索以下括號(hào)序列： ( ) 1 2 3 4 5 6 7 8到來的是到來的是“不速之客；不速之客；直到終了，也沒有到來所直到終了，也沒有到來所“等等待的括弧。待的括弧。算法的設(shè)計(jì)思想：算法的設(shè)計(jì)思想：1凡出現(xiàn)左括弧，那么進(jìn)棧；凡出現(xiàn)左括弧，那么進(jìn)棧；2凡出現(xiàn)右括弧，首先檢查棧能否空凡出現(xiàn)右括弧，首先檢查棧能否空 假設(shè)?？眨敲搓U明該假設(shè)棧空，那么闡明該“右括弧多余，右括弧

12、多余， 否那么和棧頂元素比較，否那么和棧頂元素比較， 假設(shè)相匹配，那么假設(shè)相匹配，那么“左括弧出棧左括弧出棧 ， 否那么闡明不匹配。否那么闡明不匹配。3表達(dá)式檢驗(yàn)終了時(shí)，表達(dá)式檢驗(yàn)終了時(shí)， 假設(shè)棧空，那么闡明表達(dá)式中匹配正確，假設(shè)?？眨敲搓U明表達(dá)式中匹配正確， 否那么闡明否那么闡明“左括弧有余。左括弧有余。3.2.3 行編輯程序問題行編輯程序問題如何實(shí)現(xiàn)？如何實(shí)現(xiàn)？“每接受一個(gè)字符即存入存儲(chǔ)器每接受一個(gè)字符即存入存儲(chǔ)器 ? 不不恰恰當(dāng)當(dāng)!合理的作法是：合理的作法是： 設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶輸入的一行字符，然后逐行存入用戶

13、數(shù)據(jù)區(qū)，并假設(shè)戶數(shù)據(jù)區(qū)，并假設(shè)“#為退格符，為退格符，“為退行符。為退行符。假設(shè)從終端接受了這樣兩行字符：假設(shè)從終端接受了這樣兩行字符： whli#ilr#es#*s) outchaputchar(*s=#+);那么實(shí)踐有效的是以下兩行：那么實(shí)踐有效的是以下兩行： while (*s) putchar(*s+); while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置S為空棧 default : Push(S, ch); break; ch =

14、 getchar(); / 從終端接納下一個(gè)字符 ClearStack(S); / 重置S為空棧if (ch != EOF) ch = getchar();while (ch != EOF) /EOF為全文終了符為全文終了符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；3.2.4 迷宮求解迷宮求解通常用的是通常用的是“窮舉求解的方法。窮舉求解的方法。求迷宮途徑算法的根本思想是：求迷宮途徑算法的根本思想是：v假設(shè)當(dāng)前位置假設(shè)當(dāng)前位置“可通，那么納可通，那么納入途徑，入途徑， 繼續(xù)前進(jìn)繼續(xù)前進(jìn);v假設(shè)當(dāng)前位置假設(shè)當(dāng)前位置“不可通，那不可通，那么后退，換方向繼續(xù)探求么后退，換方向繼續(xù)探求;v假設(shè)周圍假

15、設(shè)周圍“均無通路，那么均無通路，那么將當(dāng)前位置從途徑中刪除出將當(dāng)前位置從途徑中刪除出去。去。設(shè)定當(dāng)前位置的初值為入口位置； do 假設(shè)當(dāng)前位置可通， 那么將當(dāng)前位置插入棧頂； 假設(shè)該位置是出口位置，那么算法終了； 否那么切換當(dāng)前位置的東鄰方塊為 新的當(dāng)前位置； 否那么 while (棧不空；求迷宮中一條從入口到出口的途徑的算法：求迷宮中一條從入口到出口的途徑的算法： 假設(shè)棧不空且棧頂位置尚有其他方向未被探求，假設(shè)棧不空且棧頂位置尚有其他方向未被探求，那么設(shè)定新的當(dāng)前位置為那么設(shè)定新的當(dāng)前位置為: 沿順時(shí)針方向旋轉(zhuǎn)沿順時(shí)針方向旋轉(zhuǎn) 找到的棧頂位置的下一相鄰塊；找到的棧頂位置的下一相鄰塊；假設(shè)棧不

16、空但棧頂位置的周圍均不可通，假設(shè)棧不空但棧頂位置的周圍均不可通，那么刪去棧頂位置；那么刪去棧頂位置；/ 從途徑中刪去該通道塊從途徑中刪去該通道塊 假設(shè)棧不空，那么重新測試新的棧頂位置，假設(shè)棧不空，那么重新測試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至?？眨恢敝琳业揭粋€(gè)可通的相鄰塊或出棧至棧空；假設(shè)?？?，那么闡明迷宮沒有通路。假設(shè)?？眨敲搓U明迷宮沒有通路。 typedef struct int ord; / 通道塊在途徑上的“序號(hào) PosType seat; / 通道塊在迷宮中 的 “坐標(biāo)位置 int di; / 從此通道塊走向下一 通道塊的“方向 SElemType; / 棧的元素類型

17、 Status MazePath ( MazeType maze, PosType start, PosType end ) InitStack(S); curpos = start; / 設(shè)定設(shè)定“當(dāng)前位置為當(dāng)前位置為“入口位置入口位置 curstep = 1; / 探求第一步探求第一步 do if (Pass (curpos) / 當(dāng)前位置可以經(jīng)過，即是未當(dāng)前位置可以經(jīng)過，即是未曾走到過的通道塊曾走到過的通道塊 else while ( !StackEmpty(S) ); return (FALSE);/ MazePath FootPrint (curpos); e = ( curstep

18、, curpos, 1 );Push (S,e); / 參與途徑if ( curpos = end ) return (TRUE); / 到達(dá)終點(diǎn)curpos = NextPos ( curpos, 1 ); / 下一位置是當(dāng)前位置的東鄰curstep+; else / 當(dāng)前位置不能經(jīng)過當(dāng)前位置不能經(jīng)過 if (!StackEmpty(S) Pop (S,e); while (e.di=4 & !StackEmpty(S) MarkPrint (e.seat); Pop (S,e); / 留下不能經(jīng)過的標(biāo)志，并退回一留下不能經(jīng)過的標(biāo)志，并退回一步步 / while if (e.di4)

19、 e.di+; Push ( S, e); / 換下一個(gè)方向換下一個(gè)方向探求探求 curpos = NextPos (curpos, e.di ); / 設(shè)定當(dāng)前位置是該新方向上的設(shè)定當(dāng)前位置是該新方向上的相鄰塊相鄰塊 / if / if / else 限于二元運(yùn)算符的表達(dá)式定義: Exp = S1 OP S2 操作數(shù) : 變量、常量、表達(dá)式 運(yùn)算符 : 算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、 邏輯運(yùn)算符 界限符：括號(hào)、終了符3.2.5 表達(dá)式求值表達(dá)式求值表達(dá)式求值的算法：表達(dá)式求值的算法：算符優(yōu)先法根據(jù)運(yùn)算算符優(yōu)先法根據(jù)運(yùn)算優(yōu)先關(guān)系的規(guī)定來實(shí)優(yōu)先關(guān)系的規(guī)定來實(shí)現(xiàn)對表達(dá)式的編譯或現(xiàn)對表達(dá)式的編譯或解釋執(zhí)行

20、。解釋執(zhí)行。例：例：3 * ( 7 2 )OPND棧棧OPTR棧棧CCC3*(C7CC2C275C*5315例：例：3 * ( 7 2 ) OPTR棧棧 OPND棧棧 輸入輸入 操作操作1 # 3 * ( 7 2 ) # PUSH( OPND, 3 )2 # 3 * ( 7 2 ) # PUSH( OPTR, * )3 # * 3 ( 7 2 ) # PUSH( OPTR, ( )4 # * ( 3 7 2 ) # PUSH( OPND, 7 ) 5 # * ( 3 7 2 ) # PUSH( OPTR, )6 # * ( 3 7 2 ) # PHSH( OPND, 2 ) 7 # * ( 3

21、 7 2 ) # operate( 7,-,2 )8 # * ( 3 5 ) # POP( OPTR )9 # * 3 5 # operate( 3, *, 5 )10 # 15 # return GetTop( OPND )OperandType EvaluateExpression( ) / 設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合。 InitStack (OPTR); Push (OPTR, #); initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if (!In(c, OP) Pus

22、h(OPND, c); c = getchar(); / 不是運(yùn)算符那么進(jìn)棧 else / while return GetTop(OPND); / EvaluateExpression switch ( precede(GetTop(OPTR), c) case : / 退棧并將運(yùn)算結(jié)果入棧退棧并將運(yùn)算結(jié)果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switchr主程序主程序srrrs子過程子過程1rst子過程子過程2rst子過程子過程3 當(dāng)在一個(gè)函數(shù)的運(yùn)

23、轉(zhuǎn)期間調(diào)用另一個(gè)函當(dāng)在一個(gè)函數(shù)的運(yùn)轉(zhuǎn)期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)轉(zhuǎn)該被調(diào)用函數(shù)之前，需先完數(shù)時(shí)，在運(yùn)轉(zhuǎn)該被調(diào)用函數(shù)之前，需先完成三件事成三件事: : (1) (1)將一切的真實(shí)參數(shù)、前往地址等信息將一切的真實(shí)參數(shù)、前往地址等信息傳送給被調(diào)用函數(shù)保管傳送給被調(diào)用函數(shù)保管; ; (2) (2)為被調(diào)用函數(shù)的部分變量分配存儲(chǔ)區(qū)為被調(diào)用函數(shù)的部分變量分配存儲(chǔ)區(qū); ; (3) (3)將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。 從被調(diào)用函數(shù)前往調(diào)用函數(shù)之前，從被調(diào)用函數(shù)前往調(diào)用函數(shù)之前，應(yīng)該完成應(yīng)該完成: : (1) (1)保管被調(diào)函數(shù)的計(jì)算結(jié)果保管被調(diào)函數(shù)的計(jì)算結(jié)果; ; (2) (2)

24、釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū); ; (3) (3)按照被調(diào)函數(shù)保管的前往地址按照被調(diào)函數(shù)保管的前往地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。將控制轉(zhuǎn)移到調(diào)用函數(shù)。多個(gè)函數(shù)嵌套調(diào)用的規(guī)那么是：后調(diào)用先前多個(gè)函數(shù)嵌套調(diào)用的規(guī)那么是：后調(diào)用先前往往此時(shí)的內(nèi)存管理實(shí)行此時(shí)的內(nèi)存管理實(shí)行“棧式管理。棧式管理。遞歸過程指向過程中占用的數(shù)據(jù)區(qū)，遞歸過程指向過程中占用的數(shù)據(jù)區(qū)，稱之為遞歸任務(wù)棧稱之為遞歸任務(wù)棧每一層的遞歸參數(shù)合成一個(gè)記錄，每一層的遞歸參數(shù)合成一個(gè)記錄，稱之為遞歸任務(wù)記錄稱之為遞歸任務(wù)記錄棧頂記錄指示當(dāng)前層的執(zhí)行情況，棧頂記錄指示當(dāng)前層的執(zhí)行情況，稱之為當(dāng)前活動(dòng)記錄稱之為當(dāng)前活動(dòng)記錄棧頂指針，棧頂指

25、針， 稱之為當(dāng)前環(huán)境指針稱之為當(dāng)前環(huán)境指針例：遞歸的執(zhí)行情況分析 void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i1時(shí)，先把上面時(shí)，先把上面n-1個(gè)圓盤從個(gè)圓盤從X移到移到Y(jié)，然后將然后將n號(hào)盤從號(hào)盤從X移到移到Z，再將，再將n-1個(gè)盤從個(gè)盤從Y移到移到Z。即把求解。即把求解n個(gè)圓盤的個(gè)圓盤的Hanoi問題轉(zhuǎn)問題轉(zhuǎn)化為求解化為求解n-1個(gè)圓盤的個(gè)圓盤的Hanoi問題，依次類問題，依次類推，直至轉(zhuǎn)化成只需一個(gè)圓盤的推，直至轉(zhuǎn)化成只需一個(gè)圓盤的Hanoi問問題。題。void hanoi (int n, char x, char y,

26、 char z) / 將塔座x上按直徑由小到大且至上而下編號(hào)為1至n / 的n個(gè)圓盤按規(guī)那么搬到塔座z上，y可用作輔助塔座。1 2 if (n=1)3 move(x, 1, z); / 將編號(hào)為的圓盤從x移到z4 else 5 hanoi(n-1, x, z, y); / 將x上編號(hào)為至n-1的圓 / 盤移到y(tǒng), z作輔助塔6 move(x, n, z); / 將編號(hào)為n的圓盤從x移到z hanoi(n-1, y, x, z); / 將y上編號(hào)為至n-1的圓 /盤移到z, x作輔助塔8 9 執(zhí)行情況：執(zhí)行情況：遞歸任務(wù)棧保管內(nèi)容：形參遞歸任務(wù)棧保管內(nèi)容：形參n, x, y, z和前往地址前往地

27、址用語句和前往地址前往地址用語句行號(hào)表示。行號(hào)表示。任務(wù)記錄構(gòu)造：任務(wù)記錄構(gòu)造：返回地址nxyz void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else5 hanoi(n-1,x,z,y);6 move(x, n, z);7 hanoi(n-1,y,x,z);8 9 abc1230 3 a b c0 3 a b c6 2 a c b0 3 a b c6 2 a c b6 1 a b cabc0 3 a b c6 2 a c babc0 3 a b c6 2 a c b8 1 c a babc0 3 a b c0

28、 3 a b c6 2 a c b void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else5 hanoi(n-1,x,z,y);6 move(x, n, z);7 hanoi(n-1,y,x,z);8 9 abc0 3 a b c6 2 a c babc0 3 a b c8 2 b a c0 3 a b c8 2 b a c 6 1 b c aabc0 3 a b c void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else5 h

29、anoi(n-1,x,z,y);6 move(x, n, z);7 hanoi(n-1,y,x,z);8 9 0 3 a b c8 2 b a c void hanoi(int n,char x,char y,char z)1 2 if(n=1)3 move(x,1,z);4 else5 hanoi(n-1,x,z,y);6 move(x, n, z);7 hanoi(n-1,y,x,z);8 9 abc0 3 a b c8 2 b a c8 1 a b cabc0 3 a b c棧空0 3 a b c8 2 b a c0 3 a b c8 2 b a c隊(duì)列是限定只能在表的一端進(jìn)展插入，隊(duì)列

30、是限定只能在表的一端進(jìn)展插入，在表的另一端進(jìn)展刪除的線性表。在表的另一端進(jìn)展刪除的線性表。a1 a2 a3.an 入隊(duì)出隊(duì)frontrear隊(duì)列Q=(a1,a2,an)隊(duì)列特點(diǎn)：先進(jìn)先出隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)(FIFO)3.4.1 隊(duì)列的類型定義隊(duì)列的類型定義隊(duì)尾隊(duì)尾(rear)允許插入的一允許插入的一端端隊(duì)頭隊(duì)頭(front)允許刪除的一允許刪除的一端端 ADT Queue 數(shù)據(jù)對象：數(shù)據(jù)對象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 商定其中商定其中a1 端為隊(duì)列頭，端為隊(duì)列頭， an 端

31、為隊(duì)列尾端為隊(duì)列尾根本操作：根本操作：隊(duì)列的籠統(tǒng)數(shù)據(jù)類型定義：隊(duì)列的籠統(tǒng)數(shù)據(jù)類型定義： ADT Queue隊(duì)列的根本操作：隊(duì)列的根本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()typedef struct QNode/ 結(jié)點(diǎn)類型結(jié)點(diǎn)類型 QElemType data ; struct QNode *next

32、 ; QNode, *QueuePtr; typedef struct /鏈隊(duì)列類型鏈隊(duì)列類型 QueuePtr *front ; /隊(duì)頭指隊(duì)頭指針針 QueuePtr *rear ; /隊(duì)尾指針隊(duì)尾指針 LinkQueue;3.4.2 鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)a1anQ.frontQ.rearQ.frontQ.rear空隊(duì)列空隊(duì)列 Status InitQueue (LinkQueue &Q) / 構(gòu)造一個(gè)空隊(duì)列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (

33、OVERFLOW); /存儲(chǔ)分配失敗 Q.front-next = NULL; return OK; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊(duì)尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存儲(chǔ)分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; Status DeQueue (LinkQueue &Q, QElemType &a

34、mp;e) / 假設(shè)隊(duì)列不空，那么刪除Q的隊(duì)頭元素， /用 e 前往其值，并前往OK；否那么前往ERROR 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;3.4.3 循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn)循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn) #define MAXQSIZE 100 /最大隊(duì)列長度最大隊(duì)列長度 typedef struct QElemType *base;

35、 / 動(dòng)態(tài)分配存儲(chǔ)空間動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針，假設(shè)隊(duì)列不空，頭指針，假設(shè)隊(duì)列不空， / 指向隊(duì)列頭元素指向隊(duì)列頭元素 int rear; / 尾指針，假設(shè)隊(duì)列不空，指向尾指針，假設(shè)隊(duì)列不空，指向 / 隊(duì)列尾元素隊(duì)列尾元素 的下一個(gè)位置的下一個(gè)位置 SqQueue;實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)baseM123450空隊(duì)列rear=0 front=0J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6frontrearrear123450frontJ1,J2,J3入隊(duì)rear123450J1,J2,J3出隊(duì)J1J2J3frontfront

36、frontfrontv存在問題：存在問題：v當(dāng)當(dāng)front=0,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢時(shí)，再有元素入隊(duì)發(fā)生溢出出真溢出真溢出v當(dāng)當(dāng)front0,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢時(shí)，再有元素入隊(duì)發(fā)生溢出出假溢出假溢出v處理方案處理方案v隊(duì)首固定，每次出隊(duì)剩余元素向下挪動(dòng)隊(duì)首固定，每次出隊(duì)剩余元素向下挪動(dòng)浪費(fèi)時(shí)間浪費(fèi)時(shí)間v循環(huán)隊(duì)列循環(huán)隊(duì)列v 根本思想：把隊(duì)列想象成環(huán)形，讓根本思想：把隊(duì)列想象成環(huán)形，讓base0接在接在baseM-1 之后，假設(shè)之后，假設(shè)rear+1=M,那那么令么令rear=0;u實(shí)現(xiàn)：利用實(shí)現(xiàn)：利用“模運(yùn)算模運(yùn)算u入隊(duì)：入隊(duì)： baserear = e; u rear = (rear+1)%M; u出隊(duì)：出隊(duì)： e = basefront; u front = (front+1)%M; u隊(duì)滿、隊(duì)空斷定條件隊(duì)滿、隊(duì)空斷定條件012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：隊(duì)空：front=rear隊(duì)滿：隊(duì)滿：front=rear處理方案：處理方案：1.另外設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)空、隊(duì)滿另外設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間：少用一個(gè)元素空間： 隊(duì)空：隊(duì)空：front=rear 隊(duì)滿：隊(duì)滿：(re