數(shù)據(jù)結(jié)構(gòu)課件CH3 棧和隊列

1、20212021年年1212月月2020日日1919時時5151分分20212021年年1212月月2020日日1919時時5151分分通常稱，棧和隊列是限定插入和刪除插入和刪除只能只能在表的“端點端點”進行的線性表。 線性表線性表 棧棧 隊列隊列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in20212021年年1212月月2020日日1919時時5151分分3.3 棧的應(yīng)用舉例棧的應(yīng)用舉例3.1 棧的類型定義棧的類型定義3.2 棧類型的實現(xiàn)

2、棧類型的實現(xiàn)3.4 隊列的類型定義隊列的類型定義3.5 隊列類型的實現(xiàn)隊列類型的實現(xiàn)練習20212021年年1212月月2020日日1919時時5151分分 棧的定義和特點 定義：限定僅在進行插入或刪除操作的線 性表，表尾，表頭，不含 元素的空表稱空棧。 特點：先進后出（FILO）或后進先出（LIFO）ana1a2.棧底棧頂.出棧進棧棧s=(a1,a2,an)3.1 棧的類型定義棧的類型定義20212021年年1212月月2020日日1919時時5151分分 ADT Stack 數(shù)據(jù)對象數(shù)據(jù)對象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： R1 |

3、ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作：基本操作： ADT Stack棧的抽象數(shù)據(jù)類型定義20212021年年1212月月2020日日1919時時5151分分InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit()20212021年年1212月月2020日日1919時時5151分分 InitSta

4、ck(&S) 操作結(jié)果：構(gòu)造一個空棧 S。 DestroyStack(&S) 初始條件：棧 S 已存在。 操作結(jié)果：棧 S 被銷毀。20212021年年1212月月2020日日1919時時5151分分StackEmpty(S)初始條件：棧 S 已存在。 操作結(jié)果：若棧 S 為空棧， 則返回 TRUE，否則 FALE。20212021年年1212月月2020日日1919時時5151分分 StackLength(S)初始條件：棧 S 已存在。操作結(jié)果：返回 S 的元素個 數(shù)，即棧的長度。20212021年年1212月月2020日日1919時時5151分分 GetTop(S, &am

5、p;e)初始條件：棧 S 已存在且非空。操作結(jié)果：用 e 返回 S 的棧頂元素。a1a2an 20212021年年1212月月2020日日1919時時5151分分 ClearStack(&S)初始條件：棧 S 已存在。 操作結(jié)果：將 S 清為空棧。20212021年年1212月月2020日日1919時時5151分分 Push(&S, e) 初始條件：棧 S 已存在。 操作結(jié)果：插入元素 e 為新的 棧頂元素。a1a2ane 20212021年年1212月月2020日日1919時時5151分分Pop(&S, &e) 初始條件：棧 S 已存在且非空。 操作結(jié)果：刪除

6、 S 的棧頂元素，并用 e 返回其值。a1a2anan-1 e = an20212021年年1212月月2020日日1919時時5151分分3.2棧類型的實現(xiàn)棧類型的實現(xiàn)3.2.1 順序棧順序棧3.2.1 鏈鏈 棧棧20212021年年1212月月2020日日1919時時5151分分 類似于線性表的順序映象實現(xiàn)，利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)指向表尾的指針top，指示棧頂元素在順序棧中的位置，稱為。連續(xù)存儲單元的基址用指針base指示，稱為。3.2.1 順序棧順序棧20212021年年1212月月2020日日1919時時5151分分/- 棧的順序存儲表示棧的

7、順序存儲表示 - #define STACK_INIT_SIZE 100; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;top的初值指向棧底：的初值指向棧底：top=base，此條件也可作為判?？盏臈l件；，此條件也可作為判?？盏臈l件； 在實際使用中，在實際使用中，top 始終指向棧頂元素的下一個位置上；始終指向棧頂元素的下一個位置上；入棧（插入新的棧頂元素）：入棧（插入新的棧頂元素）：top增增1；出棧（刪除棧頂元素）：出棧（刪除棧頂元素）： top減減1。20212021年年1212月月2020

8、日日1919時時5151分分top=0123450棧棧S 空空棧頂指針棧頂指針top,指向?qū)嶋H棧頂指向?qū)嶋H棧頂前的空位置，初值為前的空位置，初值為0top123450進棧進棧Atop出棧出棧棧棧 滿滿BCDEF設(shè)數(shù)組大小為設(shè)數(shù)組大小為Mtop=0,?？?，此時出棧，則?？?，此時出棧，則下溢下溢（underflow)top=M,棧滿，此時入棧，則棧滿，此時入棧，則上溢上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop棧空?？?0M-1棧棧1底底棧棧1頂頂棧棧2底底棧棧2頂頂為減少溢出的概率，可以在同一段內(nèi)存中同時使用兩個棧為減少溢出的

9、概率，可以在同一段內(nèi)存中同時使用兩個棧.StackLength(S)basebasebase20212021年年1212月月2020日日1919時時5151分分 Status InitStack (SqStack &S, int maxsize) / 構(gòu)造一個最大空間為 maxsize 的空順序棧 S S.base = new ElemTypemaxsize; if (!S.base) exit (OVERFLOW); /存儲分配失敗 S.top = S.base; S.stacksize = maxsize; return OK;20212021年年1212月月2020日日1919時

10、時5151分分 Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /棧滿 return OVERFLOW; *S.top+ = e; return OK;20212021年年1212月月2020日日1919時時5151分分Status Pop (SqStack &S, SElemType &e) / 若棧不空，則刪除S的棧頂元素， / 用 e 返回其值，并返回OK； / 否則返回ERROR if (S.top = = S.base) return ERROR; e = *-S.

11、top; return OK;20212021年年1212月月2020日日1919時時5151分分3.2.1 鏈鏈 棧棧注意注意: 鏈棧中鏈棧中指針的方向指針的方向棧頂指針a1anan-1棧底結(jié)點定義結(jié)點定義typedef struct node int data; struct node *link; node;20212021年年1212月月2020日日1919時時5151分分入棧入棧出棧出棧 .棧底toptopxptop .棧底topq20212021年年1212月月2020日日1919時時5151分分3.3 棧的應(yīng)用舉例棧的應(yīng)用舉例例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例二、例二、 括號匹配的

12、檢驗括號匹配的檢驗例三、例三、 行編輯程序問題行編輯程序問題 例四、例四、 迷宮求解迷宮求解 例五、例五、 表達式求值表達式求值 例六、例六、 實現(xiàn)遞歸實現(xiàn)遞歸20212021年年1212月月2020日日1919時時5151分分 例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 算法基于原理： (N)d1 = (N div d2)d2 + N mod d2 20212021年年1212月月2020日日1919時時5151分分例如：例如：（1348)10 = (2504)8 ，其運算過程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2計算順序計算順序輸出順

13、序輸出順序20212021年年1212月月2020日日1919時時5151分分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 ); / conversion20212021年年1212月月2020日日1919時時5151分分例二、例二、 括號匹配的檢驗括號匹配的檢驗 假設(shè)在表達式中，只有（）（）兩種括號，如：（）（）、（ ）等為正確的格式，（ ）或（ ）或 （）（） ）均為不正確的格式。

14、 檢驗括號是否匹配的方法可用:這個概念來描述。20212021年年1212月月2020日日1919時時5151分分分析可能出現(xiàn)的的情況: : 到來的右括號非是所“期待”的;例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8 到來的是“不速之客”; 直到結(jié)束，也沒有到來所“期待”的括號;20212021年年1212月月2020日日1919時時5151分分算法的設(shè)計思想：算法的設(shè)計思想：1）凡出現(xiàn)左括號左括號，則進棧進棧；2）凡出現(xiàn)右括號右括號，首先檢查棧是否空： 若?？諚？?，則表明該“右括號右括號”多余多余不匹配不匹配 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，則“左括號出棧

15、左括號出?！?否則表明不匹配不匹配3）表達式表達式檢驗結(jié)束時結(jié)束時， 若?？諚？?，則表明表達式中匹配正確匹配正確 否則表明“左括號左括號”有余有余不匹配不匹配20212021年年1212月月2020日日1919時時5151分分Status matching(string& exp) int state = 1; i=0； while (iLength(exp) & state) switch (expi) case ”(” ,”: case”)”: if (StackEmpty(S)&state) return OK; . 20212021年年1212月月2020日日1

16、919時時5151分分例三、行編輯程序問題例三、行編輯程序問題 常用的文本編輯器如：常用的文本編輯器如：word、記事、記事本，最簡單的文本編輯器實現(xiàn)的功能是：本，最簡單的文本編輯器實現(xiàn)的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。存入用戶的數(shù)據(jù)區(qū)。 “每接受一個字符即存入存儲器每接受一個字符即存入存儲器” ” ? ? 20212021年年1212月月2020日日1919時時5151分分 設(shè)立一個輸入緩沖區(qū)，用以接受設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)入用戶數(shù)據(jù)區(qū); 并假設(shè)并假設(shè)“

17、#”為退格符為退格符，“”為退行符。為退行符。 在用戶輸入一行的過程中，允在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時 可以及時更正?？梢约皶r更正。20212021年年1212月月2020日日1919時時5151分分假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);則實際有效的是下列兩行： while (*s) putchar(*s+);20212021年年1212月月2020日日1919時時5151分分Void LineEdit ( ) InitState(S); ch=getchar(

18、); DestroyStake(S);/ LineEdit 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為全文結(jié)束符20212021年年1212月月2020日

19、日1919時時5151分分例四、例四、 迷宮求解迷宮求解通常用的是“窮舉求解窮舉求解”的方法# #$# #$# $# # # # # #20212021年年1212月月2020日日1919時時5151分分# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 1 1 11 2 22 2 23 2 13 3 13 4 42 4 12 5 12 6 41 6 31 5 31 4 43$20212021年年1212月月2020日日19

20、19時時5151分分求迷宮路徑算法的基本思想基本思想是： 若當前位置若當前位置“可通可通”，則納入路徑，繼續(xù)前，則納入路徑，繼續(xù)前進進; 若當前位置若當前位置“不可通不可通”，則后退，換方向繼，則后退，換方向繼續(xù)探索續(xù)探索; 若四周若四周“均無通路均無通路”，則將當前位置從路徑，則將當前位置從路徑中刪除出去。中刪除出去。 所謂當前位置所謂當前位置“可通可通”，即此位置既不在當，即此位置既不在當前路徑上，也不是已刪除掉的前路徑上，也不是已刪除掉的“不可通不可通”的的位置位置; 20212021年年1212月月2020日日1919時時5151分分設(shè)定當前位置的初值為入口位置； do 若當前位置可通

21、若當前位置可通， 則則將當前位置插入棧頂插入棧頂； 若若該位置是出口位置，則則算法結(jié)束； 否則切換否則切換當前位置的東鄰方塊為 新的當前位置； 否則否則 while (棧不空）棧不空）；求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法： 20212021年年1212月月2020日日1919時時5151分分若若棧不空且棧頂位置尚有其他方向未被探索棧不空且棧頂位置尚有其他方向未被探索，則則設(shè)定新的當前位置為: 沿順時針方向旋轉(zhuǎn) 找到的棧頂位置的下一相鄰塊棧頂位置的下一相鄰塊；若若棧不空但棧頂位置的四周均不可通棧不空但棧頂位置的四周均不可通，則則刪去棧頂位置；/ 從路徑中刪

22、去該通道塊從路徑中刪去該通道塊 若若棧不空，則則重新測試新的棧頂位置， 直至直至找到一個可通的相鄰塊或出棧至?？?；若若?？諚？?，則則表明迷宮沒有通路。20212021年年1212月月2020日日1919時時5151分分 typedef struct int ord; / 通道塊在路徑上的“序號” PosType seat; / 通道塊在迷宮中的“坐標位置” int di; / 從此通道塊走向下一通道塊的“方向” SElemType; / 棧的元素類型 20212021年年1212月月2020日日1919時時5151分分 Status MazePath ( MazeType maze, PosT

23、ype start,PosType end ) / 若迷宮maze中從入口 start到出口 end的通道,則求得一條存 / 放在棧中(從棧底到棧頂),并返回TRUE；否則返回FALSE InitStack(S); curpos = start; / 設(shè)定“當前位置”為“入口位置” curstep = 1; / 探索第一步 do if (Pass (curpos) / 當前位置可通,即未曾走過的通道塊 FootPrint (curpos); / 留下足跡 e = ( curstep, curpos, 1 ); Push (S,e); / 加入路徑 if ( curpos = end ) ret

24、urn (TRUE); / 到達終點（出口） curpos = NextPos ( curpos, 1 ); /下一位置是當前位置東鄰 curstep+; / 探索下一步 /if 20212021年年1212月月2020日日1919時時5151分分 else / 當前位置不能通過 if (!StackEmpty(S) Pop (S,e); while (e.di=4 & !StackEmpty(S) MarkPrint (e.seat); Pop (S,e); / 留下不能通過的標記，并退回一步 / while if (e.di1時，先把上面時，先把上面n-1個圓盤從個圓盤從A移到移到

25、B,然后將然后將n號盤從號盤從A移到移到C,再將再將n-1個盤從個盤從B移到移到C。即把求解。即把求解n個圓盤的個圓盤的Hanoi問題轉(zhuǎn)化為求解問題轉(zhuǎn)化為求解n-1個圓盤的個圓盤的Hanoi問題，依次類問題，依次類推，直至轉(zhuǎn)化成只有一個圓盤的推，直至轉(zhuǎn)化成只有一個圓盤的Hanoi問題問題：ABC12320212021年年1212月月2020日日1919時時5151分分0void hanoi (int n, char x, char y, char z) / 將塔座x上按直徑由小到大且至上而下編號為1至n/ 的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1 if (n=1)2 move(x,

26、1, z); / 將編號為的圓盤從將編號為的圓盤從x移到移到z3 else 4 hanoi(n-1, x, z, y); /將將x上編號為至上編號為至n-1的圓盤移到的圓盤移到y(tǒng), z作輔助塔作輔助塔5 move(x, n, z); / 將編號為將編號為n的圓盤從的圓盤從x移到移到z6 hanoi(n-1, y, x, z); / 將將y上編號為至上編號為至n-1的圓盤移到的圓盤移到z, x作輔助塔作輔助塔 7 8 20212021年年1212月月2020日日1919時時5151分分 main() int m; printf(Input number of disks”); scanf(%d,

27、&m); printf(”Steps : %3d disks”,m); hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 632120212021年年1212

28、月月2020日日1919時時5151分分 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 A C B 6

29、1 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 622113320212021年年1212月月2020日日1919時時5151分分 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(

30、n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83 A B C 022331120212021年年1212月月2020日日1919時時5151分分 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi

31、(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0?？? A B C 02 B A C 822113320212021年年1212月月2020日日1919時時5151分分 回文游戲：順讀與逆讀字符串一樣（不含空格）回文游戲：順讀與逆讀字符串一樣（不含空格）dadt

32、op1.讀入字符串讀入字符串2.去掉空格（原串）去掉空格（原串）3.壓入棧壓入棧4.原串字符與出棧字符依次比較原串字符與出棧字符依次比較 若不等，非回文若不等，非回文 直到?？斩枷嗟龋匚闹钡綏？斩枷嗟?，回文字符串：字符串：“madam im adam”棧的其它應(yīng)用棧的其它應(yīng)用20212021年年1212月月2020日日1919時時5151分分20212021年年1212月月2020日日1919時時5151分分 隊列的定義及特點隊列的定義及特點 定義：隊列是限定只能在表的一端進行插入，在表的定義：隊列是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表另一端進行刪除的線性表 隊尾隊尾(r

33、ear)允許插入的一端允許插入的一端 隊頭隊頭(front)允許刪除的一端允許刪除的一端 隊列特點：先進先出隊列特點：先進先出(FIFO)a1 a2 a3.an 入隊出隊frontrear隊列Q=(a1,a2,an) 雙端隊列雙端隊列a1 a2 a3.an 端1端2入隊出隊入隊出隊3.4 隊列的類型定義隊列的類型定義20212021年年1212月月2020日日1919時時5151分分 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 端為隊列頭隊列頭， a

34、n 端為隊列尾隊列尾基本操作：基本操作：隊列的抽象數(shù)據(jù)類型定義隊列的抽象數(shù)據(jù)類型定義 ADT Queue20212021年年1212月月2020日日1919時時5151分分隊列的基本操作：隊列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()20212021年年1212月月2020日日1919時時5151分

35、分InitQueue(&Q) 操作結(jié)果：操作結(jié)果：構(gòu)造一個空隊列Q。DestroyQueue(&Q) 初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：隊列Q被銷毀， 不再存在。20212021年年1212月月2020日日1919時時5151分分QueueEmpty(Q)初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：若Q為空隊列，則 返回TRUE，否則返回FALSE。20212021年年1212月月2020日日1919時時5151分分 QueueLength(Q) 初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。20212

36、021年年1212月月2020日日1919時時5151分分 GetHead(Q, &e) 初始條件：初始條件：Q為非空隊列。 操作結(jié)果：操作結(jié)果：用e返回Q的隊頭元素。a1a2an 20212021年年1212月月2020日日1919時時5151分分 ClearQueue(&Q)初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：將Q清為空隊列。20212021年年1212月月2020日日1919時時5151分分 EnQueue(&Q, e) 初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：插入元素e為Q的新的隊尾元素。a1a2ane 20212021年年1

37、212月月2020日日1919時時5151分分 DeQueue(&Q, &e) 初始條件：初始條件：Q為非空隊列。 操作結(jié)果：操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。a1a2an 20212021年年1212月月2020日日1919時時5151分分3.5 隊列類型的實現(xiàn)隊列類型的實現(xiàn) 鏈鏈 隊隊 列列鏈式映象循環(huán)隊列循環(huán)隊列順序映象20212021年年1212月月2020日日1919時時5151分分 typedef struct QNode / 結(jié)點類型結(jié)點類型 QElemType data; struct QNode *next; QNode, *QueuePtr;202

38、12021年年1212月月2020日日1919時時5151分分typedef struct / 鏈隊列類型鏈隊列類型 QueuePtr front; / 隊頭指針隊頭指針 QueuePtr rear; / 隊尾指針隊尾指針 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空隊列空隊列20212021年年1212月月2020日日1919時時5151分分 Status InitQueue (LinkQueue &Q) / 構(gòu)造一個空隊列Q Q.front = Q.rear = new QNode; if (!Q.front) exit (OVERFLOW);

39、 /存儲分配失敗 Q.front-next = NULL; return OK;20212021年年1212月月2020日日1919時時5151分分 Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊尾元素 p = new QNode; if (!p) exit (OVERFLOW); /存儲分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;20212021年年1212月月2020日日1919時時5151分分 Status DeQue

40、ue (LinkQueue &Q, QElemType &e) / 若隊列不空，則刪除Q的隊頭元素， /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; / 帶頭結(jié)點 Q.front-next = p-next; free (p); return OK;if (Q.rear = p) Q.rear = Q.front;a1Q.frontQ.rear20212021年年1212月月2020日日1919時時5151分分 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲

41、結(jié)構(gòu) 實現(xiàn)：用一維數(shù)組實現(xiàn)實現(xiàn)：用一維數(shù)組實現(xiàn)sqM-1隊空rear = 0front=0123450123450frontJ1,J2,J3入隊J1J2J3rearrear123450J4,J5,J6入隊J4J5J6front設(shè)兩個指針設(shè)兩個指針front,rear,約定：約定：rear指示隊尾元素下一位置；指示隊尾元素下一位置；front指示隊頭元素，指示隊頭元素，初值初值front=rear=0?？贞犃袟l件：空隊列條件：front=rear入隊列：入隊列：sqrear+=x;出隊列：出隊列：x=sqfront+;rearrearfrontrear123450J1,J2,J3出隊J1J2J3

42、frontfrontfront20212021年年1212月月2020日日1919時時5151分分 實現(xiàn)：利用實現(xiàn)：利用“取模取?！边\算運算 入隊：入隊： sqrear=x; rear=(rear+1)%M; 出隊：出隊： x=sqfront; front=(front+1)%M; 隊滿、隊空判定條件隊滿、隊空判定條件 存在問題存在問題設(shè)數(shù)組大小為設(shè)數(shù)組大小為M，則：，則： 當當front=0,rear=M時，再有元素入隊發(fā)生溢出時，再有元素入隊發(fā)生溢出真溢出真溢出 當當front 0,rear=M時，再有元素入隊發(fā)生溢出時，再有元素入隊發(fā)生溢出假溢出假溢出 解決方案解決方案 隊首固定，每次出

43、隊剩余元素向下移動隊首固定，每次出隊剩余元素向下移動浪費時間，效率低浪費時間，效率低 發(fā)生假溢出時再移動發(fā)生假溢出時再移動 基本思想：把隊列基本思想：把隊列設(shè)想成環(huán)形設(shè)想成環(huán)形，讓，讓sq0接在接在sqM-1之后，之后，若若rear=M,則令則令rear=0;0M-11frontrear.20212021年年1212月月2020日日1919時時5151分分012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊J7,J8,J9入隊隊空：隊空：front=rear隊滿：隊滿：front=rear解決

44、方案：解決方案：1.1.另外另外設(shè)一個標志設(shè)一個標志以區(qū)別隊空、隊滿以區(qū)別隊空、隊滿2 2. .少用一個元素空間少用一個元素空間： 隊空：隊空：front = rearfront = rear 隊滿：隊滿：( (rear+1)%rear+1)% M = frontM = frontrear20212021年年1212月月2020日日1919時時5151分分#define MAXQSIZE 100 /最大隊列長度最大隊列長度typedef struct QElemType *base; / 動態(tài)分配存儲空間動態(tài)分配存儲空間 int front; / 頭指針，若隊列不空，頭指針，若隊列不空， /

45、指向隊列頭元素指向隊列頭元素 int rear; / 尾指針，若隊列不空，指向尾指針，若隊列不空，指向 / 隊列尾元素隊列尾元素 的下一個位置的下一個位置 SqQueue;20212021年年1212月月2020日日1919時時5151分分 Status InitQueue (SqQueue &Q, int maxsize) / 構(gòu)造一個最大存儲空間為 maxsize 的 / 空循環(huán)隊列 Q Q.base =(QElemType *)malloc (maxsize *sizeof(QElemType); if (!Q.base) exit (OVERFLOW); Q.front = Q

46、.rear = 0; return OK; 20212021年年1212月月2020日日1919時時5151分分Status EnQueue (SqQueue &Q, ElemType e) / 插入元素e為Q的新的隊尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /隊列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;20212021年年1212月月2020日日1919時時5151分分 Status DeQueue (SqQueue &Q, ElemType &e) / 若隊列不空，則刪除Q的隊頭元素， / 用e返回其值，并返回OK; 否則返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;20212021年年1212月