第三章棧和隊列

1、第三章第三章 棧和隊列棧和隊列3 學時學時數(shù)據(jù)結構教學目標教學目標l 掌握棧和隊列的特點，并能在相應的應用問題中正確選用l 熟練掌握棧的兩種存儲結構的基本操作實現(xiàn)算法，特別應注意棧滿和棧空的條件l 熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，特別注意隊滿和隊空的條件數(shù)據(jù)結構棧棧第一節(jié)第一節(jié)數(shù)據(jù)結構3.1.1 3.1.1 棧的基本概念棧的基本概念1、棧的定義、棧的定義l棧棧(Stack)：是限制在表的一端進行插入和刪除操作的線性是限制在表的一端進行插入和刪除操作的線性表。又稱為后進先出表。又稱為后進先出LIFO (Last In First Out)或先進后出或先進后出FILO (First I

2、n Last Out)線性表。線性表。l棧頂棧頂(Top)：允許進行插入、刪除操作的一端，又稱為表尾。允許進行插入、刪除操作的一端，又稱為表尾。用棧頂指針用棧頂指針(top)來指示棧頂元素。來指示棧頂元素。l棧底棧底(Bottom)：是固定端，又稱為表頭。是固定端，又稱為表頭。l 空棧：空棧：當表中沒有元素時稱為空棧。當表中沒有元素時稱為空棧?！斑M進” 壓入壓入=PUSH=PUSH（ ) )“出出” 彈出彈出=POP( )=POP( )數(shù)據(jù)結構3.1.1 3.1.1 棧的基本概念棧的基本概念2、邏輯結構：、邏輯結構：與線性表相同，仍為與線性表相同，仍為一對一關系一對一關系3、存儲結構、存儲結構

3、：用用順序棧順序?；蚧蜴湕ｆ湕４鎯?，但以順序棧更常見存儲均可，但以順序棧更常見4、運算規(guī)則：、運算規(guī)則：只能在棧頂運算，且訪問結點時依照后進先出只能在棧頂運算，且訪問結點時依照后進先出（LIFO）或先進后出（）或先進后出（FILO）的原則）的原則5、實現(xiàn)方式：、實現(xiàn)方式：l關鍵是編寫關鍵是編寫入棧和出棧入棧和出棧函數(shù)，具體實現(xiàn)依順序?；蜴湕５暮瘮?shù)，具體實現(xiàn)依順序?；蜴湕５牟煌煌煌煌琹基本操作有入棧、出棧、讀棧頂元素值、建棧、判斷棧滿、基本操作有入棧、出棧、讀棧頂元素值、建棧、判斷棧滿、棧空等?？盏葦?shù)據(jù)結構3.1.1 3.1.1 棧的基本概念棧的基本概念6、棧與一般線性表的區(qū)別棧與

4、一般線性表的區(qū)別：僅在于：僅在于運算規(guī)則運算規(guī)則不同不同一般線性表一般線性表 邏輯結構：一對一邏輯結構：一對一 存儲結構：順序表、鏈表存儲結構：順序表、鏈表 運算規(guī)則：隨機運算規(guī)則：隨機、順序存取順序存取棧棧邏輯結構：一對一邏輯結構：一對一 存儲結構：順序存儲結構：順序棧棧、鏈、鏈棧棧運算規(guī)則：運算規(guī)則：后進先出后進先出表頭表頭表尾表尾棧底棧底basebase棧頂棧頂toptop低地址低地址高地址高地址低地址低地址高地址高地址vivi a a1 1 a a2 2 a ai i a an n順序表順序表VnVn a a1 1 a a2 2 a an n順序棧順序棧S S a ai ia an+1

5、n+1寫入：寫入：vivi= = a ai i 讀出讀出：x=x=vivi 壓入：壓入：PUSH(PUSH(a an+1n+1) ) 彈出：彈出： POP(xPOP(x) )前提：一定要預前提：一定要預設棧頂指針設棧頂指針toptop！數(shù)據(jù)結構進棧進棧1234503.1.3.1.2 2 棧的順序表示和實現(xiàn)棧的順序表示和實現(xiàn)top棧頂指針棧頂指針top 指示真正的棧頂元素之上的下標地址指示真正的棧頂元素之上的下標地址設數(shù)組大小為設數(shù)組大小為Mtop=base,?？?，此時出棧，則下溢（?？?，此時出棧，則下溢（underflow)top=M,棧滿，此時入棧，則上溢（棧滿，此時入棧，則上溢（overf

6、low)A棧棧 滿滿BCDEF?？諚？?StackLength(S)棧棧S 空空123450basetopbase出棧出棧123450ABCDEFtopbase#define MAXSIZE 100typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;數(shù)據(jù)結構3.1.3.1.2 2 棧的順序表示和實現(xiàn)棧的順序表示和實現(xiàn)l順序棧進棧順序棧進棧u判斷是否棧滿，若滿則出錯判斷是否棧滿，若滿則出錯u元素元素e壓入棧頂壓入棧頂u棧頂指針加棧頂指針加1Status Push( SqStack &S, SElemT

7、ype e) if( S.top - S.base= S.stacksize ) / 棧滿棧滿 return ERROR; *S.top+=e;return OK;出棧出棧123450ABCDEtopbase*S.top=e;S.top+;數(shù)據(jù)結構3.1.3.1.2 2 棧的順序表示和實現(xiàn)棧的順序表示和實現(xiàn)l順序棧的出棧順序棧的出棧u判斷是否?？?，若空則出錯判斷是否?？眨艨談t出錯u獲取棧頂元素獲取棧頂元素eu棧頂指針減棧頂指針減1Status Pop( SqStack &S, SElemType &e) if( S.top = S.base ) / ?？諚？?return E

8、RROR; e *-S.top;return OK;出棧出棧123450ABCDEtopbase-S.top;e=*S.top;數(shù)據(jù)結構3.1.3.1.2 2 棧的順序表示和實現(xiàn)棧的順序表示和實現(xiàn)l獲取順序棧的棧頂元素獲取順序棧的棧頂元素u判斷是否空棧，若空則返回錯誤判斷是否空棧，若空則返回錯誤u否則通過棧頂指針獲取棧頂元素否則通過棧頂指針獲取棧頂元素Status GetTop( SqStack S, SElemType &e) if( S.top = S.base ) return ERROR; / ?？諚？誩 = *( S.top 1 );return OK;出棧出棧123450A

9、BCDEtopbasee = *( S.top - ); ?數(shù)據(jù)結構3.1.3.1.2 2 棧的順序表示和實現(xiàn)棧的順序表示和實現(xiàn)l為減少溢出的概率，可以在同一段內存中同時使用兩個棧為減少溢出的概率，可以在同一段內存中同時使用兩個棧.優(yōu)點：互相調劑，靈活性強，減少溢出機會優(yōu)點：互相調劑，靈活性強，減少溢出機會棧棧1base1 棧棧1top1 棧棧2top2 棧棧2base2 0 StackSize-1Vl 棧棧1的底固定在下標為的底固定在下標為0的一端；的一端；l 棧棧2的底固定在下標為的底固定在下標為StackSize-1的一端。的一端。l top1和和top2分別為棧分別為棧1和棧和棧2的棧

10、頂指針；的棧頂指針；l Stack_Size為整個數(shù)組空間的大??；為整個數(shù)組空間的大??；數(shù)據(jù)結構3.1.3.1.2 2 棧的順序表示和實現(xiàn)棧的順序表示和實現(xiàn)l為減少溢出的概率，可以在同一段內存中同時使用兩個棧為減少溢出的概率，可以在同一段內存中同時使用兩個棧.優(yōu)點：互相調劑，靈活性強，減少溢出機會優(yōu)點：互相調劑，靈活性強，減少溢出機會棧棧1base 棧棧1top 棧棧2top 棧棧2base 0 StackSize-1Vl 什么時候?？?？什么時候?？眨縧 什么時候棧滿？什么時候棧滿？topi=basei （i表示棧的編號）表示棧的編號）top1+1=top2 或或top2-1=top1 數(shù)據(jù)結

11、構3.1.3.1.3 3 順序棧順序棧練習練習l如果一個棧的輸入序列為如果一個棧的輸入序列為123456，能否得到，能否得到435612和和135426的出棧序列？的出棧序列？出棧序列：出棧序列：1234564 3 5 6 21出棧序列：出棧序列：1 23 4561 3 5 4 26數(shù)據(jù)結構3.1.3.1.3 3 順序棧順序棧練習練習l若已知一個棧的入棧序列是若已知一個棧的入棧序列是1，2，3，n，其輸出序列，其輸出序列為為p1，p2，p3，pn，若，若p1=n，則，則pi為（為（ ） i n-i n-i+1 不確定不確定答答:當當p1=n時時,輸出序列必是輸出序列必是n,n-1,3,2,1,

12、則有則有: p2=n-1, p3=n-2, , pn=1 推斷出推斷出pi=n-i+1,所以本題答案為所以本題答案為C。C數(shù)據(jù)結構3.1.3.1.3 3 順序棧順序棧練習練習l設設n個元素進棧序列是個元素進棧序列是1,2,3,n,其輸出序列是其輸出序列是p1,p2,pn,若若p1=3,則則p2的值是（的值是（ ）。）。 (A) 一定是一定是2 (B) 一定是一定是1 (C) 不可能是不可能是1 (D) 以上都不對以上都不對答答:當當p1=3時時,說明說明1,2,3先進棧先進棧,立即出棧立即出棧3,然后可能出棧然后可能出棧,即為即為2,也可能也可能4或后面的元素進?；蚝竺娴脑剡M棧,再出棧。因此

13、再出棧。因此,p2可能是可能是2,也可也可能是能是4,n,但一定不能是但一定不能是1。所以本題答案為。所以本題答案為C。C數(shù)據(jù)結構3.1.3.1.4 4 鏈棧的表示與實現(xiàn)鏈棧的表示與實現(xiàn)l鏈棧的表示鏈棧的表示 運算是受限的單鏈表，只能在鏈表頭部進行操作，故沒有運算是受限的單鏈表，只能在鏈表頭部進行操作，故沒有必要附加頭結點。棧頂指針就是鏈表的頭指針。必要附加頭結點。棧頂指針就是鏈表的頭指針。 typedef struct StackNode SElemType data; struct StackNode *next; StackNode, *LinkStack; LinkStack S; 空

14、棧：空棧：s=NULLanan-1a1 xs數(shù)據(jù)結構3.1.3.1.4 4 鏈棧的表示與實現(xiàn)鏈棧的表示與實現(xiàn)l鏈棧進棧鏈棧進棧 Status Push(LinkStack &S , SElemType e) p=new StackNode; /生成新結點生成新結點p if (!p) exit(OVERFLOW); p-data=e; p-next=S; S=p; return OK; anan-1a1PSe數(shù)據(jù)結構3.1.3.1.4 4 鏈棧的表示與實現(xiàn)鏈棧的表示與實現(xiàn)l鏈棧出棧鏈棧出棧 Status Pop (LinkStack &S,SElemType &e) if

15、 (S=NULL) return ERROR; e = S- data; p = S; S = S- next; delete p; return OK; anan-1a1 SeP數(shù)據(jù)結構3.1.3.1.4 4 鏈棧的表示與實現(xiàn)鏈棧的表示與實現(xiàn)l獲取鏈棧棧頂元素獲取鏈棧棧頂元素 SElemType GetTop(LinkStack S) if (S=NULL) exit(1)； else return Sdata; 數(shù)據(jù)結構3.1.3.1.5 5 順序棧與鏈棧的比較順序棧與鏈棧的比較l時間性能時間性能：相同，都是常數(shù)時間：相同，都是常數(shù)時間O(1)。l空間性能：空間性能：u順序棧：順序棧：有元

16、素個數(shù)的限制和空間浪費的問題。有元素個數(shù)的限制和空間浪費的問題。u鏈棧：鏈棧：沒有棧滿的問題，只有當內存沒有可用空間時才沒有棧滿的問題，只有當內存沒有可用空間時才會出現(xiàn)棧滿，但是每個元素都需要一個指針域，從而產會出現(xiàn)棧滿，但是每個元素都需要一個指針域，從而產生了結構性開銷。生了結構性開銷。 總之，當棧的使用過程中元素個數(shù)變化較大時，用鏈棧是總之，當棧的使用過程中元素個數(shù)變化較大時，用鏈棧是適宜的，反之，應該采用順序棧。適宜的，反之，應該采用順序棧。數(shù)據(jù)結構數(shù)據(jù)結構棧的應用棧的應用 第二節(jié)第二節(jié)數(shù)據(jù)結構3.2.1 3.2.1 數(shù)制轉換數(shù)制轉換l已知一個無符號十進制整數(shù)已知一個無符號十進制整數(shù) N

17、，寫一算法，依次輸出其對應，寫一算法，依次輸出其對應的八進制數(shù)的各位數(shù)字。的八進制數(shù)的各位數(shù)字。N = 134810250481348/8 168 4168/8 21 021/8 2 5商除以商除以8 商商 余數(shù)余數(shù) 4052/8 0 22輸輸出出計計算算順順序序數(shù)據(jù)結構3.2.1 3.2.1 數(shù)制轉換數(shù)制轉換 void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversio

18、n4052數(shù)據(jù)結構3.2.2 3.2.2 括號匹配的檢驗括號匹配的檢驗（ ）期待的急迫程度期待的急迫程度l算法設計描述：算法設計描述：1）凡出現(xiàn)左括弧，則進棧；）凡出現(xiàn)左括弧，則進棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空）凡出現(xiàn)右括弧，首先檢查棧是否空 若?？?，則表明該若棧空，則表明該“右括弧右括弧”多余，多余， 否則和棧頂元素比較，否則和棧頂元素比較， 若相匹配，則若相匹配，則“左括弧出棧左括弧出棧” ， 否則表明不匹配。否則表明不匹配。3）表達式檢驗結束時，）表達式檢驗結束時， 若?？?，則表明表達式中匹配正確，若?？?，則表明表達式中匹配正確， 否則表明否則表明“左括弧左括弧”有余。有余。數(shù)據(jù)

19、結構3.2.2 3.2.2 括號匹配的檢驗括號匹配的檢驗#define TRUE 0#define FLASE -1SqStack S ; S=Init_Stack() ; /*堆棧初始化堆棧初始化*/int Match_Brackets( ) char ch , x ;scanf(“%c” , &ch) ; while (asc(ch)!=13)數(shù)據(jù)結構3.2.2 3.2.2 括號匹配的檢驗括號匹配的檢驗 if (ch=()|(ch=) push(S , ch) ; else if (ch=) x=pop(S) ; if (x!=) printf(“括號不匹配括號不匹配”) ; re

20、turn FLASE ; else if (ch=) x=pop(S) ; if (x!=() printf(“(括號不匹配括號不匹配”) ; return FLASE ; 數(shù)據(jù)結構3.2.2 3.2.2 括號匹配的檢驗括號匹配的檢驗if (S.top!=0) printf(“括號數(shù)量不匹配！括號數(shù)量不匹配！”) ; return FLASE ;else return TRUE ; 數(shù)據(jù)結構3.2.3 3.2.3 行編輯程序問題行編輯程序問題l常用的文本編輯器如：常用的文本編輯器如：word、記事本，最簡單的文本編輯、記事本，最簡單的文本編輯器實現(xiàn)的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并器

21、實現(xiàn)的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。存入用戶的數(shù)據(jù)區(qū)。l在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時現(xiàn)有誤時 可以及時更正。可以及時更正。l合理的作法是：合理的作法是： 設立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然設立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)后逐行存入用戶數(shù)據(jù)區(qū); 并假設并假設“#”為退格符，為退格符，“”為退為退行符。行符。數(shù)據(jù)結構3.2.3 3.2.3 行編輯程序問題行編輯程序問題假設從終端接受了這樣兩行字符：假設從終端接受了這樣兩行字符： whli

22、#ilr#e（s#*s) outchaputchar(*s=#+);則實際有效的是下列兩行：則實際有效的是下列兩行： while (*s) putchar(*s+);數(shù)據(jù)結構3.2.3 3.2.3 行編輯程序問題行編輯程序問題Void LineEdit ( ) InitState(S); ch=getchar( );while (ch != EOF) /EOF為全文結束符為全文結束符while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置重置S為

23、空棧為空棧 default : Push(S, ch); break; ch = getchar( ); / 從終端接收下一個字符從終端接收下一個字符 將從棧底到棧頂?shù)淖址麄魉椭琳{用過程的數(shù)據(jù)區(qū)；將從棧底到棧頂?shù)淖址麄魉椭琳{用過程的數(shù)據(jù)區(qū)；ClearStack(S); / 重置重置S為空棧為空棧if (ch != EOF) ch = getchar(); DestroyStake(S);/ LineEdit數(shù)據(jù)結構3.2.4 3.2.4 迷宮求解迷宮求解數(shù)據(jù)結構3.2.4 3.2.4 迷宮求解迷宮求解l求迷宮路徑算法的基本思想是：求迷宮路徑算法的基本思想是：u若當前位置若當前位置“可通可通”，

24、則納入路徑，繼續(xù)前進，則納入路徑，繼續(xù)前進;u若當前位置若當前位置“不可通不可通”，則后退，換方向繼續(xù)探索，則后退，換方向繼續(xù)探索;u若四周若四周“均無通路均無通路”，則將當前位置從路徑中刪除出去。，則將當前位置從路徑中刪除出去。數(shù)據(jù)結構# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 3.2.4 3.2.4 迷宮求解迷宮求解 1 1 11 2 22 2 23 2 13 3 13 4 42 4 12 5 12 6 41 6

25、 31 5 31 4 43$數(shù)據(jù)結構3.2.4 3.2.4 迷宮求解迷宮求解l求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法：設定當前位置的初值為入口位置；設定當前位置的初值為入口位置； do 若當前位置可通，若當前位置可通， 則將當前位置插入棧頂；則將當前位置插入棧頂； / 納入路徑納入路徑 若該位置是出口位置，則算法結束；若該位置是出口位置，則算法結束； /求得路徑存放在棧中求得路徑存放在棧中 否則切換當前位置的東鄰方塊為新的當前位置；否則切換當前位置的東鄰方塊為新的當前位置； 否則，若棧不空且棧頂位置尚有其他方向未被探索，否則，若棧不空且棧頂位置尚有其他方向未

26、被探索， 則設定新的當前位置為沿順時針方向旋轉找到的棧頂位置則設定新的當前位置為沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通，若棧不空但棧頂位置的四周均不可通， 則刪去棧頂位置；則刪去棧頂位置；/ 從路徑中刪去該通道塊從路徑中刪去該通道塊 若棧不空，則重新測試新的棧頂位置，若棧不空，則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至棧空；直至找到一個可通的相鄰塊或出棧至?？眨?while (棧不空）；棧不空）；若?？?，則表明迷宮沒有通路。若棧空，則表明迷宮沒有通路。數(shù)據(jù)結構3.2.4 3.2.4 迷宮求解迷宮求解 typedef stru

27、ct int ord; / 通道塊在路徑上的通道塊在路徑上的“序號序號” PosType seat; / 通道塊在迷宮中的通道塊在迷宮中的“坐標位置坐標位置” int di; / 從此通道塊走向下一通道塊的從此通道塊走向下一通道塊的“方向方向” SElemType; / 棧的元素類型棧的元素類型數(shù)據(jù)結構3.2.4 3.2.4 迷宮求解迷宮求解 Status MazePath ( MazeType maze, PosType start,PosType end ) / 若迷宮若迷宮maze中從入口中從入口 start到出口到出口 end的通道的通道,則求得一條存則求得一條存 / 放在棧中放在棧中

28、(從棧底到棧頂從棧底到棧頂),并返回并返回TRUE；否則返回；否則返回FALSE InitStack(S); curpos = start; / 設定設定“當前位置當前位置”為為“入口位置入口位置” curstep = 1; / 探索第一步探索第一步 do if (Pass (curpos) / 當前位置可通當前位置可通,即未曾走過的通道塊即未曾走過的通道塊 FootPrint (curpos); / 留下足跡留下足跡 e = ( curstep, curpos, 1 ); Push (S,e); / 加入路徑加入路徑 if ( curpos = end ) return (TRUE); /

29、到達終點（出口）到達終點（出口） curpos = NextPos ( curpos, 1 ); /下一位置是當前位置東鄰下一位置是當前位置東鄰 curstep+; / 探索下一步探索下一步 /if數(shù)據(jù)結構3.2.4 3.2.4 迷宮求解迷宮求解 else / 當前位置不能通過當前位置不能通過 if (!StackEmpty(S) Pop (S,e); while (e.di=4 & !StackEmpty(S) MarkPrint (e.seat); Pop (S,e); / 留下不能通過的標記，并退回一步留下不能通過的標記，并退回一步 / while if (e.di= 0 數(shù)據(jù)關

30、系：數(shù)據(jù)關系：R = | ai-1, aiD, i=2,3,n ， 約定約定a1端為隊首，端為隊首， an端為隊尾。端為隊尾。 基本操作：基本操作： (1) InitQueue (&Q) /構造空隊列構造空隊列 (2) DestroyQueue (&Q) /銷毀隊列銷毀隊列 (3) ClearQueue (&S) /清空隊列清空隊列 (4) QueueEmpty(S) /判空判空. 空空-TRUE, (5) QueueLength(Q) /取隊列長度取隊列長度 (6) GetHead (Q,&e) /取隊頭元素取隊頭元素, (7) EnQueue (&Q

31、,e) /入隊列入隊列 (8) DeQueue (&Q,&e) /出隊列出隊列 (9) QueueTraverse(Q,visit() /遍歷遍歷ADT Queue數(shù)據(jù)結構3.3.2 3.3.2 隊列的順序表示隊列的順序表示l隊列的順序表示隊列的順序表示用一維數(shù)組用一維數(shù)組baseM #define M 100 /最大隊列長度最大隊列長度 Typedef struct QElemType *base; /初始化的動態(tài)分配存儲空間初始化的動態(tài)分配存儲空間 int front; /頭指針頭指針 int rear; /尾指針尾指針 SqQueue;數(shù)據(jù)結構3.3.2 3.3.2 隊列

32、的順序表示隊列的順序表示入隊入隊123450rear設兩個指針設兩個指針front,rear,約定：約定：rear指示隊尾元素下一位置；指示隊尾元素下一位置；front指示隊頭元素，指示隊頭元素，初值初值front=rear=0。ABC空隊空隊123450frontrearfront出隊出隊123450ABCrearfront空隊標志：空隊標志：front= =rear入隊：入隊：baserear+=x;出隊：出隊：x=basefront+;數(shù)據(jù)結構3.3.2 3.3.2 隊列的順序表示隊列的順序表示真溢出真溢出123450ABCDEFfrontrear假溢出假溢出123450DEFrearf

33、ront存在問題：存在問題：設數(shù)組大小為設數(shù)組大小為M，則：，則：當當front=0,rear=M時，再有元素入隊發(fā)生溢出時，再有元素入隊發(fā)生溢出真溢出真溢出當當front 0,rear=M時，再有元素入隊發(fā)生溢出時，再有元素入隊發(fā)生溢出假溢出假溢出循環(huán)隊列循環(huán)隊列數(shù)據(jù)結構3.3.3 3.3.3 循環(huán)隊列的定義循環(huán)隊列的定義l為充分利用向量空間，克服上述為充分利用向量空間，克服上述“假溢出假溢出”現(xiàn)象的方法是：現(xiàn)象的方法是：將為隊列分配的向量空間看成為一個首尾相接的圓環(huán)，并將為隊列分配的向量空間看成為一個首尾相接的圓環(huán)，并稱這種隊列為稱這種隊列為循環(huán)隊列循環(huán)隊列(Circular Queue)

34、。1 10 0Q.rearQ.rearQ.frontQ.front.base0接在接在baseM-1之之后后若若rear+1=M則令則令rear=0;實現(xiàn)：利用實現(xiàn)：利用“模?！边\算運算入隊：入隊： baserear=x; rear=(rear+1)%M;出隊出隊： x=basefront; front=(front+1)%M; 數(shù)據(jù)結構3.3.3 3.3.3 循環(huán)隊列的定義循環(huán)隊列的定義J4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfrontJ9J9J8J8J7J7J7,J8,J9J7,J8,J9入隊入隊隊空：隊空：front=rearfront=re

35、ar隊滿：隊滿：front=rearfront=rear解決方案：解決方案：1.1.另外另外設一個標志設一個標志以區(qū)別隊空、隊滿以區(qū)別隊空、隊滿2 2. .少用一個元素空間少用一個元素空間： 隊空：隊空：front=rearfront=rear 隊滿：隊滿：( (rear+1)%M=frontrear+1)%M=frontJ4J4J5J5J6J60 01 12 23 34 45 5rearrearfrontfront0 01 12 23 34 45 5frontfrontJ4,J5,J6J4,J5,J6出隊出隊rearrear數(shù)據(jù)結構3.3.3 3.3.3 循環(huán)隊列的表示與實現(xiàn)循環(huán)隊列的表示與

36、實現(xiàn)l 循環(huán)隊列的表示循環(huán)隊列的表示#define MAXQSIZE 100 /最大隊列長度最大隊列長度Typedef struct QElemType *base; /初始化的動態(tài)分配存儲空間初始化的動態(tài)分配存儲空間 int front; /頭指針頭指針 int rear; /尾指針尾指針SqQueue; 數(shù)據(jù)結構3.3.3 3.3.3 循環(huán)隊列的表示與實現(xiàn)循環(huán)隊列的表示與實現(xiàn)l 循環(huán)隊列的入隊循環(huán)隊列的入隊Status EnQueue(SqQueue &Q,QElemType e) if(Q.rear+1)%MAXQSIZE=Q.front) return ERROR; Q.bas

37、eQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK;數(shù)據(jù)結構3.3.3 3.3.3 循環(huán)隊列的表示與實現(xiàn)循環(huán)隊列的表示與實現(xiàn)l 循環(huán)隊列的出隊循環(huán)隊列的出隊Status DeQueue (LinkQueue &Q,QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK;數(shù)據(jù)結構3.3.4 3.3.4 隊列的鏈式表示隊列的鏈式表示typedef struct QNode QElemTy

38、pe data; struct Qnode *next;Qnode, *QueuePtr;typedef struct QueuePtr front; /隊頭指針隊頭指針 QueuePtr rear; /隊尾指針隊尾指針LinkQueue; front rear y x空隊列空隊列front rear數(shù)據(jù)結構3.3.4 3.3.4 隊列的鏈式表示隊列的鏈式表示x入隊入隊空隊列空隊列front rearfront rear x front rear y xfront rear y x x出隊出隊y入隊入隊數(shù)據(jù)結構3.3.5 3.3.5 隊列的鏈式實現(xiàn)隊列的鏈式實現(xiàn)l獲取鏈隊的隊頭元素獲取鏈隊的隊

39、頭元素Status GetHead (LinkQueue Q, QElemType &e) if(Q.front=Q.rear) return ERROR; e=Q.front-next-data; return OK;front rear x 數(shù)據(jù)結構3.3.5 3.3.5 隊列的鏈式實現(xiàn)隊列的鏈式實現(xiàn)l鏈隊列入隊鏈隊列入隊Status EnQueue(LinkQueue &Q,QElemType e) p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=e; p-next=NULL; Q.rear-

40、next=p; Q.rear=p; return OK;front rear y xp數(shù)據(jù)結構3.3.5 3.3.5 隊列的鏈式實現(xiàn)隊列的鏈式實現(xiàn)l鏈隊列出隊鏈隊列出隊Status DeQueue (LinkQueue &Q,QElemType &e) 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;pfront rear y x數(shù)據(jù)結構3.3.6 3.3.6 隊列的應用隊列的應用l汽車加油站汽車加油站隨著城市里汽車數(shù)量的急速增長，汽車加油站也漸漸多了起隨著城市里汽車數(shù)量的急速增長，汽車加油站也漸漸多了起來。通常汽車加油站的結構基本上是：入口和出口為單行道，來。通常汽車加油站的結構基本上是：入口和出口為單行道，加油車道可能有若