1、第三章 棧與隊列通常稱，棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。 線性表線性表 棧棧 隊列隊列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棧和隊列是兩種常用的數據類型棧和隊列是兩種常用的數據類型輔導3.1 棧的類型定義棧的類型定

2、義3.2 棧的應用舉例棧的應用舉例3.3 棧類型的實現棧類型的實現3.4 隊列的類型定義隊列的類型定義3.5 隊列類型的實現隊列類型的實現3.1 棧的類型定義棧的類型定義 ADT Stack 數據對象：數據對象： D ai | ai ElemSet, i=1,2,.,n, n0 數據關系：數據關系： R1 | ai-1, aiD, i=2,.,n 約定約定an 端為棧頂，端為棧頂，a1 端為棧底。端為棧底。 基本操作：基本操作： ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackL

3、ength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()InitStack(&S)操作結果：構造一個空棧 S。DestroyStack(&S)初始條件：棧 S 已存在。操作結果：棧 S 被銷毀。StackEmpty(S)初始條件：棧 S 已存在。操作結果：若棧 S 為空棧，則返回 TRUE，否則 FALE。StackLength(S)初始條件：棧 S 已存在。操作結果：返回 S 的元素個數，即棧的長度。ClearStack(&S)初始條件：棧 S 已存在。操作結果

4、：將 S 清為空棧。 GetTop(S, &e) 初始條件：棧 S 已存在且非空。操作結果：用 e 返回 S 的棧頂元素。a1 a2an Push(&S, e) 初始條件：棧 S 已存在。 操作結果：插入元素 e 為新的棧頂元素。a1 a2an e Pop(&S, &e) 初始條件：棧 S 已存在且非空。 操作結果：刪除 S 的棧頂元素，并用 e 返回其值。a1 a2anan-1 棧的表示和實現 與線性表類似，棧也有兩種存儲表示法： （1）順序棧 （2）鏈式棧示例： 輸入： 1，2，3 如何使用Push和Pop操作，使得 輸出： 2，3，1 或 3，2，1 或

5、1，2，3stacksizetopbase順序棧 ADCBATypedef struct SElemType * base; SElemType *top; int stacksize;SqStack;空棧B AtopbasetopbasetopbaseA進棧B,C,D進棧D,C出棧SqStack S/- 棧的順序存儲表示 - #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; 類似于線性表的順序

6、映象實現，指向表尾的指針可以作為棧頂指針。 Status InitStack (SqStack &S)/ 構造一個空棧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;Status GetTop( SqStack S, SElemType &e ) /若棧不空，則用若棧不空，則用e返回返回S的棧頂元素，并返回的棧頂元素

7、，并返回OK;否則返回否則返回ERROR if( S.top = S.base ) return ERROR; e= *(s.top-1); return OK; Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /棧滿，追加存儲空間棧滿，追加存儲空間 S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemType); if (!S.base) exit (OVERFLOW);

8、/存儲分配失敗存儲分配失敗 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;Status Pop (SqStack &S, SElemType &e) / 若棧不空，則刪除若棧不空，則刪除S的棧頂元素，的棧頂元素， / 用用e返回其值，并返回返回其值，并返回OK； / 否則返回否則返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;3.2 棧的應用舉例棧的應用舉例例一、例一、 數制轉

9、換數制轉換例二、例二、 括號匹配的檢驗括號匹配的檢驗例三、例三、 行編輯程序問題行編輯程序問題例四、例四、 迷宮求解迷宮求解例五、例五、 表達式求值表達式求值例六、例六、 實現遞歸實現遞歸例一、例一、 數制轉換數制轉換 算法基于原理：算法基于原理： N = (N div d)d + N mod d 例如：（例如：（1348)10 = (2504)8 ，其運算過程如下：，其運算過程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2計算順序計算順序輸出順序輸出順序void conversion () InitStack(S); scanf (

10、%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion書本的代碼書本的代碼void conversion () InitStack(S); scanf (%d,N); do Push(S, N % 8); N = N/8; while(N); while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion改進：改進：N=0也能正常顯示也能正常顯示例二、例二、 括號匹配的檢驗括號匹配

11、的檢驗假設在表達式中假設在表達式中（）或（）或（ ）等為正確的格式，等為正確的格式，（ ）或（）或（ ）或）或 （）（）)均為不正確的格式。均為不正確的格式。則 檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。分析可能出現的不匹配的情況: 到來的右括弧并非是所“期待”的；例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8 到來的是“不速之客”； 直到結束，也沒有到來所“期待”的括弧。算法的設計思想：算法的設計思想：假設輸入的表達式的每個括號為假設輸入的表達式的每個括號為a1,a2,.,an,for i=1 to n，對每個括號，對每個括號ai, 1）凡出現左括弧，則進

12、棧；）凡出現左括弧，則進棧； 2）凡出現右括弧，首先檢查棧是否空）凡出現右括弧，首先檢查棧是否空 (1)若棧空，則表明該若棧空，則表明該“右括弧右括弧”多余，多余， 表明表達式錯誤，表明表達式錯誤， (2)若棧不空，則和棧頂元素比較，若棧不空，則和棧頂元素比較， (a)若相匹配，則若相匹配，則“左括弧出棧左括弧出棧” ， (b)若不匹配，則表明表達式錯誤。若不匹配，則表明表達式錯誤。當表達式檢驗結束時（即當表達式檢驗結束時（即 i n ），）， 若棧空，則表明表達式中表達式正確，若棧空，則表明表達式中表達式正確， 若棧不空，表明若棧不空，表明“左括弧左括弧”多余多余,表明表達式錯誤。表明表達式

13、錯誤。Status matching(string& exp) int state = 1; while (i=Length(exp) & state) switch (expi) case “(”:Push(S,expi); i+; break; case”)”: if (NOT StackEmpty(S)&GetTop(S)=“(“ ) Pop(S,e); i+; else state = 0; break; default: state = 0; break; if (StackEmpty(S)&state) return OK; 例三、行編輯程序問題例三

14、、行編輯程序問題如何實現？如何實現？“每接受一個字符即存入存儲器每接受一個字符即存入存儲器” ? 并不恰當！ 設立一個輸入緩沖區，用以接受設立一個輸入緩沖區，用以接受用戶輸入的一行字符，然后逐行存用戶輸入的一行字符，然后逐行存入用戶數據區，并假設入用戶數據區，并假設“#”為退格符為退格符，“”為退行符。為退行符。 在用戶輸入一行的過程中，允許在用戶輸入一行的過程中，允許 用戶輸入出差錯，并在發現有誤時用戶輸入出差錯，并在發現有誤時 可以及時更正。可以及時更正。合理的作法是：假設從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);則實際有效的是

15、下列兩行： 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 = getchar(); / 從終端接收下一個字符 ClearStack(S); / 重置S為空棧if (ch != EOF) ch = getchar();while (ch != EOF) /EOF為全文結束符為全文結束符將從棧底到棧頂的字符傳送至調用

16、過程的數據區；例四、例四、 迷宮求解迷宮求解通常用的是“窮舉求解”的方法# #$# #$# $# # # # # #路徑：當前已經走過的位置序列當前位置：即將試圖去踩的位置，不一定能踩上，該位置還沒有保存在路徑中。求迷宮路徑算法的基本思想是： 若當前位置“可通”，則納入路徑，繼續前進; 若當前位置“不可通”，則后退，換方向繼續探索; 若四周“均無通路”，則將當前位置從路徑中刪除出去。東東南南西西北北東東南南西西北北當前位置當前位置curpos當前位置當前位置當前已經踩上當前已經踩上的位置序列的的位置序列的最后一步最后一步設定當前位置的初值為入口位置； do 若當前位置可通， 則將當前位置插入棧

17、頂； 若該位置是出口位置，則算法結束； 否則切換當前位置的東鄰方塊為 新的當前位置； 否則 while (棧不空）；求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法： 若棧不空且棧頂位置尚有其他方向未被探索，若棧不空且棧頂位置尚有其他方向未被探索，則設定新的當前位置為則設定新的當前位置為: 沿順時針方向旋轉沿順時針方向旋轉 找到的棧頂位置的下一相鄰塊；找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，若棧不空但棧頂位置的四周均不可通，則刪去棧頂位置；則刪去棧頂位置；/ 從路徑中刪去該通道塊從路徑中刪去該通道塊 若棧不空，則重新測試新的棧頂位置，若棧不空，則

18、重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至棧空；直至找到一個可通的相鄰塊或出棧至棧空；若棧空，則表明迷宮沒有通路。若棧空，則表明迷宮沒有通路。Typedef struct int ord; PosType seat; int di;SElemType;Status MazePath(MazeType maze, PosType start, PosType end) /若迷宮maze中存在從入口start 到出口end的通道，則求得一條存放在棧中（從棧底到棧頂），并返回TRUE；否則返回FALSE;InitStack(S); curpos = start;curstep =1;d

19、o if ( Pass( curpos) ) /當前位置可通當前位置可通 FootPrint(curpos); e = ( curstep, curpos, 1); Push(S,e); if ( curpos = end ) return (TRUE); curpos = NextPos( curpos, 1); curstep+; else /當前位置不能通過 if ( !StackEmpty(S) ) Pop(S,e); while( e.di=4 & !StackEmpty(S) ) /留下不能通過的標記，并返回上一步 MarkPrint( e.seat); Pop(S,e);

20、 if ( e.di4 ) e.di+; Push(S,e);/換下一個方向探索 /設定當前位置是該方向上的相鄰塊。 curpos= NextPos(e.seat,e.di); /if / if / else while ( !StackEmpty(S) ); return (FALSE); /MazePath 表達式 4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10 -2 = 8例五、例五、 表達式求值表達式求值表達式的組成：操作數Operand：5, 255運算符Operator：+，- ，*， /界限符delimiter：(, ), #運算符和界限符統稱為：算符，它

21、們構成的集合命名為：OP。設1，2OP,在運算的每一步中，任意兩個相繼出現的算符1，2的優先關系至多是下面三個關系之一：12 : 1的優先權高于2算符間的優先關系： 2 211 + - * / ( ) # + - * / ( # =為了實現算符優先算法，使用兩個工作棧：一個稱作OPTR,用以寄存運算符；一個稱作OPND,用以寄存操作數或運算結果；OperandType EvaluateExpression() / 算術表達式求值的算符優先算法。設OPTR和/OPND分別為運算符棧和運算數棧。 /OP為運算符集合。假設輸入的表達式是正確的。 InitStack(OPTR); Push(OPTR,

22、 #); InitStack(OPND); c=getchar(); while( c!=# | GetTop(OPTR) !=#) if( !In( c, OP) ) 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 return GetTop(OPND);int Op

23、erate( int a, char theta, int b) if( theta = + ) return a+b; if( theta =- ) return a-b; .該算法的不足之處 3 + 4 5 3 + 4 5 算法不能檢查出第二個表達式的錯誤。 也就是說該算法對正確的表達式能計算出正確的結果。棧：僅在表尾進行插入和刪除的線性表。棧：僅在表尾進行插入和刪除的線性表。棧的特點：后進先出棧的特點：后進先出 Last In First Out ( LIFO)棧頂指針鏈棧鏈棧a1an注意注意: 鏈棧中鏈棧中指針的方向指針的方向an-1空棧：棧頂指針空棧：棧頂指針top=NULL不需要頭

24、結點！不需要頭結點！入棧操作：入棧操作：p = malloc(); p-data = e; p-next = top; top = p;棧頂指針topa1an入棧：入棧：棧頂指針topa1ean新生成的結點的指針p檢驗當空棧經過一次入棧后，變成有一個結點的鏈棧檢驗當空棧經過一次入棧后，變成有一個結點的鏈棧棧頂指針top=NULLa1棧頂指針top棧頂指針topa1an-1出棧：出棧：棧頂指針topa1 anan-1出棧操作：出棧操作：p = top; e = p-data ; top = top-next; free(p); return e; an棧的鏈式存儲結構稱為鏈棧， typedef

25、struct StackNode SElemType data; struct StackNode *next; StackNode; typedef struct struct StackNode *top; int len; LinkStack;棧頂指針a1a20a1920LinkStack S;S.topS.len void InitStack(LinkStack &S) S.top=NULL; S.len = 0; int StackEmpty(LinkStack S) return S.top=NULL; int StackLength( LinkStack S) retur

26、n S.len; Status Push ( LinkStack &S, SElemType e) StackNode *p; p=(StackNode*)malloc(sizeof(StackNode); if( p=NULL) exit(OVERFLOW); pdata = e; pnext=S.top; S.top=p; S.len+; return OK;Status Pop(LinkStack & S, SElemType & e) SElemType e; StackNode * p; if( S.top =NULL ) return ERROR; /Sta

27、ck underflow p = S.top; /p指向棧頂結點 e = pdata; S.top=pnext; /把棧頂元素從鏈表中刪除 S.len -; free(p);/釋放該出棧的結點 return OK; Status GetTop(LinkStack S, SElemType & e) if(S.top = NULL) return ERROR;/空棧，沒有元素 e = S.topdata; return OK; 棧與遞歸的實現 棧還有一個重要的應用是實現函數嵌套調用 嵌套調用:調用一個函數的過程中，又調用另一個函數void first(int s, int t);void

28、 second( int d);void main() int m, n;first(m,n);3000:int first( int s, int t) int i;second(i);4000:int second( int d) int x,y; 為被調用函數的形參分配存儲區； 為被調用函數的局部變量分配存儲區； 將所有的函數參數、返回地址等信息傳遞給被調用函數保存； 將控制轉移到被調用函數的入口。 當在一個函數的運行期間調用另一個函數時，在運行該被調用函數之前，需先完成三項任務：int first( int s, int t) int i;second(i);4000:sti52003

29、000返回地址main() m=3; n=200; first(m+2,n); 3000: 保存被調函數的計算結果(即return的值，放在CPU的寄存器中)； 釋放被調函數的數據區； 依照被調函數保存的返回地址將控制轉移到調用函數。從被調用函數返回調用函數之前，應該完成下列三項任務：int first( int s, int t) int i;second(i);4000:return 10;sti52003000返回地址main() m=3; n=200; first(m+2,n); 3000:first函數的數據區多個函數嵌套調用的規則是：此時的內存管理實行“棧式管理”后調用先返回后調用

30、先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的數據區函數a的數據區函數b的數據區 void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t) int i=8;3800:second(i);4000:int second( int d) int x,y;5000: 執行執行main函數前的狀態函數前的狀態void f

31、irst(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t) int i;second(i);4000:int second( int d) int x,y; 9000 2 1main返回地址返回地址mn執行到執行到first(m,n)前棧的狀態前棧的狀態啟動代碼void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);

32、3000:main();9000:.int first( int s, int t) int i;3800:second(i);4000:int second( int d) int x,y;5000: 3000 2 1 9000 2 1main返回地址返回地址mn執行到執行到second(i)前棧的狀態前棧的狀態stifirst返回地址返回地址啟動代碼void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t

33、) int i=8;3800:second(i);4000:int second( int d) int x,y;5000: 4000 83000 2 1 9000 2 1main返回地址返回地址mn執行到執行到second函數的函數的5000指令時的狀態指令時的狀態stifirst返回地址返回地址dxysecond返回地址返回地址啟動代碼void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t) int i

34、=8;3800:second(i);4000:int second( int d) int x,y;5000: 3000 2 1 9000 2 1main返回地址返回地址mn執行完執行完second函數回到函數回到4000指令時的狀態指令時的狀態stifirst返回地址返回地址啟動代碼void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t) int i=8;3800:second(i);4000:int s

35、econd( int d) int x,y;5000: 9000 2 1main返回地址返回地址mn執行完執行完first函數回到地址為函數回到地址為3000的指令時的狀態的指令時的狀態啟動代碼void first(int s, int t);void second( int d);void main() int m=1, n=2;first(m,n);3000:main();9000:.int first( int s, int t) int i=8;3800:second(i);4000:int second( int d) int x,y;5000: 執行完執行完main函數時的狀態函數

36、時的狀態啟動代碼4000 83000 2 1 9000 2 1main返回地址返回地址mn執行到執行到second函數的函數的5000指令時的狀態指令時的狀態stifirst返回地址返回地址dxysecond返回地址返回地址84000123000129000一行表示：一次函數調用一行表示：一次函數調用時，棧的情況時，棧的情況棧與遞歸的實現 一個直接調用自己或通過一系列的調用語句間接地調用自己的函數，稱作遞歸函數。Fact(n)=1 若若 n = 0n*Fact(n-1) 若若 n 0unsigned int Fact ( unsigned int n) if ( n=0) return 1;

37、return n*Fact(n-1);Fact(n)=n!Fact(n)函數直接調用自己函數直接調用自己在C語言程序設計中，遞歸調用也是函數嵌套調用，在編譯處理上沒有什么區別。 間接調用自己 int a() . b(.); void b() . count = a(); 對編譯器而言，遞歸調用和其他的函數調用沒有什么對編譯器而言，遞歸調用和其他的函數調用沒有什么區別，都采用同樣的編譯處理過程。區別，都采用同樣的編譯處理過程。 遞歸的特點、用途主要是針對編程人員而言的。遞歸的特點、用途主要是針對編程人員而言的。 對于如何編寫遞歸程序，我們在對于如何編寫遞歸程序，我們在“樹和二叉樹樹和二叉樹”這一

38、章學這一章學unsigned int Fact ( unsigned int n) int x; 3000: if ( n=0) return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 35087 n x 返回地址返回地址 當調用當調用Fact(3) 剛進入剛進入Fact函數時，函數時，棧的狀態棧的狀態5087到到5089是把函數結果賦值給是把函數結果賦值給y的指令的指令5080：調用Fact(3);5087:把函數返回值賦值給y;unsigned int Fact ( u

39、nsigned int n) int x; 3000: if ( n=0) return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 23015 35087 n x 返回地址返回地址 當調用當調用Fact(2) 剛進入剛進入Fact函數時，函數時，棧的狀態棧的狀態3015到到3019是計算乘法和賦值的指令是計算乘法和賦值的指令3010：調用Fact(n-1);3015:把函數返回值*n,并賦值給x;unsigned int Fact ( unsigned int n) int

40、 x; 3000: if ( n=0) return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 13015 23015 35087 n x 返回地址返回地址 當調用當調用Fact(1) 剛進入剛進入Fact函數時，函數時，棧的狀態棧的狀態3015到到3019是計算乘法和賦值的指令是計算乘法和賦值的指令3010：調用Fact(n-1);3015:把函數返回值*n,并賦值給x;unsigned int Fact ( unsigned int n) int x; 3000: if

41、 ( n=0) return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 03015 13015 23015 35087 n x 返回地址返回地址 當調用當調用Fact(0) 剛進入剛進入Fact函數時，函數時，棧的狀態棧的狀態3015到到3019是計算乘法和賦值的指令是計算乘法和賦值的指令3010：調用Fact(n-1);3015:把函數返回值*n,并賦值給x;unsigned int Fact ( unsigned int n) int x; 3000: if ( n=0

42、) return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 13015 23015 35087 n x 返回地址返回地址 當調用當調用Fact(0) 完成返回到上一層完成返回到上一層Fact函數時，函數時，棧的狀態棧的狀態3015到到3019是計算乘法和賦值的指令是計算乘法和賦值的指令3010：調用Fact(n-1);3015:把函數返回值*n,并賦值給x;unsigned int Fact ( unsigned int n) int x; 3000: if ( n=0)

43、return 1; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 23015 35087 n x 返回地址返回地址 當調用當調用Fact(1) 完成返回到上一層完成返回到上一層Fact函數時，函數時，棧的狀態棧的狀態3015到到3019是計算乘法和賦值的指令是計算乘法和賦值的指令3010：調用Fact(n-1);3015:把函數返回值*n,并賦值給x;unsigned int Fact ( unsigned int n) int x; 3000: if ( n=0) return 1

44、; 3010: x = n*Fact(n-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); 35087 n x 返回地址返回地址 當調用當調用Fact(2) 完成返回到上一層完成返回到上一層Fact函數時，函數時，棧的狀態棧的狀態3015到到3019是計算乘法和賦值的指令是計算乘法和賦值的指令5080：調用Fact(3);5087:把函數返回值賦值給y;unsigned int Fact ( unsigned int n) int x; 3000: if ( n=0) return 1; 3010: x = n*Fact(n

45、-1); 3020: return x; 5080: y=Fact( 3);5090: printf(“%dn”,y); n x 返回地址返回地址 當調用當調用Fact(3) 完成返回到地址為完成返回到地址為5087的指令時，的指令時，棧的狀態棧的狀態3015到到3019是計算乘法和賦值的指令是計算乘法和賦值的指令5080：調用Fact(3);5087:把函數返回值賦值給y;3.4 隊列的類型定義隊列的類型定義 隊列(queue)是一種先進先出(First In First Out, FIFO)的線性表。a1 a2an 出隊列出隊列入隊列入隊列隊頭隊頭隊尾隊尾雙端隊列：限定插入和刪除操作在表的

46、兩端進行的線性表。幾種受限的雙端隊列：（1）隊列（2）輸出受限的雙端隊列：一個端點允許插入和刪除，另一個端點只允許插入；（3）一個端點允許插入和刪除，另一個端點只允許刪除;（4）雙棧：限定雙端隊列從某個端點插入的元素只能從該端點刪除（蛻變為兩個棧底相鄰接的棧）。a1 a2 a3 an-1 an插入插入刪除刪除插入插入刪除刪除ADT Queue 數據對象：數據對象： Dai | aiElemSet, i=1,2,.,n, n0 數據關系：數據關系： R1 | ai-1, ai D, i=2,.,n 約定其中約定其中a1 端為隊列頭，端為隊列頭， an 端為隊列尾端為隊列尾基本操作：基本操作： A

47、DT Queue隊列的基本操作：隊列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()InitQueue(&Q) 操作結果：構造一個空隊列操作結果：構造一個空隊列Q。DestroyQueue(&Q)初始條件：隊列初始條件：隊列Q已存在。已存在。 操作結果：隊列操作結果：隊列Q被銷毀，被銷毀，

48、 不再存在。不再存在。 ClearQueue(&Q)初始條件：隊列Q已存在。 操作結果：將Q清為空隊列。 QueueEmpty(Q)初始條件：隊列Q已存在。 操作結果：若Q為空隊列，則返回TRUE，否則返回FALSE。 QueueLength(Q) 初始條件：隊列Q已存在。 操作結果：返回Q的元素個數，即隊列的長度。 GetHead(Q, &e) 初始條件：Q為非空隊列。 操作結果：用e返回Q的隊頭元素。a1 a2an EnQueue(&Q, e) 初始條件：隊列Q已存在。 操作結果：插入元素e為Q的新的隊尾元素。a1 a2an e DeQueue(&Q, &a

49、mp;e) 初始條件：Q為非空隊列。 操作結果：刪除Q的隊頭元素，并用e返回其值。a1 a2an 3.5 隊列類型的實現隊列類型的實現鏈隊列鏈隊列鏈式映象鏈式映象循環隊列循環隊列順序映象順序映象 typedef struct QNode / 結點類型 QElemType data; struct QNode *next; QNode, *QueuePtr;鏈隊列鏈隊列鏈式映象鏈式映象typedef struct / 鏈隊列類型鏈隊列類型 QueuePtr front; / 隊頭指針隊頭指針 QueuePtr rear; / 隊尾指針隊尾指針 LinkQueue;a1anQ.frontQ.rea

50、rQ.frontQ.rear空隊列空隊列 Status InitQueue (LinkQueue &Q) / 構造一個空隊列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存儲分配失敗 Q.front-next = NULL; return OK;Q.frontQ.rear空隊列空隊列 Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊尾元素 p = (QueuePtr) malloc (size

51、of (QNode); if (!p) exit (OVERFLOW); /存儲分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;a1Q.frontQ.rearana1Q.frontQ.reareanp Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊列不空，則刪除Q的隊頭元素， /用 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); r