數據結構C／C+描述第章 棧和隊列

1、 Data Structures: Chapter 3.1 Data Structures: Chapter 3.2 通常稱，棧和隊列是限定插入插入和刪除刪除只能在表的“端點端點”進行的線性表。棧棧和和隊列隊列是兩種常用的是兩種常用的數據類型數據類型 Data Structures: Chapter 3.33.1 棧棧 棧棧是限定僅能在是限定僅能在表尾表尾一端進行一端進行插入插入、刪除刪除操作的操作的線性表線性表（a1, a2, . , ai -1, ai , ai+1, , an ）插入插入刪除刪除3.1.1 3.1.1 棧的棧的定義定義及基本及基本運算運算 一、什么是棧一、什么是棧 Dat

2、a Structures: Chapter 3.4棧的示意圖棧的示意圖出棧出棧進棧進棧棧的特點棧的特點后進先出后進先出(LIFO表表)第第1個進棧的元素在個進棧的元素在棧底棧底，最后一個進棧的元素在最后一個進棧的元素在棧頂棧頂，第第1個出棧的元素為個出棧的元素為棧頂元素棧頂元素，最后一個出棧的元素為最后一個出棧的元素為棧底元素棧底元素棧頂棧頂棧底棧底an na2 2a1 1二、棧的圖示二、棧的圖示 Data Structures: Chapter 3.5（1 1）初始化操作初始化操作 InitStack(InitStack(&S) S) 功能：功能：構造一個空棧構造一個空棧S S；（2

3、 2）銷毀棧操作銷毀棧操作 DestroyStack(DestroyStack(&S) S) 功能：功能：銷毀一個已存在的棧銷毀一個已存在的棧; ;（3 3）置空棧操作置空棧操作 ClearStack(ClearStack(&S) S) 功能功能：將棧：將棧S S置為空棧置為空棧; ;（4 4）取棧頂元素操作取棧頂元素操作 GetTop(S, GetTop(S, &e) e) 功能功能：取棧頂元素，并用：取棧頂元素，并用e e 返回返回; ;三、三、棧棧的基本操作（的基本操作（1） Data Structures: Chapter 3.6（5 5）進棧操作進棧操作 Pu

4、sh(Push(&S, e) S, e) 功能功能：元素：元素e e進棧進棧; ;（6 6）退棧操作退棧操作 Pop(Pop(&S, S, &e) e) 功能功能：棧頂元素退棧，并用：棧頂元素退棧，并用e e返回返回; ;（7 7）判空操作判空操作 StackEmpty(S) StackEmpty(S) 功能功能：若棧：若棧S S為空，返回為空，返回TrueTrue，否則返回，否則返回False; False; 三、三、棧棧的基本操作的基本操作（2） Data Structures: Chapter 3.7 棧的順序存儲結構，也是利用一組連續(xù)的內存單元依次存放自棧底到棧

5、頂的數據元素數據元素，棧頂元素棧頂元素的位置，的位置，由一個稱為棧頂指針棧頂指針的變量指示 。 棧的順序存貯結構也稱為順序棧。順序棧。一、棧的順序存儲結構一、棧的順序存儲結構及及實現實現 3 3. .1 1.2 .2 棧的棧的順序順序表示與實現表示與實現 與線性表類似，棧也可以用順序結構或鏈與線性表類似，棧也可以用順序結構或鏈式結構存儲。式結構存儲。 Data Structures: Chapter 3.8SqStack:結構類型名；結構類型名；SqStack類型的變量是結構變量。類型的變量是結構變量。base：稱為稱為棧底指針棧底指針，始終指向，始終指向棧底位置棧底位置；top：稱為稱為棧頂

6、指針棧頂指針，約定約定棧頂指針指向棧頂指針指向棧頂元素棧頂元素的的下一個位置下一個位置；Stacksize：用于存放當前已分配的用于存放當前已分配的棧棧的存儲空間的大??；的存儲空間的大?。?defineSTACK_INIT_SIZE100/棧存儲空間的初始分配量棧存儲空間的初始分配量#defineSTACKINCREMENT10/棧存儲空間的分配增量棧存儲空間的分配增量typedefstructSElemType *base;/?？臻g基址便于判斷棧是否為空?？臻g基址便于判斷棧是否為空SElemType *top/棧頂指針棧頂指針intstacksize;/當前分配的?？臻g大小當前分配的?？臻g大

7、小/（以（以sizeof(SElemType)為單位）為單位）SqStack;順序棧的類型定義順序棧的類型定義 Data Structures: Chapter 3.9topbasebasetopbasetopbasetopAABCDEAB空?？諚?A進棧進棧 BCDE進棧，進棧，棧滿棧滿EDC出棧出棧順序棧的操作示例順序棧的操作示例P.58 Data Structures: Chapter 3.10順序棧的順序棧的圖示圖示anaiai-1a2a1 nn-1i-1i-210 100basetopstacksizeS Data Structures: Chapter 3.11 StatusIni

8、tStack(SqStack&S)/構造一個空棧構造一個空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);/為順序棧動態(tài)分配存儲空間為順序棧動態(tài)分配存儲空間if(!S.base)exit(OVERFLOW);/存儲分配失敗存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;/InitStack_Sq（1 1）初始化初始化操作操作順序棧的順序棧的基本操作的實現基本操作的實現 Data Structures: Chapter 3.12StatusDetro

9、yStack(SqStack&S)/銷毀一個已存在的棧銷毀一個已存在的棧If(!S.base)returnERROR;/若棧未建立（尚未分配?？臻g）若棧未建立（尚未分配?？臻g）free(S.base);/回收?？臻g回收?？臻gS.base=S.top=null;S.stacksize=0;returnOK;/DetroyStack_Sq（2 2） 銷毀銷毀棧操作棧操作 Data Structures: Chapter 3.13 StatusClearStack(SqStack&S)/將棧將棧S置為空棧置為空棧If(!S.base)returnERROR;/若棧未建立若棧未建立S.

10、top=S.base;returnOK;/ClearStack（3 3）置置空?？諚２僮鞑僮?Data Structures: Chapter 3.14StatusGetTop(SqStackS,SelemType&e)/若棧不空，則用若棧不空，則用e返回返回S的棧頂元素，并返回的棧頂元素，并返回OK；/否則返回否則返回ERRORif(S.top=S.base)returnERROR;/若棧為空若棧為空e=*(S.top-1);/取棧頂元素至取棧頂元素至ereturnOK;/GetTop_Sq（4 4） 取取棧頂棧頂元素操作元素操作 GetTop Data Structures: Ch

11、apter 3.15StatusPush(SqStack&S,SElemTypee)/將元素將元素e插入棧成為新的棧頂元素插入棧成為新的棧頂元素if(S.top-S.base=S.stacksize)/棧滿，追加存儲空間棧滿，追加存儲空間S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存儲分配失敗存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.to

12、p+=e;/元素元素e插入棧頂，修改棧頂指針插入棧頂，修改棧頂指針returnOK;/Push（5 5） 進棧操作進棧操作 Push Data Structures: Chapter 3.16StatusPop(SqStack&S,SElemType&e)/若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用e返回其值，并返回返回其值，并返回OK；/否則返回否則返回ERRORif(S.top=S.base)returnERROR;/?？諚？誩=*-S.top;/刪除棧頂元素，并修改棧頂指針刪除棧頂元素，并修改棧頂指針returnOK;（6 6） 出棧操作出棧操作 Po

13、p Data Structures: Chapter 3.17棧的鏈式存儲結構，棧的鏈式存儲結構，也稱也稱鏈棧鏈棧，如右圖所示：如右圖所示：DatanextS棧頂棧頂棧底棧底an-1a1an3 3. .1 1. .3 3 棧棧的鏈式表示的鏈式表示及及實現實現 Data Structures: Chapter 3.18鏈式棧圖示鏈式棧圖示說明：說明： 1. 1. 鏈棧鏈?？捎每捎镁€性鏈表線性鏈表表示；表示； 2 2. . 鏈棧的鏈棧的棧頂指針棧頂指針就是鏈表的就是鏈表的頭頭指針指針； 3 3. . 進棧操作進棧操作( (pushpush) )就是在該線性就是在該線性鏈表第一個元素結點之前插入一個

14、鏈表第一個元素結點之前插入一個新結點新結點. . 4. 4. 出棧操作出棧操作( (poppop) )就是刪除鏈表的就是刪除鏈表的第一個元素結點。第一個元素結點。DatanextS棧頂棧頂棧底棧底an-1a1an Data Structures: Chapter 3.193.2 3.2 棧棧的應用舉例的應用舉例例例1 1 數制轉換數制轉換 我們學習過各種數制的轉換問題。我們學習過各種數制的轉換問題。 十十-八進制轉換八進制轉換 十十-二進制轉換等。二進制轉換等。 下面我們設計一程序下面我們設計一程序, ,實現實現十十-八八進制數的自動轉進制數的自動轉換。該程序功能為：換。該程序功能為： 對于輸

15、入的任意一個對于輸入的任意一個非負非負十十進制數，顯示輸出與其進制數，顯示輸出與其等值的等值的八八進制數。進制數。 Data Structures: Chapter 3.20 我們這里介紹的方法基于下列原理：我們這里介紹的方法基于下列原理：N=(Ndiv8)10 8+Nmod8N：十進制數十進制數，div：整除運算整除運算，mod：求余運算求余運算；例：例：(1348)10=2 83+5 82+0 8+4=(2504)8NNdiv8Nmod8134816841682102125202 Data Structures: Chapter 3.21 由上述求解過程可以看出，在由上述求解過程可以看出，

16、在計算過程中計算過程中是是從低從低位到高位順序位到高位順序產生八進制數的各個數位。產生八進制數的各個數位。而而顯示時顯示時按照我們的習慣是從高位在前，低位在按照我們的習慣是從高位在前，低位在后，即按后，即按從高位到低位從高位到低位的順序輸出。的順序輸出。即后計算出的（高）位數先輸出，具有后進先出即后計算出的（高）位數先輸出，具有后進先出的特點。的特點。因此可將計算過程中得到的因此可將計算過程中得到的八進制數八進制數順序順序進棧進棧，按出棧序列按出棧序列打印輸出的數，就是對應的八進制數。打印輸出的數，就是對應的八進制數。 Data Structures: Chapter 3.22例如：例如：（1

17、348)10 = (2504)8 其運算過程如下： NNdiv8Nmod81348 168 4 168 21 0 21 2 5 2 0 2計算順序計算順序輸出順序輸出順序 Data Structures: Chapter 3.23voidconversion()/輸入任意一個非負輸入任意一個非負十十進制整數，輸出與其等值的進制整數，輸出與其等值的八八進制數進制數InitStack(S);/建空棧建空棧scanf(“%d”,&N);/輸入一個輸入一個非負十進制整數非負十進制整數while(N)/N不等于零不等于零循環(huán)循環(huán)Push(S,N%8);/余數余數N%8進棧進棧N=N/8;/輾轉相

18、除輾轉相除while(!StackEmpty(S)/輸出存放在棧中的八制數位輸出存放在棧中的八制數位。Pop(S,e);Printf(“%d”,e); Data Structures: Chapter 3.24例例2 括號匹配的檢驗括號匹配的檢驗假設在表達式中 （）或（ ）等為正確正確的格式， （ ）或（ ）或 ( )均為不正確不正確的格式。則 檢驗括號是否匹配是否匹配的方法可用 “期待的急迫程度”這個概念來描述。 Data Structures: Chapter 3.25分析可能出現的不匹配不匹配的情況:到來的右括弧非所“期待”的;例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7

19、 8到來的是“不速之客”;直到結束，也沒有到來所“期待”的括弧; Data Structures: Chapter 3.26算法的設計思想：算法的設計思想：（1）凡出現左括弧左括弧，則進棧進棧；（2）凡出現右括弧右括弧，首先檢查棧是否空 若棧空?？眨瑒t表明該“右括弧右括弧”多余多余errorerror 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，則“左括弧出棧左括弧出?！?否則表明不匹配不匹配errorerror（3）表達式表達式檢驗檢驗結束時結束時， 若棧空?？眨瑒t表明表達式中匹配正確匹配正確 否則表明“左括弧左括弧”有余有余errorerror Data Structures: Cha

20、pter 3.27Statusmatchpairs(SElemType str)SqStack*S;inttag=1;char*ch,e;/ e/ e存放出棧字符存放出棧字符/tag=1表示表達式中括號正確配對，表示表達式中括號正確配對，tag=0表示不配對表示不配對InitStack(&S);/初始化構造一個空棧初始化構造一個空棧Sch=str;while(*ch!=0)&(tag=1)switch(*ch)/ / 遇到遇到(，或或，將其入棧，將其入棧case(:case:case:Push(S,*ch);break; Data Structures: Chapter 3.2

21、8/遇到遇到)，或或，彈出棧頂字符，彈出棧頂字符case):Pop(S,&e);if(e!=()tag=0;break;/若棧頂不是對應的若棧頂不是對應的(，或或，則置，則置tag為為0；/endofswitchch+; /繼續(xù)判斷下一個字符繼續(xù)判斷下一個字符e=0;/將將e清空，以便存放下一次出棧的字符清空，以便存放下一次出棧的字符/endofwhile/如果棧為空且如果棧為空且tag為為1，則配對成功，則配對成功if(tag=1)&(S-top=S-base)printf(match!n);elseprintf(notmatch!n); Data Structures: C

22、hapter 3.29例3 行編輯程序問題如何實現？如何實現？ 是否是否每接受一個字符即存入存儲器每接受一個字符即存入存儲器 ? Data Structures: Chapter 3.30 設立一個設立一個輸入緩沖區(qū)輸入緩沖區(qū)，用以接受用，用以接受用戶輸入的一行字符，然后逐行存入用戶戶輸入的一行字符，然后逐行存入用戶數據區(qū)數據區(qū); 并假設并假設“#”為為退格符退格符,“”為為退退行符行符。 在用戶在用戶輸入一行輸入一行的過程中，允許用的過程中，允許用戶輸入出差錯，并在發(fā)現有誤時可以及戶輸入出差錯，并在發(fā)現有誤時可以及時更正。時更正。合理的作法是： Data Structures: Chapte

23、r 3.31假設假設從終端從終端接受了這樣兩行字符：接受了這樣兩行字符： whli#ilr#e（s#*s) outputchar(*s=#+);則則實際有效實際有效的是下列兩行：的是下列兩行： while (*s) putchar(*s+); Data Structures: Chapter 3.32 while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break; / 重置S為空棧 default : Push(S, ch); break; ch = getc

24、har( ); / 從終端接收下一個字符 ClearStack(S); / 重置S為空棧 if (ch != EOF) ch = getchar();while (ch != EOF) / EOF為全文結束符為全文結束符將從棧底到棧頂的字符傳送至調用過程的數據區(qū)； Data Structures: Chapter 3.33(1) (1) 問題的提出問題的提出 設計一個小計算器（設計一個小計算器（程序程序），希望從鍵），希望從鍵盤上輸入一個算術表達式（盤上輸入一個算術表達式（由運算符操作數由運算符操作數構成的構成的字符串字符串）后）后, ,在屏幕上顯示表達式的在屏幕上顯示表達式的求值結果。求值結

25、果。 例例4 表達式求值表達式求值 Data Structures: Chapter 3.34(2) (2) 表達式的構成表達式的構成 操作數操作數+ +運算符運算符+ +界符界符（如括號如括號）(3)(3) 表達式的求值：表達式的求值： 例例 5+6 5+6 (1+2)-4(1+2)-4 按照四則運算法則，上述表達式的計算過程為按照四則運算法則，上述表達式的計算過程為： 5+65+6 (1+2)-4(1+2)-4= =5+65+6 3-4 3-4 = = 5+18-4 5+18-4= = 23-4 23-4= =1919 表達式中運算符的運算順序為：表達式中運算符的運算順序為： + + ，

26、， + +， - - 如何確定運算符的如何確定運算符的運算順序運算順序？12341234 Data Structures: Chapter 3.35+ 2 1 -* */ /()#+-*/()# = = (4) (4) 算符間的優(yōu)先關系表算符間的優(yōu)先關系表注：注： 1 1 , ,2 2 是相鄰算符，是相鄰算符， 1 1在在左左， 2 2在在右右 1 1 2 2 表示表示1 1的的優(yōu)先權優(yōu)先權低于低于2 2 P.52P.52 Data Structures: Chapter 3.36( (5 5) ) 算符優(yōu)先算法算符優(yōu)先算法 分析表達式分析表達式5+45+4 (1+2)-6 (1+2)-6 計

27、算過程計算過程： 從左向右掃描表達式：從左向右掃描表達式：遇遇操作數操作數進棧進棧；遇遇運算符號運算符號 j與前面的剛掃描過的運算符與前面的剛掃描過的運算符 i比較比較若若 i j則則 j進棧進棧（已保存的運算符的優(yōu)先關系為已保存的運算符的優(yōu)先關系為 1 2 3 j則說明則說明 i是已掃描算符中優(yōu)先級最高者，是已掃描算符中優(yōu)先級最高者， j出棧，出棧，進行運算；進行運算；若若 i= j若若 i為為（， j為為）， j出棧，出棧，說明括號內的式子已計算完；說明括號內的式子已計算完；若若 i為為#，出棧，出棧，?？?，表達式計算完畢棧空，表達式計算完畢。5+4 (1+2)- 6 進行運算的進行運算的

28、算符算符 i i是當前掃描過的運算符中是當前掃描過的運算符中優(yōu)先級最高者優(yōu)先級最高者，可以利用可以利用兩個棧兩個棧分別保存掃描過程中遇到的分別保存掃描過程中遇到的操作數操作數和和運算符運算符。后面也許有優(yōu)先級后面也許有優(yōu)先級更大的算符更大的算符 Data Structures: Chapter 3.37 建立兩個工作棧。建立兩個工作棧。OPTR棧保存運算符；棧保存運算符；OPND棧棧-保存保存操作數或運算結果。操作數或運算結果。算法算法3.3operandTypeEvaluateExpression()/算術表達式求值的算符優(yōu)先算法。設算術表達式求值的算符優(yōu)先算法。設OPTR和和OPND/分別

29、為運算符棧和運算數棧，分別為運算符棧和運算數棧，OP為運算符集合為運算符集合。InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();While(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)/In(c,OP)是判斷是判斷c是否為運算符的函數是否為運算符的函數 Push(OPND,c);c=getchar();/不是運算符則進不是運算符則進數據棧數據棧OPNDelse Data Structures: Chapter 3.38續(xù)續(xù) switch(Precede(GetTop(OPTR),c)case:/棧頂算符優(yōu)先權

30、高棧頂算符優(yōu)先權高,出棧運算，并將運算結果入棧出棧運算，并將運算結果入棧OPNDPop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch/whilereturnGetTop(OPND);/EvaluateExpression Data Structures: Chapter 3.393.3 3.3 棧與遞歸棧與遞歸1 1什么是遞歸什么是遞歸 遞歸是一個很有用的工具，在數學和程序設計等許遞歸是一個很有用的工具，在數學和程序設計等許多領域中都用到了遞歸。多領域中都用到了遞歸。遞歸概念遞歸概念

31、：一個用一個用自己定義自己自己定義自己的定義的定義, ,稱為稱為遞歸定義遞歸定義。例例 n!= 1n!= 1* *2 2* *3 3* *4 4* * *(n-1)(n-1)* * n n n! n!遞歸定義遞歸定義 n!= 1 n!= 1 當當 n=0 n=0 時時 n!= n!= n n(n-1)!(n-1)! 當當 n0 n0 時時用用(n-1)!定義定義n! Data Structures: Chapter 3.40例例1編寫求解編寫求解階乘階乘n!的遞歸算法的遞歸算法 n!的遞歸定義的遞歸定義：基本項：基本項：n!=1當當n=1遞歸項：遞歸項：n!=n(n-1)!當當n1遞歸算法：遞

32、歸算法：intfact(intn)/算法功能是求解并返回算法功能是求解并返回n的階乘的階乘 If（n=1）return（1）；）；elsereturn（n*fact(n-1)）；）； Data Structures: Chapter 3.41例例2 2 編寫求解編寫求解HanoiHanoi塔問題的遞歸算法塔問題的遞歸算法 有有3個各為個各為X，Y，Z的塔座，在的塔座，在X項上有項上有n個大小不同，依個大小不同，依小到大編號為小到大編號為1，2，n的圓盤。的圓盤。現要求將現要求將X上的上的n個圓盤移至個圓盤移至Z上，并仍以同樣順序疊放，上，并仍以同樣順序疊放，圓盤移動時必須圓盤移動時必須遵守下列

33、原則遵守下列原則：（1）每次）每次移動移動1個個盤子；盤子；（2）圓盤可以放在）圓盤可以放在X，Y，Z中的任一塔座上；中的任一塔座上；（3）任何時刻都）任何時刻都不能不能將較大的圓盤壓放在較小圓盤之上；將較大的圓盤壓放在較小圓盤之上； Data Structures: Chapter 3.42abc321 11213121例例:n=3時圓盤移動的過程如下圖所示時圓盤移動的過程如下圖所示：Y YX XZ Z Data Structures: Chapter 3.43 求解求解Hanoi塔問題的遞歸描述（定義）塔問題的遞歸描述（定義）基本項：基本項：n=1時，將時，將n號圓盤從號圓盤從X移至移至Z

34、；遞歸項：遞歸項：n1時，時，將將X上上1n-1號圓盤移至號圓盤移至Y；將將X上的上的n號圓盤從號圓盤從X移至移至Z;將將Y上上1n-1號圓盤從號圓盤從Y移至移至Z; 將規(guī)模為將規(guī)模為n n的問題的求的問題的求解歸結為規(guī)模為解歸結為規(guī)模為n-1n-1的的問題的求解問題的求解有了問題的遞歸定義，有了問題的遞歸定義，很容易寫出對應的很容易寫出對應的遞歸算法遞歸算法： Data Structures: Chapter 3.44voidhanoi(intn,charx,chary,charz)/將塔座將塔座x上按直徑由小到大，且自上而下編號為上按直徑由小到大，且自上而下編號為1至至n的的n個圓盤按規(guī)則

35、搬到個圓盤按規(guī)則搬到/塔座塔座z上，上，y可用作輔助塔座。可用作輔助塔座。/搬動操作搬動操作move(x,n,z)可定義為可定義為(c是初值為是初值為0的全局變量，對搬動計數的全局變量，對搬動計數)：/printf(“%d.Movedisk%dfrom%cto%cn”,+c,n,x,z);if(n=1)move(x,1,z);/將編號為將編號為1的圓盤從的圓盤從x移動移動zelsehanoi(n-1,x,z,y);/將將x上編號為上編號為1至至n-1的圓盤移到的圓盤移到y,z作輔助塔作輔助塔move(x,n,z);/將編號為將編號為n的圓盤從的圓盤從x移到移到zhanoi(n-1,y,x,z)

36、；/將將y上編號為上編號為1至至n-1的圓盤移到的圓盤移到z,x作輔助塔作輔助塔算法算法3.5Hanoi塔問題塔問題 Data Structures: Chapter 3.453 3.4 .4 隊隊 列列3.4.13.4.1 隊列的定義及基本運算隊列的定義及基本運算 一一 什么是隊列什么是隊列 隊列隊列是限定僅能在是限定僅能在表頭表頭進行進行刪除刪除，表尾表尾進行進行插入插入的線性表。的線性表。（ a1, a2, . , ai -1, ai , ai+1, , an ）插入插入刪除刪除 Data Structures: Chapter 3.46說明：設說明：設（a1,a2,a3,.,an）為一

37、隊列為一隊列(1)表尾稱作表尾稱作隊尾隊尾，表頭稱為，表頭稱為隊頭隊頭；(2)a1為為隊頭隊頭元素，元素，an為為隊尾隊尾元素；元素；(3)在在表尾插入表尾插入元素操作，稱為元素操作，稱為入隊入隊操作；操作；在在表頭刪除表頭刪除元素的操作，稱為元素的操作，稱為出隊出隊操作；操作；(4)元素按元素按a1,a2,a3,.an順序入隊，順序入隊，第第1個個入隊入隊的元素為的元素為a1，最后一個入隊的元素是，最后一個入隊的元素是an；第第1個個出隊出隊的元素為的元素為a1,最后一個出隊的元素是最后一個出隊的元素是an(5)隊列具有隊列具有先進先出先進先出的特點，所以又稱為的特點，所以又稱為先進先出先進

38、先出表（表（FIFO表）表） Data Structures: Chapter 3.47二隊列的基本操作二隊列的基本操作（1）初始化操作）初始化操作InitQueue(&Q)功能：構造一個空隊列功能：構造一個空隊列Q；（2）銷毀操作銷毀操作DestroyQueue(&Q)功能：銷毀已存在隊列功能：銷毀已存在隊列Q；（3）置空操作置空操作ClearQueue(&Q)功能：功能：將隊列將隊列Q置為空隊列；置為空隊列；（4）判空操作）判空操作QueueEmpty(Q)功能：若隊列功能：若隊列Q為空，則返回為空，則返回True，否則返回否則返回False； Data Struc

39、tures: Chapter 3.48 （5）取隊頭元素操作取隊頭元素操作GetHead(Q,&e)功能：取隊頭元素，并用功能：取隊頭元素，并用e返回；返回；（6）入隊操作入隊操作EnQueue(&Q,e)功能：將元素功能：將元素e插入插入Q的隊尾；的隊尾； （7）出隊操作）出隊操作DeQueue(&Q,&e)功能：若隊列不空，則刪除功能：若隊列不空，則刪除Q的隊頭元素，用的隊頭元素，用e返回其值，并返回返回其值，并返回OK，否則返回否則返回ERROR； Data Structures: Chapter 3.493.4.3.4.2 2 隊列的順序表示和實現隊列的

40、順序表示和實現 一、一、 隊列的順序存貯結構隊列的順序存貯結構隊列的隊列的順序存儲順序存儲結構是用一組結構是用一組地址連續(xù)地址連續(xù)的存儲單的存儲單元依次存放隊列中的各個元素，并用指針元依次存放隊列中的各個元素，并用指針front指指向隊頭，指針向隊頭，指針rear指向隊尾指向隊尾 。Q.rearQ.frontJ1J2J3實際上，實際上，front指針始終指向隊指針始終指向隊頭元素，頭元素，rear指針實際上并不指針實際上并不是指向隊尾元素，而是指向隊是指向隊尾元素，而是指向隊尾元素的下一個位置。如圖：尾元素的下一個位置。如圖：隊列的順序存貯結構圖示隊列的順序存貯結構圖示 Data Struct

41、ures: Chapter 3.50#defineMAXSIZE100/最大隊列長度最大隊列長度typedefstructQElemType*base;/初始化時動態(tài)分配初始化時動態(tài)分配存儲空間的存儲空間的基址基址intfront;/隊頭指針，指向隊頭指針，指向隊頭元素隊頭元素intrear;/隊尾指針，指向隊尾指針，指向隊尾隊尾元素的元素的下一個位置下一個位置SqQueue;二、順序隊列的類型定義二、順序隊列的類型定義 Data Structures: Chapter 3.51順序隊列常常會出現順序隊列常常會出現“假溢出假溢出”現象，如現象，如圖所示。雖然隊列中圖所示。雖然隊列中還有一定的存

42、儲空間，還有一定的存儲空間，但因為但因為front指針與指針與rear指針均向同一個指針均向同一個方向移動，導致該隊方向移動，導致該隊列不能再進行入隊操列不能再進行入隊操作。作。rearfrontE ED DC C Data Structures: Chapter 3.52 為了避免“假溢出”，可以這樣規(guī)定，一旦 rear指針（或 front指針）指向了存儲空間的末尾位置，如果此時再進行入隊（或出隊）操作，則將相應的指針平移到數組的起始位置，即是將隊列假想為一個循環(huán)的環(huán)狀空間，我們稱之為循環(huán)循環(huán)隊列隊列。 Data Structures: Chapter 3.53三、循環(huán)隊列操作圖示front

43、rear空隊空隊front=rear是是隊空隊空標志標志3120MAXSIZE=4ArearfrontA進隊進隊B進隊進隊ABrearfrontC進隊進隊ArearfrontBC Data Structures: Chapter 3.54frontrear空隊空隊front=rear是隊空標志是隊空標志BCrearfront3120MAXSIZE=4A A 出隊出隊三、循環(huán)隊列操作圖示隊列中含有隊列中含有3個元素，個元素，rear已經指向存儲空已經指向存儲空間的末端，不能再向間的末端，不能再向上移動上移動ArearfrontBC Data Structures: Chapter 3.55fro

44、ntrear空隊空隊front=rear是隊空標志是隊空標志Crearfrontrearfront3120MAXSIZE=4BCB B 出隊出隊三、循環(huán)隊列操作圖示隊列中含有隊列中含有2個元素個元素 Data Structures: Chapter 3.56CrearfrontDMAXSIZE=4此刻此刻rear已經指向存儲空間的末端已經指向存儲空間的末端若再有元素進隊列，則執(zhí)行語句：若再有元素進隊列，則執(zhí)行語句： rear=(rear+1)% MAXSIZErearfrontC三、循環(huán)隊列操作圖示D元素進隊列，執(zhí)行：元素進隊列，執(zhí)行：rearrear=(rear+1)%=(rear+1)%

45、MAXSIZEMAXSIZE經過計算，經過計算，rear的值為的值為0 Data Structures: Chapter 3.57frontrear空隊空隊front=rear是隊空標志是隊空標志CCrearfrontrearfrontDE3120MAXSIZE=4DE進隊進隊三、循環(huán)隊列操作圖示Rear重新指向存儲重新指向存儲空間的起始位置，空間的起始位置，此刻隊列仍有存儲此刻隊列仍有存儲空間，可以進行進空間，可以進行進隊操作隊操作 Data Structures: Chapter 3.58frontrear空隊空隊front=rear是隊空標志是隊空標志CCrearfrontrearfro

46、ntDEF3120MAXSIZE=4 F進隊進隊，隊滿，隊滿隊滿隊滿與與隊空隊空條件混淆條件混淆ED三、循環(huán)隊列操作圖示 Data Structures: Chapter 3.59frontrear空隊空隊front=rear是隊空標志是隊空標志CrearfrontDEF3120MAXSIZE=4為了區(qū)分隊滿與隊空，規(guī)定為了區(qū)分隊滿與隊空，規(guī)定隊滿條件隊滿條件為為：(rear+1)%MAXQSIZE=front所以隊列中最多能包含的元素個數比實際所以隊列中最多能包含的元素個數比實際空間空間少一個少一個隊滿隊滿三、循環(huán)隊列操作圖示 Data Structures: Chapter 3.60出隊時

47、出隊時應先判應先判-隊是否隊是否空空?隊空隊空條件條件：Q.rear=Q.front 不空，則出隊。不空，則出隊。進隊時進隊時應先判應先判-隊是否隊是否滿滿?隊滿隊滿條件條件：(Q.rear+1)%MAXQSIZE)=Q.front 不滿，則進隊不滿，則進隊。 Data Structures: Chapter 3.61(1)初始化循環(huán)隊初始化循環(huán)隊StatusInitQueue(SqQueue&Q)Q.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;

48、returnOK;四、循環(huán)隊列基本操作的實現Q.base=newQElemTypeMAXSIXE; Data Structures: Chapter 3.62（2）進隊操作進隊操作StatusEnSqQueue(SqQueue&Q,QElemTypee)if(Q.rear+1)%MAXQSIZE)=Q.front)returnERROR;/隊滿隊滿Q.baseQ.rear=e;/ e 入隊入隊Q.rear=(Q.rear+1)%MAXQSIZE);/修改尾指針修改尾指針returnOK;/EnQueue;CrearfrontDE3120CrearfrontDEDrearfront再進隊

49、再進隊 滿滿（上溢）（上溢）再進隊循環(huán)、再進隊循環(huán)、滿滿再進隊循環(huán)、再進隊循環(huán)、不滿不滿DrearfrontSS進隊進隊 Data Structures: Chapter 3.63（3）出隊操作出隊操作P.76StatusDeSqQueue(SqQueue&Q,QElemType&e)if(Q.rear=Q.front)returnERROR;/隊空隊空e=Q.baseQ.front;/取隊首元素取隊首元素Q.front=(Q.front+1)%MAXQSIZE;/出隊出隊returnOK;CrearfrontE出隊出隊不循環(huán)不循環(huán)rearfrontE出隊出隊不循環(huán)不循環(huán)rea

50、rfront隊隊空空 Data Structures: Chapter 3.643.4.3.4.3 3 鏈隊列鏈隊列 隊列的鏈式存儲結構和實現隊列的鏈式存儲結構和實現一、定義一、定義 用鏈表表示的隊列，稱為用鏈表表示的隊列，稱為鏈隊列鏈隊列Q.frontQ.rear空鏈隊列空鏈隊列J1J1Q.frontQ.rear J2J2 非空鏈隊列非空鏈隊列 Data Structures: Chapter 3.65二、鏈隊列的二、鏈隊列的類型定義類型定義typedefstructQNode/鏈隊列鏈隊列結點的類型結點的類型定義定義QElemTypedata;structQNode*next;QNode,

51、*QueuePtr;typedefstruct/鏈隊列鏈隊列表頭結點表頭結點的類型定義的類型定義QueuePtr*front;/隊頭指針，指向鏈表的隊頭指針，指向鏈表的頭結點頭結點QueuePtr*rear;/隊尾指針，指向隊尾指針，指向隊尾結點隊尾結點LinkQueue; Data Structures: Chapter 3.66 設設Q為為LinkQueue類型的變量，類型的變量，Q為鏈隊列的為鏈隊列的表頭結點表頭結點，用于，用于存儲隊列存儲隊列隊頭指針和隊尾指針隊頭指針和隊尾指針。鏈隊列的鏈隊列的表頭結點表頭結點鏈隊列的鏈隊列的頭結點頭結點空鏈隊列空鏈隊列J1J1Q.frontQ.rea

52、r J2J2 非空鏈隊列非空鏈隊列Q.frontQ.rear Data Structures: Chapter 3.67（1）初始化隊操作：初始化隊操作：InitQueue(LinkQueue&Q)StatusInitQueue(LinkQueue&Q)/建建一個空隊列一個空隊列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);/為為鏈隊列的鏈隊列的頭結點頭結點分配空間分配空間if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;三、三、 鏈隊列基本操作的算法鏈隊列基本操作的算法Q.frontQ.rear空鏈隊列空鏈隊列 Data Structures: Chapter 3.68銷毀銷毀隊隊操作操作：DestroyQueue(LinkQueue&Q)StatusDestroyQueue(LinkQu