1、l棧l棧的應用l隊列l(wèi)小結(jié)l抽象數(shù)據(jù)類型棧的定義l棧的表示和實現(xiàn)抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義基本概念基本概念 棧棧(Stack)是限定僅在表尾進行插入和刪除的線性表。是限定僅在表尾進行插入和刪除的線性表。 允許插入和刪除的一端稱為允許插入和刪除的一端稱為棧頂棧頂(top)，另一端稱為另一端稱為棧底棧底(bottom)。 棧的特點：棧的特點：后進先出后進先出(LIFO)。 如右圖所示：如右圖所示： 抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義ADT Stack 數(shù)據(jù)對象：數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,n, n 0 數(shù)據(jù)關系：數(shù)據(jù)關系：R1= | ai-1, ai D, i=

2、2,n 約定 an 端為棧頂，a1 端為棧底。 基本操作：基本操作： InitStack(&S) 操作結(jié)果：構(gòu)造一個空棧S。 DestroyStack(&S) 初始條件：棧S已存在。 操作結(jié)果：棧S被銷毀。 ClearStack(&S) 初始條件：棧S已存在。 操作結(jié)果：將S清為空棧。 StackEmpty(S) 初始條件：棧S已存在。 操作結(jié)果：若棧S為空棧，則返回TRUE，否則返回FALSE。StackLength(S) 初始條件：棧S已存在。 操作結(jié)果：返回S的元素個數(shù)，即棧的長度。GetTop(S, &e) 初始條件：棧S已存在且非空。 操作結(jié)果：用e返回S的棧頂元素。Push(&S,

3、 e) 初始條件：棧S已存在。 操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S, &e) 初始條件：棧S已存在且非空。 操作結(jié)果：刪除S的棧頂元素，并用e返回其值。StackTraverse(S, visit( ) ) 初始條件：棧S已存在且非空。 操作結(jié)果：從棧底到棧頂依次對S的每個數(shù)據(jù)元素調(diào)用函數(shù) visit( )。一旦visit()失敗，則操作失效。ADT Stack 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 順序棧順序棧：即棧的順序存儲結(jié)構(gòu)，是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設指針base指示棧底元素位置、top指示棧頂元素的下一個位置。 通常以下述類型說明作為順

4、序棧的定義： typedef struct SElemType *base; /棧底指針 SElemType *top; /棧頂指針，初始值指向棧底(top=base 棧空） int stacksize; /棧當前可使用的最大容量 SqStack;SElemType *SElemType *int a1 an存儲結(jié)構(gòu)示意存儲結(jié)構(gòu)示意 base top stacksize SElemType *棧頂指針和棧中元素之間的關系，如圖所示：棧頂指針和棧中元素之間的關系，如圖所示：空?？諚?A進棧進棧 棧滿棧滿 D出棧出棧 top base top baseA top baseABCD top base

5、ABCDbase 為為NULL ，表示棧不存在；，表示棧不存在；top=base時，表示?？眨粫r，表示?？眨籺op指向空間最后一個位置，指示棧滿。指向空間最后一個位置，指示棧滿。 棧的順序存儲表示棧的順序存儲表示# define STACK_INIT_SIZE 100 /存儲空間初始分配量# define STACKINCREMENT 10 / 存儲空間分配增量typedef struct SEelmType *base; /在棧構(gòu)造之前和銷毀之后，base的值為NULL SEelmType *top; /棧頂指針 int stacksize; /當前已分配的存儲空間，以元素為單位SqStac

6、k; /常用的基本操作的函數(shù)原型說明常用的基本操作的函數(shù)原型說明： Status InitStack(SqStack &S); /構(gòu)造一個空棧S Status ClearStack(SqStack &S); /把S置為空棧 Status StackEmpty(SqStack S); / 判斷棧S是否為空 Status GetTop(SqStack S, SElemType &e); /獲取棧頂元素 Status Push(SqStack &S, SElemType e); /進棧 Status Pop(SqStack &S, SElemType &e); /出棧棧的基本操作實現(xiàn)棧的基本操作實現(xiàn)

7、(1)初始化棧初始化棧Status InitStack(SqStack &S) /構(gòu)造一個空棧S S.base=(Selemtype *)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW); /存儲分配失敗 S.top=S.base; S.stacksize= STACK_INIT_SIZE ; return OK;/InitStack(2)獲取棧頂元素獲取棧頂元素 Status GetTop(SqStack S, SElemType &e) /若棧不空，則用 e 返回S的棧頂元素，并返回OK，否則返回FA

8、LSE if(S.top= =S.base) return ERROR; e=*(S.top-1); reutrn OK;/GetTop (3) 進棧進棧 Status Push(SqStack &S, SElemType e) /插入元素e為新的棧頂元素 if(S.top-S.base=S.stacksize) /棧滿。 S.base=(SElemType *)realloc(s.base, (S.stacksize+ STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize

9、; S.stacksize+= STACKINCREMENT; *S.top+=e; reutrn OK;/Push(4) 出棧出棧 Status Pop(SqStack &S, SElemType &e) /若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK； /否則返回ERROR if(S.top= = S.base) return ERROR; e=*-S.top; return OK; /Pop 鏈棧鏈棧 棧的鏈式表示如下圖所示。 由于棧的操作是線性表操作的特例，則鏈棧的操作易于實現(xiàn)，在此不做詳細討論。例例1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 遵循原理遵循原理：N=(N div d) d+ N m

10、od d (其中：div為整除，mod為求余) 例如： （1348)10=(2504)8 ，其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2假設現(xiàn)要編制一個滿足下列要求的程序：對于任意輸入非負十進制對于任意輸入非負十進制整數(shù)，輸出與其等值的八進制數(shù)整數(shù)，輸出與其等值的八進制數(shù)。算法為：void conversion( ) /對于輸入的任意一個非負十進制整數(shù)，輸出與其等 值的八進制數(shù)。 Initstack(S); scanf (“%d”,N); while (N) Push(S, N % 8); N=N / 8; while

11、(!StackEmpty(S) Pop(S,e); printf(“%d”,e); /conversion例2 迷宮求解迷宮求解 求迷宮中從入口到出口的所有路徑問題是一個經(jīng)典的程序設計問題。一般求迷宮中從入口到出口的所有路徑問題是一個經(jīng)典的程序設計問題。一般采用采用“窮舉求解窮舉求解”的方法。即從入口出發(fā)，順某一方向向前探索，若能走通則的方法。即從入口出發(fā)，順某一方向向前探索，若能走通則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。都探索到為止。 為了記住所走過的路并保證在任何為了記住所走過

12、的路并保證在任何位置上都能沿原路退回，顯然需要一個位置上都能沿原路退回，顯然需要一個后進先出的結(jié)構(gòu)來保存從入口到當前位后進先出的結(jié)構(gòu)來保存從入口到當前位置的路徑。因此，在求迷宮通路的算法置的路徑。因此，在求迷宮通路的算法中應用中應用 “棧棧” 就是自然而然的事了。就是自然而然的事了。 我們用如圖所示的方塊表示迷宮。我們用如圖所示的方塊表示迷宮。白色塊為通道，陰影塊為墻（即不通）白色塊為通道，陰影塊為墻（即不通） 假設假設 “當前位置當前位置”指的是在搜索指的是在搜索過程中某一時刻所在圖中某個方塊位置；過程中某一時刻所在圖中某個方塊位置；每一個方塊有四個方向可以探索（將四每一個方塊有四個方向可以

13、探索（將四周用墻圍?。┲苡脡。?求迷宮中一條路徑的算法的基本思想是： (1) 將入口入口位置設置為“當前當前位置”； (2) 若“當前位置”可通，則： 納入“當前路徑”（插入棧頂）； 若該位置是出口位置，算法結(jié)束（求得的路徑存放在棧中）； 否則切換當前位置的東鄰位置為新的當前位置； 返回 (2) ；(3) 否則， (a) 若棧不空且棧頂位置尚有其他方向未經(jīng)探索，則 設頂新的當前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一個 相鄰塊；返回 (2)； (b) 若棧不空且棧頂位置的四周四個相鄰塊均不可通，則 從當前路徑中刪除棧頂位置； 重復步驟 (b) 直至找到一個可通的相鄰塊作為新的棧頂位置或

14、?？?； 若?？談t結(jié)束，未找到通路； 否則返回 (2)；注：“可通”指的是未曾走到過的通道塊，即不能在當前路徑上（否 則所求路徑就不是簡單路徑），也不是曾經(jīng)納入過路徑（否則 只能在死胡同內(nèi)轉(zhuǎn)圈）。/棧的元素類型typedef struct int ord; /通道塊在路徑上的“序號” PosType seat; /通道塊在迷宮中的“坐標位置” int di; /從此通道塊走向下一通道塊的“方向”SElemType;typedef struct int x; /通道塊的行號 int y; /通道塊的列號PosType;typedef int MazeTypen+2 n+2;Status MazeP

15、ath (MazeType maze, PosType start, PosType end) /求迷宮maze從入口 start 到出口 end 的通道，若求得一條通道則存放棧中 / （從棧底到棧頂），并返回 TRUE，否則返回 FALSE。 InitStack (S); curpos = start; curstep = 1; /初始化棧 S、當前位置等 do if ( Pass ( curpos ) ) /測試當前位置，若可通則 FootPrint ( curpos ); /留下足跡 e = ( curstep, curpos, 1); Push ( S, e ); /當前位置加入路徑（

16、即入棧） if ( curpos = end ) PrintMazePath; DestroyStack ( S ); return OK;/結(jié)束 curpos = NextPos (curpos , 1); curstep+; /探索下一位置，即當前位置的東鄰 else if ( !StackEmpty ( S ) )Pop ( S, e ); /當前位置不通則 while ( !StackEmpty ( S ) ); / do=while 循環(huán)結(jié)束 return FALSE;/MazePath;迷宮算法續(xù)if ( !StackEmpty ( S ) ) /當前位置不通則 Pop ( S,

17、e ); while ( e.di = 4 & !StackEmpty ( S ) ) Markprint ( e.seat ); Pop ( S, e); /留下不能通過的標記，并退回一步 /while if ( e.di 4 ) e.di+; Push ( S, e ); /換一個方向探索 crupos = NextPos ( e.seat, e.di ); /設定當前位置是該新方向上的相鄰塊 curstep = e.ord + 1; 迷宮算法執(zhí)行示例：初始化： curpos = (1, 1); curstep = 1;curpos 可通執(zhí)行(2):e.ord = curstep; e.s

18、eat = curpos; e.di = 1;e 入棧: Push ( S, e);curpos = (1, 2); curstep = 2;1, (1, 1), 12, (1, 2), 11, (1, 1), 1curpos 可通執(zhí)行(2):e.ord = 2; e.seat = (1, 2); e.di = 1;e 入棧: Push ( S, e);curpos = (1, 3); curstep = 3;curpos 不通執(zhí)行(3):e 出棧: Pop ( S, &e);因 e.di4 :e.di = e.di +1(=2);e 再入棧: Push ( S, e);curpos = (2

19、, 2); curstep = 3;2, (1, 2), 21, (1, 1), 13, (2, 2), 12, (1, 2), 11, (1, 1), 1curpos 可通執(zhí)行(2):e.ord = 3; e.seat = (2, 2); e.di = 1;e 入棧: Push ( S, e);curpos = (2, 3); curstep = 4;curpos 不通執(zhí)行(3):e 出棧: Pop ( S, &e);因 e.di4 :e.di = e.di +1(=2);e 再入棧: Push ( S, e);curpos = (3, 2); curstep = 4;3, (2, 2),

20、22, (1, 2), 21, (1, 1), 14, (3, 2), 13, (2, 2), 22, (1, 2), 21, (1, 1), 1curpos 可通執(zhí)行(2):e.ord = 4; e.seat = (3, 2); e.di = 1;e 入棧: Push ( S, e);curpos = (3, 3); curstep = 5;5, (3, 1), 14, (3, 2), 33, (2, 2), 22, (1, 2), 21, (1, 1), 110, (6, 3), 19, (5, 3), 28, (5, 2), 17, (5, 1), 16, (4, 1), 215, (8

21、, 6), 114, (8, 5), 113, (7, 5), 212, (6, 5), 211, (6, 4), 116, (8, 7), 117, (8, 8), 1例3 表達式求值表達式求值中綴表達式求值算法中綴表達式求值算法OperandType EvaluateExpression( ) /算術表達式求值的優(yōu)先算法。設OPTR和OPND分別為運算符棧 /和運算數(shù)棧，OP為運算符集合。 InitStack(OPTR); Push(OPTR,#); /初始化操作符棧 InitStack(OPND); c=getchar( ); /初始化操作數(shù)棧 while(c!=# | GetTop(O

22、PTR)!=#) if (!In(c,OP) Push(S,c); c=getchar( ); /不是運算符則進操作數(shù)棧 else switch (Precede(GetTop(OPTR),c) case ： /退棧并將運算結(jié)果入棧 Pop (OPTR,theta); Pop (OPND,b); Pop(OPND,a); Push (OPND, Operate(a,theta,b); break; /switch /while return GetTop (OPND); /EvaluateExpression 可以看出算法中還調(diào)用了兩個函數(shù)，其中Precede是判定運算符棧的棧頂運算符 與讀入

23、的運算符 之間優(yōu)先關系的函數(shù)；Operate為進行二元運算 的函數(shù)。表達式求值示例參見 P54 例3-1 12bal 抽象數(shù)據(jù)類型隊列的定義抽象數(shù)據(jù)類型隊列的定義l 鏈隊列鏈隊列隊列的鏈式表示和實現(xiàn)隊列的鏈式表示和實現(xiàn)l 循環(huán)隊列循環(huán)隊列隊列的順序表示和實現(xiàn)隊列的順序表示和實現(xiàn)隊列的定義隊列的定義隊列定義隊列定義 隊列隊列(Queue）是一種先進先出是一種先進先出 (First In First Out, 縮寫為縮寫為FIFO ) 的線性表。它只允許在表的一端進行插入，而在另一端刪除的線性表。它只允許在表的一端進行插入，而在另一端刪除元素。元素。 在隊列中，允許插入的一端叫做在隊列中，允許插入

24、的一端叫做隊尾隊尾(rear），），允許刪除的一端允許刪除的一端則稱為則稱為隊頭隊頭(front）。）。 假設隊列為假設隊列為 q = (a1,a2, , an), 那么那么 a1 就是隊頭元素，就是隊頭元素，an 則是隊則是隊尾元素。隊列的示意圖為：尾元素。隊列的示意圖為： a1 a2 a3 an 出隊列出隊列入隊列入隊列隊隊頭頭隊隊尾尾本節(jié)抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型描述ADT Queue 數(shù)據(jù)對象：數(shù)據(jù)對象：D=D=a ai i|a|ai i ElemSet,iElemSet,i=1,2,=1,2,n, n,n, n00 數(shù)據(jù)關系：數(shù)據(jù)關系：R1=aR1= | a | ai-1i-1,

25、, a ai i D, i=2,D, i=2,n.,n. 約定其中約定其中a a1 1端為隊列頭端為隊列頭, ,a an n端為隊列尾。端為隊列尾。 基本操作：基本操作： InitQueue(&QInitQueue(&Q) ) 操作結(jié)果操作結(jié)果: :構(gòu)造一個空隊列構(gòu)造一個空隊列Q Q。 DestroyQueue(&QDestroyQueue(&Q) ) 初始條件：隊列初始條件：隊列Q Q已存在。已存在。 操作結(jié)果：隊列操作結(jié)果：隊列Q Q被銷毀，不再存在。被銷毀，不再存在。 ClearQueue(&QClearQueue(&Q) ) 初始條件：隊列初始條件：隊列Q Q已存在。已存在。 操作結(jié)果

26、：將操作結(jié)果：將Q Q清為空隊列。清為空隊列。QueueEmpty(Q) 初始條件：隊列初始條件：隊列Q Q已存在。已存在。 操作結(jié)果操作結(jié)果: :若若Q Q為空隊列為空隊列, ,則返回則返回TRUE,TRUE,否則返回否則返回FALSE.FALSE.QueueLength(QQueueLength(Q) ) 初始條件：隊列初始條件：隊列Q Q已存在。已存在。 操作結(jié)果操作結(jié)果: :返回返回Q Q的元素個數(shù)的元素個數(shù), ,即隊列的長度即隊列的長度. .GetHead(Q,&eGetHead(Q,&e) ) 初始條件初始條件: :Q Q為非空隊列。為非空隊列。 操作結(jié)果操作結(jié)果: :用用e e返

27、回返回Q Q的隊頭元素。的隊頭元素。EnQueue(&Q,eEnQueue(&Q,e) ) 初始條件：隊列初始條件：隊列Q Q已存在。已存在。 操作結(jié)果操作結(jié)果: :插入元素插入元素e e為為Q Q的新的隊尾元素。的新的隊尾元素。DelQueue(&Q,&eDelQueue(&Q,&e) ) 初始條件初始條件: :Q Q為非空隊列。為非空隊列。 操作結(jié)果：刪除操作結(jié)果：刪除Q Q的隊頭元素，并用的隊頭元素，并用e e返回其值。返回其值。 QueueTraverse(Q,visit( ) 初始條件：初始條件：Q已存在且非空。已存在且非空。 操作結(jié)果：從隊頭到隊尾，依次對操作結(jié)果：從隊頭到隊尾，依

28、次對Q的每個元素調(diào)用函數(shù)的每個元素調(diào)用函數(shù)visit( )。 一旦一旦visit( )失敗，則操作失敗。失敗，則操作失敗。 ADT Queue 雙端隊列雙端隊列 定義：限定插入和刪除操作在表的兩端進行。這兩端分別稱作端點定義：限定插入和刪除操作在表的兩端進行。這兩端分別稱作端點1和端點和端點2，如圖：，如圖： a1 a2 a3 an插入刪除插入刪除端1端2本節(jié)鏈隊列鏈隊列隊列的鏈式表示和實現(xiàn)隊列的鏈式表示和實現(xiàn)定義定義 鏈隊列鏈隊列就是用就是用鏈表鏈表表示的隊列。如圖：表示的隊列。如圖： data nextQ.front.Q.rear隊頭隊頭隊尾隊尾鏈隊列鏈隊列需要兩個指針：需要兩個指針： 頭

29、指針頭指針：指向隊頭元素所在位置。：指向隊頭元素所在位置。 尾指針尾指針：指向隊尾元素所在位置。：指向隊尾元素所在位置。為了操作方便，給鏈隊列附加一頭結(jié)點，為了操作方便，給鏈隊列附加一頭結(jié)點，并令頭指針指向頭結(jié)點。并令頭指針指向頭結(jié)點。因此，空隊列的判決條件為因此，空隊列的判決條件為 頭指針和尾頭指針和尾指針均指向頭結(jié)點。指針均指向頭結(jié)點。隊列運算指針變化狀況隊列運算指針變化狀況(鏈隊的插入和刪除操作只需修改尾或頭指針鏈隊的插入和刪除操作只需修改尾或頭指針) X X y X Q.frontQ.rearQ.frontQ.frontQ.frontQ.rearQ.rearQ.rear(a)(b)(c

30、)(d)空隊列空隊列元素元素X入隊入隊元素元素y入隊入隊元素元素X出隊出隊 鏈隊列鏈隊列 隊列的鏈式表示和實現(xiàn)隊列的鏈式表示和實現(xiàn)單鏈隊列的鏈式存儲結(jié)構(gòu)：單鏈隊列的鏈式存儲結(jié)構(gòu)： typedef struct QNode /結(jié)點類型結(jié)點類型 QElemType data; struct QNode *next; QNode, * QueuePtr; typedef struct QueuePtr front; /隊頭指針隊頭指針 QueuePtr rear; /隊尾指針隊尾指針 LinkQueue;本節(jié)鏈隊的基本操作：鏈隊的基本操作：(1)初始化鏈隊初始化鏈隊 Status InitQueue

31、(LinkQueue &Q) /構(gòu)造一個空隊列構(gòu)造一個空隊列Q Q.front = Q.rear = (QueuePtr) malloc (sizeof(QNode); if (! Q.front) exit (OVERFLOW); /存儲分配失敗存儲分配失敗 Q.front-next = NULL; return OK; /InitQueue鏈隊的基本操作：鏈隊的基本操作：(2)銷毀隊列銷毀隊列 Status DestroyQueue(LinkQueue &Q) /銷毀隊列銷毀隊列Q while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.f

32、ront=Q.rear; return OK; /DestroyQueue本節(jié)(3)入隊入隊 Status EnQueue(LinkQueue &Q, QElemType e) /插入元素插入元素e為為Q的新的隊尾元素的新的隊尾元素 p=(QueuePtr)malloc(sizeof(QNode); /申請一個結(jié)點空間申請一個結(jié)點空間 if(! p) exit(OVERFLOW); p-data=e; /新結(jié)點數(shù)據(jù)賦值新結(jié)點數(shù)據(jù)賦值 p-next=NULL; Q.rear-next=p; /新結(jié)點插入到隊尾新結(jié)點插入到隊尾 Q.rear=p; return OK; / EnQueue(4)出隊

33、出隊Status DelQueue(LinkQueue &Q, QElemType &e) /若隊列不空，則刪除若隊列不空，則刪除Q的隊頭元素，用的隊頭元素，用e返回其值，并返回返回其值，并返回 / OK；否則返回否則返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; /p指向隊頭結(jié)點指向隊頭結(jié)點 e=p-data; /隊頭元素值賦予變量隊頭元素值賦予變量e Q.front-next=p-next; /從隊列中鏈表中刪除隊頭結(jié)點從隊列中鏈表中刪除隊頭結(jié)點 if (Q.rear = p) Q.rear=Q.front; /刪

34、除后隊列若為空的處理刪除后隊列若為空的處理 free(p); /釋放釋放p指向的隊頭結(jié)點指向的隊頭結(jié)點 return OK;/DelQueue注：注： 當隊列中最后一個元素被刪后，隊列尾指針也丟失了，因此需對隊尾當隊列中最后一個元素被刪后，隊列尾指針也丟失了，因此需對隊尾指針重新賦值（指向頭結(jié)點）。指針重新賦值（指向頭結(jié)點）。循環(huán)隊列循環(huán)隊列隊列的順序表示和實現(xiàn)隊列的順序表示和實現(xiàn) 和棧的順序存儲相類似，在隊列的順序存儲結(jié)構(gòu)中，除和棧的順序存儲相類似，在隊列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元存放從隊列頭到隊列尾的元素了用一組地址連續(xù)的存儲單元存放從隊列頭到隊列尾的元素外，尚需附設兩

35、個指針外，尚需附設兩個指針 frontfront 和和 rearrear 分別指示隊列頭元素分別指示隊列頭元素和隊列尾元素的位置。和隊列尾元素的位置。 為了描述方便，在此特別約定：為了描述方便，在此特別約定：初始化隊列時令初始化隊列時令 front front = = rear =rear = 0 0；插入元素時（即入隊操作），隊尾指針插入元素時（即入隊操作），隊尾指針 rearrear 增增 1 1；刪除元素時（即出隊操作），隊頭指針刪除元素時（即出隊操作），隊頭指針 frontfront 增增 1 1。因此，在非空隊列中，頭指針始終指向隊列的頭元素，而尾因此，在非空隊列中，頭指針始終指向隊

36、列的頭元素，而尾指針始終指向隊列的尾元素的下一個位置。如圖指針始終指向隊列的尾元素的下一個位置。如圖 3.12 3.12 所示。所示。 圖圖3.12(3.12(d) d) 所示情形稱為所示情形稱為“假假溢出溢出”。解決的方法是存儲空間地。解決的方法是存儲空間地址進行首尾相接處理，即將順序隊址進行首尾相接處理，即將順序隊列臆造為一個環(huán)狀的空間（故稱之列臆造為一個環(huán)狀的空間（故稱之為循環(huán)隊列），如圖為循環(huán)隊列），如圖3.13 3.13 所示。所示。 此時，隊頭、隊尾指針加此時，隊頭、隊尾指針加1 1時從時從 maxsizemaxsize 1 1 直接進到直接進到0 0，可用語言，可用語言的取模的取

37、模( (余數(shù)余數(shù)) )運算實現(xiàn)。運算實現(xiàn)。 隊頭指針增1: Q.front = (Q.front + 1) % maxsize; 隊尾指針增1: Q rear = (Q.rear + 1) % maxsize; 隊列初始化： Q.front = Q.rear = 0; 隊空條件： Q.front = Q.rear;隊滿條件： （Q.rear + 1） % maxsize = Q.front循環(huán)隊列的頭尾指針示意圖循環(huán)隊列的頭尾指針示意圖 J5J4J3051234Q.rearQ.frontJ5J4J3J6J7501234Q.rearQ.front150234Q.rearQ.front(a) 一般情況一般情況（b）隊列滿隊列滿（c）空隊列空隊列循環(huán)隊列的實現(xiàn)循環(huán)隊列的實現(xiàn) # define MAXQSIZE 100 /最大隊列長度最大隊列長度typedef struct QElemType * base; /初始化的動態(tài)分配存儲空間初始化的動態(tài)