第3章 棧和隊列

1、第第3章章 棧棧和和隊隊列列2/72l 重點重點n棧、隊列的定義、特點、性質和應用；棧、隊列的定義、特點、性質和應用；nADT棧、棧、ADT隊列的設計和實現以及基本操作及隊列的設計和實現以及基本操作及相關算法。相關算法。 l 難點難點n循環(huán)隊列中邊界條件的處理方法；循環(huán)隊列中邊界條件的處理方法；n分析棧和隊列在表達式求值、括號匹配、數制轉分析棧和隊列在表達式求值、括號匹配、數制轉換、迷宮求解中的應用實例，提高利用棧和隊列換、迷宮求解中的應用實例，提高利用棧和隊列解決實際問題的應用水平。解決實際問題的應用水平。 本章重點難點本章重點難點3/723.1.1 棧的定義棧的定義 3.1.2 棧的順序存

2、儲結構（順序棧）棧的順序存儲結構（順序棧）3.1.3 棧的鏈式存儲結構（鏈棧）棧的鏈式存儲結構（鏈棧）3.1.4 棧的應用棧的應用3.1 3.1 棧棧 4/72n 棧頂的當前位置是動態(tài)的，棧頂的當前位置由一個稱為棧頂的當前位置是動態(tài)的，棧頂的當前位置由一個稱為棧頂指針棧頂指針的位置指示器指示。表的另一端稱為的位置指示器指示。表的另一端稱為棧底棧底。n 當棧中沒有數據元素時，稱為當棧中沒有數據元素時，稱為空?？諚！ 棧的插入操作稱為棧的插入操作稱為進棧進?；蚧蛉霔Ｈ霔＃瑮５膭h除操作稱為，棧的刪除操作稱為退棧退?；蚧虺鰲３鰲！ 棧是一種棧是一種后進先出后進先出結構（結構（LIFO），），操作不

3、具有隨機性操作不具有隨機性。3.1.1 3.1.1 棧的定義棧的定義 l 棧是一種棧是一種特殊的線性表特殊的線性表（操作受限操作受限）n是一種是一種只能在一端進行插入或刪除操作只能在一端進行插入或刪除操作的線性表。允許進的線性表。允許進行插入、刪除操作的一端稱為行插入、刪除操作的一端稱為棧頂棧頂。5/72例例3.1 設有設有4個元素個元素a、b、c、d進棧，給出它們所有可能的出進棧，給出它們所有可能的出棧次序。棧次序。 所有可能的出棧次序如下所有可能的出棧次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba

4、 dcba棧示意圖棧示意圖棧頂棧頂棧底棧底出棧出棧進棧進棧a1a2a3a4a5a66/72例例3.2 設一個棧的輸入序列為設一個棧的輸入序列為A,B,C,D，則借助一個，則借助一個棧所得到的輸出序列不可能是棧所得到的輸出序列不可能是 。(A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C 容易得出容易得出D,A,B,C是不可能的，因為是不可能的，因為D先出來，說明先出來，說明A,B,C,D均在棧中，按照入棧順序，在棧中順序應均在棧中，按照入棧順序，在棧中順序應為為D,C,B,A，出棧的順序只能是，出棧的順序只能是D,C,B,A。7/72例例3.3 已知一個

5、棧的進棧序列是已知一個棧的進棧序列是1,2,3,n，其輸出序，其輸出序列是列是p1,p2,pn，若若p1=n，則，則pi的值的值 。(A) i (B) n-i (C) n-i+1 (D) 不確定不確定 當當p1=n時，輸出序列必是時，輸出序列必是n,n-1,3,2,1，則有，則有: p2=n-1，p3=n-2，pn=1 ，推斷出，推斷出pi=n-i+1。若若p2=n，則有多少種可能的出棧序列？，則有多少種可能的出棧序列？8/72例例3.4 設設n個元素進棧序列是個元素進棧序列是1,2,3,n，其輸出序列，其輸出序列是是p1,p2,pn，若，若p1=3，則，則p2的值的值 。(A) 一定是一定是

6、2(B) 一定是一定是1(C) 不可能是不可能是1 (D) 以上都不對以上都不對 當當p1=3時，說明時，說明1,2,3先進棧，出棧先進棧，出棧3，然后可能出，然后可能出棧棧2，也可能，也可能4或后面的元素進棧，再出棧。因此，或后面的元素進棧，再出棧。因此，p2可能是可能是2，也可能是，也可能是4,n，但一定不是，但一定不是1。9/72ADT Stack 數據對象：數據對象： 數據關系：數據關系： 抽象數據類型?；静僮鳎夯静僮鳎?ADT StackR1 | ai-1, aiD, i=2,.,n 約定約定an 端為棧頂，端為棧頂，a1 端為棧底端為棧底。 D ai | ai ElemSet,

7、 i=1,2,.,n, n0 見下頁見下頁10/72InitStack(&S) /初始化棧初始化棧DestroyStack(&S) /銷毀棧銷毀棧StackEmpty(S) /判斷棧是否為空判斷棧是否為空StackLength(S) /求棧長度求棧長度GetTop(S, &e) /取棧頂元素取棧頂元素Push(&S, e) /入棧入棧Pop(&S, &e) /出棧出棧棧的基本操作棧的基本操作ClearStack(&S) /清空棧清空棧11/72 假設棧中元素的類型是假設棧中元素的類型是SElemType，則可用下列方式來，則可用下列方式來

8、定義棧類型定義棧類型SqStack:#define STACK_INIT_SIZE 100 /初始分配量初始分配量#define STACKINCREMENT 10 /增量增量typedef struct SElemType *base; /棧底指針棧底指針 SElemType *top; /棧頂指針棧頂指針(棧頂元素的下一個位置棧頂元素的下一個位置) int stacksize; /當前分配的容量當前分配的容量 SqStack；/順序棧類型順序棧類型3.1.2 棧的順序存儲結構棧的順序存儲結構及其實現及其實現順序棧的定義：順序棧的定義：12/72順序棧進棧和出棧示意圖順序棧進棧和出棧示意圖(

9、a)(a)空?？諚?4 3 2 1 0topbase(b)(b)元素元素 a a 入棧入棧 a43210topbase(c)(c)元素元素 b b、c c、d d 入棧入棧 d c b a 43210topbase(d)(d)元素元素 d d 出棧出棧 cba43210topbase13/72順序棧順序棧的基本操作實現的基本操作實現:(1) 初始化棧初始化棧 InitStack(&s) /構造空棧構造空棧Status InitStack( SqStack &s ) s.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof( SElemTy

10、pe ); if (! s.base) exit(OVERFLOW); s.top=s.base; s.stacksize=STACK_INIT_SIZE; return OK; 14/72(2) 銷毀棧銷毀棧 DestroyStack( &s )釋放棧釋放棧s占用的存儲空間，對應算法：占用的存儲空間，對應算法：void DestroyStack( SqStack &s )free( s.base ); s.base = NULL; s.top = NULL; s.stacksize = 0;15/72(3) 求棧的長度求棧的長度 StackLength( s )返回棧返回棧s

11、中的元素個數，對應算法中的元素個數，對應算法:Status StackLength( SqStack s ) return( s.top-s.base ); 16/72(4) 判斷棧是否為空判斷棧是否為空 StackEmpty( s )棧棧S為空的條件是為空的條件是s.top=s.base，對應算法，對應算法:Status StackEmpty( SqStack s ) return( s.top = = s.base ); 17/72(5) 進棧進棧 Push( &s, e )Status Push( SqStack &s, SElemType e ) if ( s.top-

12、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; s.stacksize + = STACKINCREMENT; *s.top+=e; /先賦值，后自增先賦值，后自增 return OK; 18/72(6) 出棧出棧 Pop( &s, &e )

13、在棧不空時，先將棧指針減在棧不空時，先將棧指針減1，再將棧頂元素賦給，再將棧頂元素賦給e。對應算法對應算法: Status Pop( SqStack &s, SElemType &e ) if (s.top= =s.base) return ERROR; /棧為空，下溢棧為空，下溢 s.top-; e= *s.top; return OK; e=*-s.top;19/72(7) 取棧頂元素取棧頂元素GetTop(s)在棧不空的條件下，將棧頂元素賦給在棧不空的條件下，將棧頂元素賦給e。對應算法。對應算法: Status GetTop(SqStack s, SElemType &a

14、mp;e) if (s.top= =s.base) return ERROR; /棧為空棧為空 e=*(s.top-1); /區(qū)別取棧頂元素與出棧區(qū)別取棧頂元素與出棧 return OK; 20/72l采用鏈式存儲的棧稱為采用鏈式存儲的棧稱為鏈棧鏈棧，可采用單鏈表實現。，可采用單鏈表實現。n不存在棧滿（上溢）的情況。不存在棧滿（上溢）的情況。n規(guī)定棧的所有操作都是在單鏈表的表頭進行規(guī)定棧的所有操作都是在單鏈表的表頭進行，下圖，下圖是頭結點為是頭結點為lhead的鏈棧，的鏈棧，第一個數據結點是棧頂結點，第一個數據結點是棧頂結點，最后一個結點是棧底結點最后一個結點是棧底結點。棧中元素自棧頂到棧底依

15、次。棧中元素自棧頂到棧底依次是是an, an-1, , a1。3.1.3 棧的鏈式存儲結構棧的鏈式存儲結構及其實現及其實現鏈棧示意圖鏈棧示意圖21/72l鏈棧類型定義鏈棧類型定義 typedef struct Stacknode SElemType data; /數據域數據域 struct Stacknode *next; /指針域指針域 StackNode, *LinkStack;22/72在鏈棧中，棧的基本運算實現如下在鏈棧中，棧的基本運算實現如下:(1)初始化棧初始化棧InitStack( &s )建立一個空棧建立一個空棧s。實際上是創(chuàng)建鏈棧的頭結點，并。實際上是創(chuàng)建鏈棧的頭結點

16、，并將其將其next域置為域置為NULL。void InitStack( LinkStack &s )s=( LinkStack ) malloc ( sizeof( StackNode ) );s-next=NULL;23/72(2) 銷毀棧銷毀棧DestroyStack( &s )釋放棧釋放棧s占用的全部存儲空間。占用的全部存儲空間。void DestroyStack( LinkStack &s ) p=s-next;while (p!=NULL)free( s ); /每個結點逐一釋放每個結點逐一釋放s=p;p=p-next;24/72(3) 求棧的長度求棧的長度

17、StackLength( s )從第從第1個數據結點開始掃描單鏈表，用個數據結點開始掃描單鏈表，用n記錄數據結點記錄數據結點個數，最后返回個數，最后返回n值。值。 Status StackLength (LinkStack s) n=0;p=s;while ( p-next!=NULL ) n+; p=p-next; return n; 25/72(4)判斷棧是否為空判斷棧是否為空StackEmpty(s)棧棧S為空的條件是為空的條件是s-next=NULL，即單鏈表中沒，即單鏈表中沒有數據結點。有數據結點。 Status StackEmpty( LinkStack s ) return( s

18、-next=NULL ); 26/72(5) 進棧進棧 Push( &s, e )將新數據結點插入到頭結點之后將新數據結點插入到頭結點之后(頭插法頭插法)。 void Push( LinkStack &s, SElemType e) p=(LinkStack)malloc(sizeof(StackNode);p-data=e;p-next=s-next; /插入插入p結點作為第結點作為第1個數據結點個數據結點s-next=p; 27/72(6) 出棧出棧 Pop( &s, &e )在棧不為空的條件下，將頭結點的直接后繼結點的數在棧不為空的條件下，將頭結點的直接后

19、繼結點的數據域賦給據域賦給e，然后將其刪除。，然后將其刪除。 Status Pop( LinkStack &s, SElemType &e ) if (s-next= =NULL) return 0; / ?？盏那闆r棧空的情況p=s-next;/ p指向第指向第1個數據結點個數據結點e=p-data;s-next=p-next;free(p);return OK; 28/72 (7) 取棧頂元素取棧頂元素GetTop(s, &e) 在棧不為空的條件下，將頭結點直接后繼結點的數在棧不為空的條件下，將頭結點直接后繼結點的數據域賦給據域賦給e。 Status GetTop(L

20、inkStack s, SElemType &e) if (s-next=NULL) return 0; /?？盏那闆r棧空的情況e=s-next-data; /注意與出棧的區(qū)別注意與出棧的區(qū)別return 1; 29/72進制轉換、括號匹配、迷宮問題請參看教材。進制轉換、括號匹配、迷宮問題請參看教材。表達式求值表達式求值 這里限定的表達式求值問題是：用戶輸入一個包這里限定的表達式求值問題是：用戶輸入一個包含含“+”、“-”、“*”、“/”、正整數和圓括號等、正整數和圓括號等的的合法數學表達式，求該表達式的運算結果。合法數學表達式，求該表達式的運算結果。3.1.4 3.1.4 棧的應用棧

21、的應用30/72 表達式的三種表示方法：表達式的三種表示方法：設設 Exp = S1 OP S2則稱則稱 OP S1 S2 為前綴表示法前綴表示法 S1 OP S2 為中綴表示法中綴表示法 S1 S2 OP 為后綴表示法后綴表示法 31/72l運算符位于兩個操作數中間的表達式稱為運算符位于兩個操作數中間的表達式稱為中綴表達中綴表達式式。例如：例如： 1+2*3l中綴表達式是最常用的一種表達式的表示方法。對中綴表達式是最常用的一種表達式的表示方法。對中綴表達式的運算一般遵循中綴表達式的運算一般遵循“先乘除，后加減，從先乘除，后加減，從左到右計算，先括號內，后括號外左到右計算，先括號內，后括號外”

22、的規(guī)則。因此，的規(guī)則。因此，中綴表達式不僅要中綴表達式不僅要依賴運算符優(yōu)先級，而且還要處依賴運算符優(yōu)先級，而且還要處理括號理括號。中綴表達式（算術表達式）中綴表達式（算術表達式）32/72中綴表達式的求值中綴表達式的求值n引入引入OPTR（運算符棧）和（運算符棧）和OPND（操作數棧）兩個棧（操作數棧）兩個棧n初始：初始：OPTR有一個元素有一個元素#，OPND為空為空n依次讀入表達式中每個字符依次讀入表達式中每個字符cc = = #: return( GetTop(OPND) )c非運算符：非運算符：Push(OPND, c)c運算符運算符: t=GetTop(OPTR)，比較t、c的優(yōu)先級

23、優(yōu)先級 t c： Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); x=Operate(a, theta, b); Push(OPND, x)n繼續(xù)讀入字符，處理同上繼續(xù)讀入字符，處理同上。 l 輸入輸入：中綴表達式串(此處以#結尾) 輸出輸出：表達式的值33/72運算符優(yōu)先級運算符優(yōu)先級( () )# # ( ( # # =0 & c=9): x=0; while (c!= ) /數字字符轉換成數值數字字符轉換成數值 x=x*10+c-48; c=A+i; break; case c=+: x=Pop(S) + Pop(S); break;

24、case c=*: x=Pop(S) * Pop(S); break;算法如下：算法如下：38/72 case c=-: x=Pop(S); x= Pop(S)-x; break; case c=/: x=Pop(S); x= Pop(S)/x; break; /switch Push(S, x); /將操作數或運算結果進棧將操作數或運算結果進棧 c=A+i; /while return ( Pop(S) ); /end of CompExpr39/72(1)設定一個設定一個字符棧字符棧，用來存儲運算符，并首先將，用來存儲運算符，并首先將#入棧；入棧；(2)掃描算術表達式掃描算術表達式exp，

25、若遇到的是，若遇到的是數字數字，將其直接送到字，將其直接送到字符數組符數組postexp ；(3)若遇到若遇到運算符運算符： (3.1)若小于棧頂運算符，則將棧頂運算符出棧并存入若小于棧頂運算符，則將棧頂運算符出棧并存入postexp中，重復中，重復3.1； (3.2)若大于棧頂運算符，則進棧；若大于棧頂運算符，則進棧； (3.3)若相等，直接出棧；若相等，直接出棧；(4)重復重復(2)、(3)，直到掃描結束。，直到掃描結束。(5) 掃描結束后，將字符棧中的運算符依次出棧，并存入掃描結束后，將字符棧中的運算符依次出棧，并存入postexp中。中。 后綴表達式就在數組后綴表達式就在數組poste

26、xp中。中。中綴表達式轉換為后綴表達式中綴表達式轉換為后綴表達式40/72void trans(char exp , char postexp ) / exp為中綴表達式、為中綴表達式、postexp保存后綴表達式保存后綴表達式 InitStack(OPTR); /初始化運算符棧初始化運算符棧 Push( OPTR, # ); i=j=0; ch=expi; while( ch!=# ) /遍歷中綴表達式串遍歷中綴表達式串 if ( In(ch) ) /ch是數字字符，編寫是數字字符，編寫In()函數判斷函數判斷 while ( In(ch) ) postexpj+=ch; ch= exp+i

27、; /while postexpj+= ; /理解加入空格的意義理解加入空格的意義 / if 數字數字 41/72 if ( ! In(ch) ) /ch是運算符是運算符 t=GetTop( OPTR ); while ( cht ) Push(OPTR, ch); /大于棧頂大于棧頂 else Pop(OPTR); /等于棧頂等于棧頂 /if 運算符運算符 ch= exp+i; /end of while (ch!=#) t=Pop(OPTR); while (t!=#) /將棧中剩余運算符放入將棧中剩余運算符放入postexp中中 postexpj+=t; t=Pop(OPTR); 42/

28、723.2 3.2 隊列隊列 3.2.1 3.2.1 隊列的定義隊列的定義 3.2.2 3.2.2 隊列的鏈式存儲結構隊列的鏈式存儲結構3.2.3 3.2.3 隊列的順序存儲結構隊列的順序存儲結構43/72l隊列簡稱隊，它也是一種操作隊列簡稱隊，它也是一種操作受限的線性表受限的線性表，僅允，僅允許在表的一端進行插入，而在表的另一端進行刪除。許在表的一端進行插入，而在表的另一端進行刪除。是一種是一種先進先出（先進先出（FIFO）結構。結構。 3.2.1 3.2.1 隊列的定義隊列的定義 anan-1a3a4a2a1進隊進隊出隊出隊隊頭元素隊頭元素隊尾元素隊尾元素先進先出先進先出44/72fron

29、trearEnQueueDeQueueABCl進行進行插入插入的一端稱做的一端稱做隊尾隊尾(rear)，進行，進行刪除刪除的一端稱做的一端稱做隊頭隊頭(front)。l向隊列中插入新元素稱為向隊列中插入新元素稱為進隊或入隊進隊或入隊(EnQueue)，新元素進，新元素進隊后就成為新的隊尾元素；從隊列中刪除元素稱為隊后就成為新的隊尾元素；從隊列中刪除元素稱為出隊或離隊出隊或離隊(DeQueue)，元素出隊后，其后繼元素就成為隊頭元素。，元素出隊后，其后繼元素就成為隊頭元素。l注意注意：禁止在隊列的中間部分實施插入、刪除操作。：禁止在隊列的中間部分實施插入、刪除操作。45/72先進先出先進先出Fi

30、rst-in First-out (FIFO)如果令一組數據一一入列，如果令一組數據一一入列，然后又令該隊列中的數據然后又令該隊列中的數據一一出列，我們將得到一一一出列，我們將得到一組同序的數據。組同序的數據。ABCAABBCC最先入列的數據元素也是最先入列的數據元素也是最先出列的元素。最先出列的元素。 (FIFO)46/72隊列應用舉例隊列應用舉例l隊列能很好地異步處理數據傳送和存儲，當頻繁地隊列能很好地異步處理數據傳送和存儲，當頻繁地向數據庫中插入數據、頻繁地向搜索引擎提交數據，向數據庫中插入數據、頻繁地向搜索引擎提交數據，就可采取隊列來異步插入。還可將較慢的處理邏輯、就可采取隊列來異步插

31、入。還可將較慢的處理邏輯、有并發(fā)數量限制的處理邏輯，通過消息隊列放在后臺有并發(fā)數量限制的處理邏輯，通過消息隊列放在后臺處理。例如：處理。例如： 銀行排隊系統銀行排隊系統火車火車/ /汽車汽車/ /飛機購票系統飛機購票系統發(fā)送手機短信、發(fā)送電子郵件發(fā)送手機短信、發(fā)送電子郵件 打印文件打印文件47/72 ADT Queue 數據對象：數據對象： 數據關系：數據關系： 基本操作：基本操作： ADT Queue見下頁見下頁Dai | aiElemSet, i=1,2,.,n, n0R1 | ai-1, ai D, i=2,.,n約定約定a1 端為隊頭，端為隊頭， an 端為隊尾端為隊尾抽象數據類型隊列

32、48/72隊列的幾種基本操作如下隊列的幾種基本操作如下:(1)初始化隊列初始化隊列InitQueue(&Q)：構造一個空隊列構造一個空隊列Q。(2)銷毀隊列銷毀隊列DestroyQueue(&Q)：釋放隊列釋放隊列Q占用的占用的存儲空間。存儲空間。(3)求隊列的長度求隊列的長度QueueLength(Q)：返回隊列返回隊列Q中的中的元素個數。元素個數。(4)判斷隊列是否為空判斷隊列是否為空QueueEmpty(Q)：若隊列若隊列Q為空為空，則返回真；否則返回假。，則返回真；否則返回假。49/72(5)取隊頭元素取隊頭元素GetHead(Q, &e)：返回當前的隊頭元素返

33、回當前的隊頭元素,并將其值賦給并將其值賦給e。(6)入隊入隊Enqueue(&Q, e)：插入元素插入元素e作為作為Q的新隊尾元的新隊尾元素。素。(7)出隊出隊DeQueue(&Q, &e)：刪除隊刪除隊Q的隊頭元素，并的隊頭元素，并將其值賦給將其值賦給e。50/72鏈隊列鏈隊列Q的組成的組成: (1)存儲隊列元素的單鏈表；存儲隊列元素的單鏈表； (2)指向隊頭和隊尾的指針（頭指針和尾指針）。指向隊頭和隊尾的指針（頭指針和尾指針）。3.2.2 3.2.2 隊列的鏈式存儲結構隊列的鏈式存儲結構Q.frontQ.rear( (a a) )不帶頭結點的鏈隊初態(tài)不帶頭結點的鏈隊

34、初態(tài) Q.front Q.rear 頭結點頭結點( (b b) )帶頭結點的鏈隊初態(tài)帶頭結點的鏈隊初態(tài)( (c c) )入隊入隊2 2個元素個元素Q.frontQ.rear a b Q.frontQ.rear( (d d) )出隊出隊1 1 個元素個元素 b51/72l單鏈隊列單鏈隊列類型類型定義如下定義如下:typedef struct Qnode QElemType data; /數據元素數據元素struct Qnode *next; QNode, *QueuePtr; /鏈隊列中的結點類型定義鏈隊列中的結點類型定義typedef struct QueuePtr front; /隊頭指針隊

35、頭指針QueuePtr rear; /隊尾指針隊尾指針 LinkQueue; /鏈隊列鏈隊列52/72在鏈隊存儲中，隊列的基本操作對應的算法如下在鏈隊存儲中，隊列的基本操作對應的算法如下:(1)初始化隊列初始化隊列InitQueue(Q)構造空隊列，即只創(chuàng)建一個鏈隊頭結點，其構造空隊列，即只創(chuàng)建一個鏈隊頭結點，其front和和rear域均域均指向頭結點，不創(chuàng)建數據元素結點。指向頭結點，不創(chuàng)建數據元素結點。 Status InitQueue( LinkQueue &Q) Q.front=Q.rear=(QueuePtr )malloc (sizeof (QNode); if (!Q.fr

36、ont) exit(OVERFLOW); Q.front-next=NULL; return Ok; 53/72(2)銷毀隊列銷毀隊列DestroyQueue(Q)釋放隊列占用的存儲空間，包括釋放隊列占用的存儲空間，包括鏈隊頭結點鏈隊頭結點和和所有數據結點所有數據結點的的存儲空間。存儲空間。 Status DestroyQueue( LinkQueue &Q) while (Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return Ok; 54/72(3)判斷隊列是否為空判斷隊列是否為空QueueEmpty(

37、Q)int QueueEmpty(LinkQueue Q) return (Q.rear=Q.front); 55/72(4)入隊列入隊列EnQueue(&Q, e)創(chuàng)建創(chuàng)建data域為域為e的數據結點的數據結點p，將，將p鏈到單鏈表的鏈到單鏈表的末尾末尾，并讓，并讓鏈隊結點的鏈隊結點的rear域指向它。域指向它。Status EnQueue(LinkQueue &Q, QElemType e) p=(QueuePtr)malloc(sizeof(QNode); /生成新結點生成新結點if (!p) exit (OVERFLOW); p-data=e; /給新結點的數據域賦值給

38、新結點的數據域賦值p-next=NULL; Q.rear-next=p;Q.rear=p;return OK; /入隊入隊56/72(5)出隊列出隊列 DeQueue( &Q, &e)若原隊列不為空，則將第若原隊列不為空，則將第1個數據結點的個數據結點的data域值賦給域值賦給e，并，并刪除之。若原隊列中只有一個數據結點，則需將尾指針指向頭刪除之。若原隊列中只有一個數據結點，則需將尾指針指向頭結點。結點。 Status DeQueue( LinkQueue &Q, QElemType &e ) if (Q.rear=Q.front) return ERROR;

39、/隊列為空隊列為空p=Q.front-next;/p指向第一個數據結點指向第一個數據結點e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; /只有一個結點情形只有一個結點情形 free(p);return OK; 57/72 3.2.3 隊列的順序存儲結構隊列的順序存儲結構l假設隊列的元素個數最大不超過整數假設隊列的元素個數最大不超過整數MAXSIZE，所有的元素都具有同一數據類型所有的元素都具有同一數據類型QElemType，則，則順順序隊列類型序隊列類型SqQueue定義如下定義如下: typedef struct QEl

40、emType *base;int front, rear; /隊頭和隊尾隊頭和隊尾”指針指針” SqQueue ;58/72隊列的入隊和出隊操作示意圖：隊列的入隊和出隊操作示意圖：frontfront d d c c b b a a rearrear(b) (b) a,b,c,da,b,c,d 入隊入隊4 43 32 21 10 0frontfrontd dc cb b rearrear(c)(c)出隊一次出隊一次4 43 32 21 10 0frontfront 4 4 3 3 2 2 1 1 0 0(a)(a)空隊空隊 rearrear頭指針頭指針front指向實際隊頭位置，指向實際隊頭位

41、置，隊尾指針隊尾指針rear指向實際隊尾的下一個位置。指向實際隊尾的下一個位置。frontfronte e rearrear(d)(d)入隊入隊1 1次、出隊次、出隊2 2次次 4 43 32 21 10 0d d 59/72l前面圖前面圖(a)為隊列的初始狀態(tài)，有為隊列的初始狀態(tài)，有front=rear成成立，該條件可作為立，該條件可作為隊空隊空的條件。的條件。l能否用能否用rear=MAXSIZE-1作為隊滿的條件呢？作為隊滿的條件呢？l顯然不能，在圖顯然不能，在圖(d)中，隊列不滿，但卻滿足該條件。這時入中，隊列不滿，但卻滿足該條件。這時入隊時出現隊時出現“上溢出上溢出”，這種溢出并不是

42、真正的溢出，這種溢出并不是真正的溢出，隊列仍隊列仍存存在可存放元素的空位置，所以這是一種在可存放元素的空位置，所以這是一種假溢出假溢出。l為充分使用隊列中的存儲空間，把隊列的首尾相連為充分使用隊列中的存儲空間，把隊列的首尾相連接，形成一個環(huán)，即接，形成一個環(huán)，即循環(huán)隊列循環(huán)隊列。60/72l循環(huán)隊列循環(huán)隊列基本操作的實現：基本操作的實現：n初始化空隊：初始化空隊：Q.front=Q.rear=0;n入隊入隊：，Q.rear=(Q.rear+1)%MAXSIZE;n出隊出隊：，Q.front=(Q.front+1)%MAXSIZE;n隊空條件隊空條件nQ.front=Q.rear /由于出隊由于

43、出隊Q.front追上了追上了Q.rearn隊滿條件隊滿條件nQ.front=Q.rear /由于入隊由于入隊Q.rear 追上了追上了Q.front 問題問題：隊空、隊滿判斷條件一樣：隊空、隊滿判斷條件一樣循環(huán)隊列循環(huán)隊列61/72在入隊時少用一個數據元素空間，在入隊時少用一個數據元素空間，以隊尾指針加以隊尾指針加1等于等于隊頭指針判斷隊滿隊頭指針判斷隊滿，即隊滿條件為，即隊滿條件為: (Q.rear+1) % MAXSIZE=Q.front隊空條件仍為隊空條件仍為: Q.rear=Q.frontl如何區(qū)分隊空、隊滿如何區(qū)分隊空、隊滿? ?62/7263/72在循環(huán)隊列中，實現隊列的基本運算

44、算法如下在循環(huán)隊列中，實現隊列的基本運算算法如下:(1)初始化隊列初始化隊列InitQueue( &Q)Status InitQueue(SqQueue &Q) Q.base=(QElemType *)malloc (MAXSIZE*sizeof(QElemtype); if (!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK;64/72(2)求隊列長度求隊列長度QueueLength(Q) int QueueLength(SqQueue Q) return (Q.rear-Q.front+MAXSIZE)%MAXSIZE

45、; 65/72(3)入隊列入隊列EnQueue(&Q, e) 在隊列不滿時，先將元素添加到在隊列不滿時，先將元素添加到rear位置，再將隊尾位置，再將隊尾指針指針rear循環(huán)增循環(huán)增1。int EnQueue(SqQueue &Q, QElemType e) if ( (Q.rear+1)%MAXSIZE=Q.front ) return ERROR; /隊滿隊滿 Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK;66/72(4)出隊列出隊列DeQueue(&Q, &e)在隊列在隊列Q不空時，先將不空時，先

46、將front位置上的元素值賦給位置上的元素值賦給e，再將隊首再將隊首front循環(huán)增循環(huán)增1。對應算法如下。對應算法如下: int DeQueue(SqQueue &Q, QElemType &e) if ( Q.front=Q.rear ) return ERROR; /隊空隊空 e=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;return OK; 67/72在隊列的順序存儲結構中，設頭指針為在隊列的順序存儲結構中，設頭指針為front，尾指針，尾指針rear，隊的容量為，隊的容量為MaxSize。當有元素加入隊列時，。當有元素加入隊列時，若若rear=MaxSize-1 (初始初始rear=0)則發(fā)生隊列的上則發(fā)生隊