嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)課件第三章棧和隊(duì)列

1、第3章 棧和隊(duì)列 孫甲霞孫甲霞n教學(xué)目標(biāo)：掌握棧和隊(duì)列的結(jié)構(gòu)特性，熟練掌握棧和教學(xué)目標(biāo)：掌握棧和隊(duì)列的結(jié)構(gòu)特性，熟練掌握棧和隊(duì)列的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)方法。隊(duì)列的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)方法。n教學(xué)重點(diǎn)：棧和隊(duì)列的基本操作教學(xué)重點(diǎn)：棧和隊(duì)列的基本操作n教學(xué)難點(diǎn)：遞歸教學(xué)難點(diǎn)：遞歸n教學(xué)時(shí)數(shù)：教學(xué)時(shí)數(shù)：4n棧和隊(duì)列是特殊的線性表，是操作受限的線性表。和棧和隊(duì)列是特殊的線性表，是操作受限的線性表。和線性表的運(yùn)算規(guī)則不同。線性表的運(yùn)算規(guī)則不同。3.1 棧的定義和特點(diǎn)3.1.1 棧的定義和特點(diǎn)棧的定義和特點(diǎn)棧是棧是限定在表尾進(jìn)行插入刪除操作的線性表限定在表尾進(jìn)行插入刪除操作的線性表。表

2、尾端稱。表尾端稱為棧頂，表頭端稱為棧底。不含元素的空表稱為空棧。為棧頂，表頭端稱為棧底。不含元素的空表稱為空棧。棧棧s=( a1，a2，an)n插入元素到插入元素到棧頂棧頂（即表尾）的操作，稱為（即表尾）的操作，稱為入棧入棧。n從從棧頂棧頂（即表尾）刪除最后一個(gè)元素的操作，稱為（即表尾）刪除最后一個(gè)元素的操作，稱為出棧出棧。n棧的特點(diǎn)：棧的特點(diǎn)：后進(jìn)先出（后進(jìn)先出（LIFO）棧底元素棧底元素棧頂元素棧頂元素3.3 棧的表示和實(shí)現(xiàn)3.3.2、順序棧、順序棧即即采用一組地址連續(xù)的存儲(chǔ)單元采用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。的數(shù)據(jù)元素。basetopa1ba

3、setop空?？諚：泻?個(gè)元素的棧個(gè)元素的棧含有含有n個(gè)元素的棧個(gè)元素的棧top=basetop指向棧頂元素的下一個(gè)位置指向棧頂元素的下一個(gè)位置basetopa1a2a3ann順序棧的表示與實(shí)現(xiàn)順序棧的表示與實(shí)現(xiàn)棧的順序存儲(chǔ)表示：棧的順序存儲(chǔ)表示：#define STACK_INIT_SIZE100#define STACKINCREMENT10typedef struct SElemType *base; /棧底指針，始終指向棧底元素，構(gòu)棧底指針，始終指向棧底元素，構(gòu)造之前和銷毀之后，造之前和銷毀之后，base的值為的值為NULLSElemType*top; /棧頂指針棧頂指針,始終指向

4、棧頂元素的始終指向棧頂元素的下一個(gè)位置下一個(gè)位置intstacksize; /當(dāng)前分配的存儲(chǔ)容量，以元素為當(dāng)前分配的存儲(chǔ)容量，以元素為單位單位SqStack;基本操作1、初始化操作、初始化操作status InitStack(SqStack &S) /構(gòu)造一個(gè)空棧構(gòu)造一個(gè)空棧SS.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) exit(OVERFLOW); /若分配失敗，異常退出若分配失敗，異常退出/否則，初始化棧頂指針否則，初始化棧頂指針top和和stacksizeS.top=S.base

5、;S.stacksize=STACK_INIT_SIZE;return OK; /InitStackS.baseS.top2、取棧頂元素、取棧頂元素status GetTop(SqStack S, SElemType &e)/若棧不空，則用若棧不空，則用e返回棧頂元素，并返回返回棧頂元素，并返回OK，否則返回，否則返回/ERRORif(S.top =S.base) return ERROR;e=*(S.top-1);return OK; /GetTopS.baseS.topa1a2a3anean(S.top-1)3、進(jìn)棧、進(jìn)棧status Push(SqStack &S, SE

6、lemType e)/插入元素插入元素e為新的棧頂元素為新的棧頂元素if(S.top-S.base=S.stacksize) /棧滿的標(biāo)志，棧滿的標(biāo)志，S.top-S.base為棧的長(zhǎng)度為棧的長(zhǎng)度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; /元素元素e進(jìn)棧進(jìn)棧 /PushS.

7、baseS.topa1a2a3ane4、出棧、出棧status Pop(SqStack &S, SElemType &e)/若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用e返回其值，并返回返回其值，并返回/OK，否則返回，否則返回ERRORif(S.top=S.base) return ERROR; /若棧若棧S為空，返為空，返回回ERROR，S.top=S.base為棧空的標(biāo)志為?？盏臉?biāo)志e=*-S.top; /若棧不空，用若棧不空，用e返回其值，并刪除該元素返回其值，并刪除該元素rerurn OK; /PopS.topS.basea1a2a3anean注意n

8、棧的長(zhǎng)度：棧的長(zhǎng)度： S.top-S.basen空棧：空棧：S.top=S.basen棧滿：棧滿：S.top-S.base=S.stacksizenS.top在元素進(jìn)出棧時(shí)改變?cè)谠剡M(jìn)出棧時(shí)改變nS.base只在追加存儲(chǔ)空間時(shí)改變只在追加存儲(chǔ)空間時(shí)改變n3.3.3、鏈棧、鏈棧鏈表插入刪除在表首進(jìn)行比較方便，而棧的操作經(jīng)常是鏈表插入刪除在表首進(jìn)行比較方便，而棧的操作經(jīng)常是在棧頂進(jìn)行，因此以單鏈表的表首表示棧頂，即鏈棧在棧頂進(jìn)行，因此以單鏈表的表首表示棧頂，即鏈棧為限定在鏈表首部進(jìn)行插入、刪除操作的不帶頭結(jié)點(diǎn)為限定在鏈表首部進(jìn)行插入、刪除操作的不帶頭結(jié)點(diǎn)的單鏈表。的單鏈表。類型定義：類型定義：ty

9、pedef struct StackNodeElemType data;struct StackNode *next;StackNode,*LinkStack;n1、初始化、初始化status InitStack(LinkStack &s)/初始化一個(gè)空棧初始化一個(gè)空棧ss=NULL;return OK;n2、入棧、入棧status Push(LinkStack &s, EelmType e)p=(LinkStack)malloc(sizeof(StackNode);p-data=e;p-next=s;/插入表首插入表首s=p;return OK;n3、出棧、出棧status

10、Pop(LinkStack &s, EelmType &e)if(s=NULL) return ERROR;e=s-data;p=s;s=s-next;free(p);return OK;n4、取棧頂元素、取棧頂元素status GetTop(LinkStack s,ElemType &e)/用用e返回棧頂元素的值返回棧頂元素的值if(s=NULL) return ERROR;e=s-data;return OK;練習(xí)例例1、一個(gè)棧的輸入序列是、一個(gè)棧的輸入序列是123456，若在入棧的過程中，若在入棧的過程中允許出棧，則棧的輸出序列允許出棧，則棧的輸出序列435612

11、可能實(shí)現(xiàn)嗎？可能實(shí)現(xiàn)嗎？ 135426的輸出呢？的輸出呢？例例2、一個(gè)棧的輸入序列為、一個(gè)棧的輸入序列為123，若在入棧的過程中允許，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？出棧，則可能得到的出棧序列是什么？判斷的原則：判斷的原則：若進(jìn)棧的順序?yàn)槿暨M(jìn)棧的順序?yàn)閕jk，則出棧的順序不可能是，則出棧的順序不可能是kij。討論：1、為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？、為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？n調(diào)用函數(shù)或子程序非它莫屬；調(diào)用函數(shù)或子程序非它莫屬；n遞歸運(yùn)算的有力工具；遞歸運(yùn)算的有力工具；n用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；n簡(jiǎn)化了程序設(shè)計(jì)的問題。簡(jiǎn)化了程序設(shè)計(jì)

12、的問題。n2、棧和線性表的異同？棧和線性表的異同？邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)運(yùn)算規(guī)則運(yùn)算規(guī)則線性表線性表一對(duì)一一對(duì)一順序表、鏈表順序表、鏈表隨機(jī)存取隨機(jī)存取棧棧一對(duì)一一對(duì)一順序棧、鏈棧順序棧、鏈棧后進(jìn)先出后進(jìn)先出3.4 棧和遞歸n3.4.1 遞歸思想遞歸思想將大問題劃分為若干個(gè)小問題，且小問題的解決方法與將大問題劃分為若干個(gè)小問題，且小問題的解決方法與原問題相同或類似，只是規(guī)模變小了，直到問題的規(guī)原問題相同或類似，只是規(guī)模變小了，直到問題的規(guī)模小到可以直接解決為止。模小到可以直接解決為止。遞歸程序的結(jié)構(gòu)：遞歸程序的結(jié)構(gòu)：l遞歸調(diào)用遞歸調(diào)用l遞歸結(jié)束條件（劃分到最小規(guī)模時(shí)的條件）遞歸結(jié)束條

13、件（劃分到最小規(guī)模時(shí)的條件）l遞歸出口（直接求解的方法）遞歸出口（直接求解的方法）函數(shù)類型函數(shù)類型 p（參數(shù)列表）（參數(shù)列表）if(遞歸結(jié)束條件遞歸結(jié)束條件) 直接求解；直接求解；else p(較小的參數(shù)較小的參數(shù)) ；n例、輸出鏈表中各個(gè)元素。例、輸出鏈表中各個(gè)元素。void Print(LinkList L)if(L=NULL) return;printf(L-data);Print(L-next);n棧與遞歸棧與遞歸函數(shù)調(diào)用過程：函數(shù)調(diào)用過程：1、在棧里為被調(diào)用函數(shù)分配一條記錄，保存所有的、在棧里為被調(diào)用函數(shù)分配一條記錄，保存所有的實(shí)參、局部變量和上一層的返回地址。實(shí)參、局部變量和上一層

14、的返回地址。2、被調(diào)用函數(shù)執(zhí)行結(jié)束后，將刪除棧頂記錄，并轉(zhuǎn)、被調(diào)用函數(shù)執(zhí)行結(jié)束后，將刪除棧頂記錄，并轉(zhuǎn)到返回地址處繼續(xù)執(zhí)行。到返回地址處繼續(xù)執(zhí)行。3、當(dāng)前正在執(zhí)行的函數(shù)的記錄即為棧頂記錄。后調(diào)、當(dāng)前正在執(zhí)行的函數(shù)的記錄即為棧頂記錄。后調(diào)用的函數(shù)先返回。用的函數(shù)先返回。3.4 棧的應(yīng)用舉例3.4.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換將非負(fù)十進(jìn)制整數(shù)將非負(fù)十進(jìn)制整數(shù)N轉(zhuǎn)換成八進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)分析：分析：N除除8取余，直至商為取余，直至商為0，求得的余數(shù)逆序輸出即，求得的余數(shù)逆序輸出即為對(duì)應(yīng)的八進(jìn)制數(shù)。可用棧來保存求得的余數(shù)，出棧為對(duì)應(yīng)的八進(jìn)制數(shù)?？捎脳肀４媲蟮玫挠鄶?shù)，出棧的順序即為對(duì)應(yīng)八進(jìn)制數(shù)的正確位序。的

15、順序即為對(duì)應(yīng)八進(jìn)制數(shù)的正確位序。void conversion()/將輸入的任意一個(gè)非負(fù)十進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)將輸入的任意一個(gè)非負(fù)十進(jìn)制數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)InitStack(S);scanf(N);while(N)Push(S,N%8);N/=8;while(!StackEmpty(S) Pop(s,e);printf(%d,e);/ conversion3.4.2 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn) 假設(shè)表達(dá)式中允許括號(hào)嵌套假設(shè)表達(dá)式中允許括號(hào)嵌套,則檢驗(yàn)括號(hào)是否匹配的方則檢驗(yàn)括號(hào)是否匹配的方法可用法可用“期待的急迫程度期待的急迫程度”這個(gè)概念來描述。例：這個(gè)概念來描述。例： （）（）（）（） （

16、）（ )）（）（）（）（）（）（）（ （）（）（）（） （）（）解題思路：解題思路：n遇到左括號(hào)，進(jìn)棧；遇到左括號(hào)，進(jìn)棧；n遇到右括號(hào)，若棧不空且和棧頂?shù)睦ㄌ?hào)是一對(duì)，則出遇到右括號(hào)，若棧不空且和棧頂?shù)睦ㄌ?hào)是一對(duì)，則出棧；棧；否則，若和棧頂?shù)牟黄ヅ浠驐Ｒ芽栈蛞褵o右括號(hào)但棧否則，若和棧頂?shù)牟黄ヅ浠驐Ｒ芽栈蛞褵o右括號(hào)但棧里還有左括號(hào)，出錯(cuò)里還有左括號(hào)，出錯(cuò)3.4.3 表達(dá)式求值表達(dá)式求值表達(dá)式的形式：表達(dá)式的形式：#a+b*c-d/e#步驟：步驟：n構(gòu)造算符優(yōu)先表構(gòu)造算符優(yōu)先表n寫算法寫算法n#入棧；入棧；n遇到不等于遇到不等于#的字符或棧頂字符不等于的字符或棧頂字符不等于#(都等于都等于#則則結(jié)束

17、結(jié)束)：n若是操作數(shù)，進(jìn)操作數(shù)棧；n若是運(yùn)算符，和棧頂?shù)倪\(yùn)算符比較優(yōu)先級(jí) 優(yōu)先級(jí)高于棧頂運(yùn)算符，進(jìn)運(yùn)算符棧；輸入下一字符 優(yōu)先級(jí)低于棧頂運(yùn)算符，運(yùn)算符出棧，兩操作數(shù)出棧，運(yùn)算后將結(jié)果進(jìn)操作數(shù)棧； 優(yōu)先級(jí)相等，脫括號(hào)，輸入下一字符3.5 隊(duì)列3.5.1 抽象數(shù)據(jù)類型隊(duì)列的定義抽象數(shù)據(jù)類型隊(duì)列的定義 隊(duì)列隊(duì)列(Queue)也是一種運(yùn)算受限的線性表。也是一種運(yùn)算受限的線性表。它只允許它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪允許刪除的一端稱為隊(duì)頭除的一端稱為隊(duì)頭(front)，允許插入的一端稱為隊(duì)尾，允許插入的一端稱為隊(duì)尾(rear)。例如：排隊(duì)購

18、物。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入隊(duì)列例如：排隊(duì)購物。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入隊(duì)列的成員總是先離開隊(duì)列。因此的成員總是先離開隊(duì)列。因此隊(duì)列亦稱作先進(jìn)先出隊(duì)列亦稱作先進(jìn)先出(First In First Out)的線性表，簡(jiǎn)稱的線性表，簡(jiǎn)稱FIFO表。表。空隊(duì)列空隊(duì)列出隊(duì)出隊(duì)入隊(duì)入隊(duì)隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾a1 a2 a3 an 長(zhǎng)度為長(zhǎng)度為n的非空隊(duì)列的非空隊(duì)列隊(duì)列的抽象數(shù)據(jù)定義見課本3.5.2 循環(huán)隊(duì)列循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn)隊(duì)列的順序表示和實(shí)現(xiàn)用一組地址連續(xù)的存儲(chǔ)單元存放從隊(duì)頭到隊(duì)尾的元素。用一組地址連續(xù)的存儲(chǔ)單元存放從隊(duì)頭到隊(duì)尾的元素。n入隊(duì)時(shí)將新元素插入入隊(duì)時(shí)將新元素插入rear所指的位

19、置，然后將隊(duì)尾指針加。所指的位置，然后將隊(duì)尾指針加。n出隊(duì)時(shí)，刪去出隊(duì)時(shí)，刪去front所指的元素，然后將隊(duì)頭指針加并返所指的元素，然后將隊(duì)頭指針加并返回被刪元素?；乇粍h元素。由此可見：由此可見：n當(dāng)當(dāng)front=rear時(shí)，隊(duì)列為空。時(shí)，隊(duì)列為空。n在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而尾指針始終在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而尾指針始終指向隊(duì)尾元素的下一位置。指向隊(duì)尾元素的下一位置。front reara1a2a3a4什么是假溢出？什么是假溢出？在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再插在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再插入新的隊(duì)尾元素，否則就會(huì)溢出，但其實(shí)數(shù)組

20、前段還入新的隊(duì)尾元素，否則就會(huì)溢出，但其實(shí)數(shù)組前段還有空位置，這就叫有空位置，這就叫“假溢出假溢出”。解決假溢出的途徑解決假溢出的途徑采用循環(huán)隊(duì)列采用循環(huán)隊(duì)列隊(duì)空時(shí)：隊(duì)空時(shí)：front=rear隊(duì)滿時(shí)：隊(duì)滿時(shí)：front=rear解決辦法：解決辦法：n約定約定front指向指向rear的下的下一個(gè)位置（環(huán)狀的下一一個(gè)位置（環(huán)狀的下一個(gè)位置）時(shí)為滿，即浪個(gè)位置）時(shí)為滿，即浪費(fèi)費(fèi)1個(gè)元素空間，隊(duì)列最個(gè)元素空間，隊(duì)列最多可有多可有n-1個(gè)元素個(gè)元素n設(shè)一標(biāo)志位表示隊(duì)列是設(shè)一標(biāo)志位表示隊(duì)列是滿還是空滿還是空n用一個(gè)計(jì)數(shù)器記錄隊(duì)列用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的個(gè)數(shù)中元素的個(gè)數(shù)J2 J3J1 J4 J5fr

21、ontrear(1)隊(duì)列的定義：隊(duì)列的定義：#define MAXQSIZE100typedef structQElemtype*base;int front;intrear;SqQueue;隊(duì)空條件隊(duì)空條件 : front = rear (初始化時(shí)：初始化時(shí)：front = rear )隊(duì)滿條件：隊(duì)滿條件： front = (rear+1) % MAXQSIZE 隊(duì)列長(zhǎng)度：隊(duì)列長(zhǎng)度：（rearfront MAXQSIZE ）% MAXQSIZE 循環(huán)隊(duì)列的操作實(shí)現(xiàn)循環(huán)隊(duì)列的操作實(shí)現(xiàn)1）初始化一空隊(duì)列）初始化一空隊(duì)列算法要求：生成一空隊(duì)列算法要求：生成一空隊(duì)列算法操作：為隊(duì)列分配基本容量空間算

22、法操作：為隊(duì)列分配基本容量空間 設(shè)置隊(duì)列為空隊(duì)列，即設(shè)置隊(duì)列為空隊(duì)列，即 front=rear=0算法：算法：Status InitQueue ( SqQueue &Q )/初始化空循環(huán)隊(duì)列初始化空循環(huán)隊(duì)列 q Q.base=(QElemType *)malloc(sizeof(QElemType）*MAXQSIZE) ; /分配空間分配空間 if (!Q.base) exit(OVERFLOW); /失敗，退出程序失敗，退出程序 Q.front =Q.rear=0; /置空隊(duì)列置空隊(duì)列 return OK; /InitQueue;算法說明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素算法說明：向循環(huán)

23、隊(duì)列的隊(duì)尾插入一個(gè)元素分分 析析：(1) 插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿 if ( Q . rear + 1 ) % MAXQSIZE )=Q.front) return ERROR;(2）插入動(dòng)作）插入動(dòng)作 Q.base Q.rear = e; Q.rear = ( Q.rear + 1 ) % MAXQSIZE; 2） 入隊(duì)操作入隊(duì)操作J2 J3J1 J4J5frontrearStatus EnQueue(SqQueue &Q, QElemType e)/向循環(huán)隊(duì)列向循環(huán)隊(duì)列 q 的隊(duì)尾加入一個(gè)元素的隊(duì)尾加入一個(gè)元素 e if ( (Q.rear+1) % M

24、AXQSIZE = = Q.front ) return ERROR ; Q.base Q.rear = e; /存儲(chǔ)存儲(chǔ) Q.rear = ( Q . rear + 1 ) % MAXQSIZE;/指針后移指針后移 return OK; / EnQueue;算法算法J2 J3J1 J4J5frontrear3）出隊(duì)操作）出隊(duì)操作算法說明：刪除隊(duì)頭元素，返回其值算法說明：刪除隊(duì)頭元素，返回其值 e 分分 析：析： （1） 在刪除前應(yīng)當(dāng)判斷隊(duì)列是否空；在刪除前應(yīng)當(dāng)判斷隊(duì)列是否空； if (Q.front = Q.rear ) return ERROR; （2）出隊(duì)動(dòng)作）出隊(duì)動(dòng)作 因?yàn)殛?duì)頭指針因?yàn)?/p>

25、隊(duì)頭指針front指向隊(duì)頭元素的位置，所以：指向隊(duì)頭元素的位置，所以： e = Q.base Q.front ; Q.front = ( Q . front + 1 ) % MAXQSIZE; J2 J3J1 J4J5frontrearStatus DeQueue ( SqQueue &Q, QElemType &e) /若隊(duì)列不空，刪除循環(huán)隊(duì)列若隊(duì)列不空，刪除循環(huán)隊(duì)列 Q 的隊(duì)頭元素，的隊(duì)頭元素， /由由 e 返回其值，并返回返回其值，并返回OK if ( Q.front = = Q.rear ) return ERROR; /隊(duì)列空隊(duì)列空 e = Q.base Q.fron

26、t ; Q.front=(Q.front+1) % MAXQSIZE ; return OK; / DeQueue算法：算法：J2 J3J1 J4J5frontrear4）求隊(duì)列長(zhǎng)度）求隊(duì)列長(zhǎng)度int Queuelength(SqQueue Q)return (Q.rear-Q.front+MAXQSIZE)%MAXSIZE;J2 J3J1 J4J5frontrear(2)隊(duì)列定義：隊(duì)列定義：#defineMAXSIZE100typedef structQelemtype *base;intfront;intrear;intflag;SqQueue;隊(duì)空條件隊(duì)空條件 : front = rea

27、r&flag=0 (初始化時(shí)：初始化時(shí)：front = rear=0,flag=0 )隊(duì)滿條件：隊(duì)滿條件： front = =rear&flag=1隊(duì)列長(zhǎng)度：隊(duì)列長(zhǎng)度：L=（rearfront MAXSIZE ）% MAXSIZE （隊(duì)不滿時(shí)）或（隊(duì)不滿時(shí)）或 MAXSIZE （隊(duì)滿時(shí)）（隊(duì)滿時(shí)）Status InitQueue ( SqQueue &q )/初始化空循環(huán)隊(duì)列初始化空循環(huán)隊(duì)列 q q.base=(QElemType *)malloc(sizeof(QElemType）* MAXSIZE); /分配空間分配空間 if (!q.base) exit(OVER

28、FLOW); /失敗，退出程序失敗，退出程序 q.front=q.rear=0; /置空隊(duì)列置空隊(duì)列q.flag=0; return OK; /InitQueueStatus EnQueue(SqQueue &q, QElemType e) /向循環(huán)隊(duì)列向循環(huán)隊(duì)列 q 的隊(duì)尾加入一個(gè)元素的隊(duì)尾加入一個(gè)元素 e if ( q.rear= = q.front&q.flag=1 ) return ERROR ; q.base q.rear = e; /存儲(chǔ)存儲(chǔ) q.rear = ( q.rear + 1 ) % MAXSIZE; /指針后移指針后移 if(q.rear=q.front

29、) q.flag=1; /插入后隊(duì)列滿，插入后隊(duì)列滿，flag置置1 return OK; / EnQueueStatus DeQueue ( SqQueue &q, QElemType &e) /若隊(duì)列不空，刪除循環(huán)隊(duì)列若隊(duì)列不空，刪除循環(huán)隊(duì)列 q 的隊(duì)頭元素，的隊(duì)頭元素， /由由 e 返回其值，并返回返回其值，并返回OK if (q.front = = q.rear&q.flag=0) return ERROR; /隊(duì)隊(duì)列空列空 e = q.base q.front ; q.front=(q.front+1) % MAXSIZE ; if(q.front = = q

30、.rear ) q.flag=0; return OK; / DeQueuegint Queuelength(SqQueue q)if(q.rear=q.front&q.flag=1) return MAXSIZE;else return (q.rear-q.front+MAXSIZE)%MAXSIZE;3.5.3 鏈隊(duì)列鏈隊(duì)列 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，它是限制僅在表隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，它是限制僅在表頭刪除和表尾插入的單鏈表。頭刪除和表尾插入的單鏈表。由于需要在隊(duì)頭刪除、隊(duì)尾插入，設(shè)頭指針和尾指針。由于需要在隊(duì)頭刪除、隊(duì)尾插入，設(shè)頭指針和尾指針。 Q.frontQ.

31、rear帶頭結(jié)點(diǎn)的空鏈隊(duì)列帶頭結(jié)點(diǎn)的空鏈隊(duì)列 Q.frontQ.rear x 元素元素x入隊(duì)列入隊(duì)列 Q.frontQ.rear x y 元素元素y入隊(duì)列入隊(duì)列 Q.frontQ.rear x y 元素元素x出隊(duì)列出隊(duì)列鏈隊(duì)列的類型鏈隊(duì)列的類型LinkQueue的定義：的定義： typedef struct QNode/隊(duì)列結(jié)點(diǎn)類型隊(duì)列結(jié)點(diǎn)類型 QElemType data; struct QNode *next; QNode, *QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue; /鏈隊(duì)列類型鏈隊(duì)列類型初始化以下基本操

32、作針對(duì)帶頭結(jié)點(diǎn)的隊(duì)列以下基本操作針對(duì)帶頭結(jié)點(diǎn)的隊(duì)列status InitQueue(LinkQueue &Q)/構(gòu)造一個(gè)空隊(duì)列構(gòu)造一個(gè)空隊(duì)列Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next=NULL;return OK; /InitQueue Q.frontQ.rear銷毀隊(duì)列status DestroyQueue(LinkQueue &Q) /銷毀隊(duì)列銷毀隊(duì)列Qwhile(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;/DestroyQueueQ.frontQ.rear y x進(jìn)隊(duì)status EnQueue(LinkQueue &am