3數(shù)據(jù)結(jié)構(gòu)與算法北京大學(xué) 張銘 棧和隊(duì)列

1、數(shù)據(jù)結(jié)構(gòu)與算法 第3章 棧與 隊(duì)列本章由趙海燕主寫北京大學(xué)張銘，王騰蛟，趙海燕高等教育出版社，2012. 6。“十一五”國(guó)家級(jí)規(guī)劃教材操作受限的線性表?xiàng)＃⊿tack）運(yùn)算只在表的一端進(jìn)行隊(duì)列（Queue）運(yùn)算只在表的兩端進(jìn)行3.1 棧后進(jìn)先出（LastInFirstOut）一種限制訪問端口的線性表?xiàng)４鎯?chǔ)和刪除元素的順序與元素到達(dá)的順序相反也稱為“下推表”棧的主要元素棧頂（top）元素：棧的唯一可訪問元素元素插入棧稱為“入?！被颉皦簵！保╬ush）刪除元素稱為“出棧”或“彈出”（pop）棧底：另一端 棧的示意圖 每次取出（并被刪除）的總是剛壓進(jìn)的元素，而最先壓入的元素則被放在棧的底部 當(dāng)棧中沒有

2、元素時(shí)稱為“空?！?k0k1.kn-1棧頂棧底出棧進(jìn)棧棧的主要操作入棧（ push ） 出棧（pop）取棧頂元素（ top ）判斷棧是否為空（ isEmpty ）3.1.1 棧的抽象數(shù)據(jù)類型 template / 棧的元素類型為 Tclass Stack public: / 棧的運(yùn)算集void clear();/ 變?yōu)榭諚?bool push(const T item); / item入棧，成功則返回真，否則返回假 bool pop(T & item);/ 返回棧頂內(nèi)容并彈出，成功返回真，否則返回假 bool top(T& item);/ 返回棧頂內(nèi)容但不彈出，成功返回真，否則返回假bool

3、isEmpty(; / 若棧已空返回真 bool isFull(); / 若棧已滿返回真 ;棧的實(shí)現(xiàn)方式順序棧（Array-based Stack）使用向量實(shí)現(xiàn)，本質(zhì)上是順序表的簡(jiǎn)化版棧的大小關(guān)鍵是確定哪一端作為棧頂鏈?zhǔn)綏＃↙inked Stack）用單鏈表方式存儲(chǔ)，其中指針的方向是從棧頂向下鏈接 3.1.2 順序棧 template class arrStack : public Stack private: / 棧的順序存儲(chǔ)int mSize;/ 棧中最多可存放的元素個(gè)數(shù)inttop;/ 棧頂位置，應(yīng)小于mSizeT *st;/ 存放棧元素的數(shù)組public: / 棧的運(yùn)算的順序?qū)崿F(xiàn)arr

4、Stack(int size) / 創(chuàng)建一個(gè)給定長(zhǎng)度的順序棧實(shí)例mSize = size; top = -1;st = new TmSize;arrStack() / 創(chuàng)建一個(gè)順序棧的實(shí)例 top = -1;arrStack() / 析構(gòu)函數(shù)delete st;void clear() / 清空棧內(nèi)容top = -1;順序棧 按壓入先后次序，最后壓入的元素編號(hào)為4，然后依次為3,2,1 123top棧底4順序棧示意012345s.top = -1s.top = 0A0B1C2D3E4F5s.top = 5A012345A0B1C2D345s.top = 3順序棧的溢出上溢（Overflow）當(dāng)

5、棧中已經(jīng)有maxsize個(gè)元素時(shí)，如果再做進(jìn)棧運(yùn)算，所產(chǎn)生的現(xiàn)象下溢（Underflow）對(duì)空棧進(jìn)行出棧運(yùn)算時(shí)所產(chǎn)生的現(xiàn)象順序棧 若入棧的順序?yàn)?,2,3,4的話，則出棧的順序可以有哪些? 12341243132413421423143221342143壓入棧頂 bool arrStack:push(const T item) if (top = mSize-1) / 棧已滿 cout 棧滿溢出 endl;return false;else / 新元素入棧并修改棧頂指針st+top = item;return true;從棧頂彈出 bool arrStack:pop(T & item) / 出

6、棧的順序?qū)崿F(xiàn)if (top = -1) / 棧為空cout 棧為空，不能執(zhí)行出棧操作 endl; return false;else item = sttop-;/ 返回棧頂元素并修改棧頂指針return true;從棧頂讀取，但不彈出 bool arrStack: top(T & item) / 返回棧頂內(nèi)容，但不彈出if (top = -1) / 棧空cout 棧為空，不能讀取棧頂元素 endl; return false;else item = sttop;return true; 其他算法 把棧清空void arrStack:clear() top = -1;棧滿時(shí)，返回非零值（真值t

7、rue） bool arrStack: isFull() return (top = maxsize-1) ;棧的變種兩個(gè)獨(dú)立的棧底部相連：雙棧迎面增長(zhǎng)哪一種更好些？迎面增長(zhǎng)的棧top1top23.1.3 鏈?zhǔn)綏?ki+2 ki+1 ki k0 topdatanext用單鏈表方式存儲(chǔ)指針的方向從棧頂向下鏈接 鏈?zhǔn)綏５膭?chuàng)建 template class lnkStack : public Stack private: / 棧的鏈?zhǔn)酱鎯?chǔ)Link*top;/ 指向棧頂?shù)闹羔榠nt size;/ 存放元素的個(gè)數(shù)public: / 棧運(yùn)算的鏈?zhǔn)綄?shí)現(xiàn)lnkStack(int defSize) / 構(gòu)造函數(shù)

8、top = NULL;size = 0;lnkStack() / 析構(gòu)函數(shù)clear();壓入棧頂 / 入棧操作的鏈?zhǔn)綄?shí)現(xiàn)bool lnksStack: push(const T item) Link* tmp = new Link(item, top); top = tmp; size+; return true;自單鏈棧彈出 / 出棧操作的鏈?zhǔn)綄?shí)現(xiàn)bool lnkStack: pop(T& item) Link *tmp; if (size = 0) cout 棧為空，不能執(zhí)行出棧操作data; tmp = top-next; delete top; top = tmp; size-; r

9、eturn true;順序棧和鏈?zhǔn)綏５谋容^時(shí)間效率所有操作都只需常數(shù)時(shí)間順序棧和鏈?zhǔn)綏Ｔ跁r(shí)間效率上難分伯仲空間效率順序棧須說明一個(gè)固定的長(zhǎng)度鏈?zhǔn)綏５拈L(zhǎng)度可變，但增加結(jié)構(gòu)性開銷順序棧和鏈?zhǔn)綏５谋容^實(shí)際應(yīng)用中，順序棧比鏈?zhǔn)綏Ｓ玫酶鼜V泛些 順序棧容易根據(jù)棧頂位置，進(jìn)行相對(duì)位移，快速定位并讀取棧的內(nèi)部元素 順序棧讀取內(nèi)部元素的時(shí)間為O(1)，而鏈?zhǔn)綏t需要沿著指針鏈游走，顯然慢些，讀取第k個(gè)元素需要時(shí)間為O(k) 一般來說，棧不允許“讀取內(nèi)部元素”，只能在棧頂操作 3.1.4 棧的應(yīng)用棧的特點(diǎn)：后進(jìn)先出體現(xiàn)了元素之間的透明性常用來處理具有遞歸結(jié)構(gòu)的數(shù)據(jù)深度優(yōu)先搜索表達(dá)式求值子程序函數(shù)調(diào)用的管理消除遞歸

10、計(jì)算表達(dá)式的值表達(dá)式的遞歸定義基本符號(hào)集：0，1，9，+，-，*，/，（，） 語法成分集： , , , , 語法公式集 中綴表達(dá)式 23+(34*45)/(5+6+7)后綴表達(dá)式 23 34 45 * 5 6 + 7 + / +后綴表達(dá)式求值 中綴表達(dá)法的語法公式 = + | | = * | / | = | （ ） = | = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 中綴表達(dá)的算術(shù)表達(dá)式的計(jì)算次序 先執(zhí)行括號(hào)內(nèi)的計(jì)算，后執(zhí)行括號(hào)外的計(jì)算。在具有多層括號(hào)時(shí)，按層次反復(fù)地脫括號(hào)，左右括號(hào)必須配對(duì)在無括號(hào)或同層括號(hào)時(shí)，先乘(*) 、除()，后加(+)、減(-)在同

11、一個(gè)層次，若有多個(gè)乘除（*、）或加減 (+，-)的運(yùn)算，那就按自左至右順序執(zhí)行 23+(34*45)/(5+6+7) = ? 計(jì)算特點(diǎn)？后綴表達(dá)式 = + | - | = * | / | = = | = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 后綴表達(dá)式的計(jì)算 23 34 45 * 5 6 + 7 + / + =？ 計(jì)算特點(diǎn)？中綴和后綴表達(dá)式的主要異同？23+34*45/(5+6+7) = ?23 34 45 * 5 6 + 7 + / + =？從左到右掃描中綴表達(dá)式。用棧存放表達(dá)式中的操作數(shù)、開括號(hào)以及在此開括號(hào)后暫不確定計(jì)算次序的其他符號(hào)：(1) 當(dāng)輸入

12、的是操作數(shù)時(shí)，直接輸出到后綴表達(dá)式序列；(2) 當(dāng)遇到開括號(hào)時(shí)，把它壓入棧；(3) 當(dāng)輸入遇到閉括號(hào)時(shí)，先判斷棧是否為空，若為空（括號(hào)不匹配），應(yīng)該作為錯(cuò)誤異常處理，清棧退出。 若非空，則把棧中元素依次彈出，直到遇到第一個(gè)開括號(hào)為止，將彈出的元素輸出到后綴表達(dá)式序列中（彈出的開括號(hào)不放到序列中），若沒有遇到開括號(hào)，說明括號(hào)不配對(duì)，做異常處理，清棧退出。 中綴表達(dá)式后綴表達(dá)式中綴表達(dá)式后綴表達(dá)式從左到右掃描中綴表達(dá)式。用棧存放表達(dá)式中的操作數(shù)、開括號(hào)以及在此開括號(hào)后暫不確定計(jì)算次序的其他符號(hào)：（4）當(dāng)輸入為運(yùn)算符op（ 四則運(yùn)算 + - * / 之一）時(shí)（a）循環(huán) 當(dāng)（棧非空 and 棧頂不是開

13、括號(hào) and 棧頂運(yùn)算符的優(yōu)先級(jí)不低于輸入的運(yùn)算符的優(yōu)先級(jí)）時(shí)，反復(fù)操作 將棧頂元素彈出，放到后綴表達(dá)式序列中；（b）將輸入的運(yùn)算符壓入棧內(nèi)；（5）最后，當(dāng)中綴表達(dá)式的符號(hào)全部讀入時(shí)，若棧內(nèi)仍有元素，把它們?nèi)恳来螐棾?，放在后綴表達(dá)式序列的尾部。若彈出的元素遇到開括號(hào)，則說明括號(hào)不匹配，做異常處理，清棧退出。中綴表達(dá)式后綴表達(dá)式待處理中綴表達(dá)式： 輸出后綴表達(dá)式：棧的狀態(tài)23/45567*()()34后綴表達(dá)式求值 循環(huán)：依次順序讀入表達(dá)式的符號(hào)序列（假設(shè)以作為輸入序列的結(jié)束），并根據(jù)讀入的元素符號(hào)逐一分析：1.當(dāng)遇到的是一個(gè)操作數(shù)，則壓入棧頂；2.當(dāng)遇到的是一個(gè)運(yùn)算符, 就從棧中兩次取出棧頂

14、，按照運(yùn)算符對(duì)這兩個(gè)操作數(shù)進(jìn)行計(jì)算。然后將計(jì)算結(jié)果壓入棧頂如此繼續(xù)，直到遇到符號(hào), 這時(shí)棧頂?shù)闹稻褪禽斎氡磉_(dá)式的值 后綴表達(dá)式求值待處理后綴表達(dá)式：23/45567*34棧狀態(tài)的變化1530111885108后綴表達(dá)式求值中綴表達(dá)式：運(yùn)算符在中間需要括號(hào)改變優(yōu)先級(jí) 4* x * (2 * x + a) c后綴表達(dá)式運(yùn)算符在后面完全不需要括號(hào)4 x * 2 x * a + * c 后綴計(jì)算器的類定義/ Class Declaration 類的說明 (參見算法3.5)class Calculator private: Stack s;/ 這個(gè)棧用于壓入保存操作數(shù) / 從棧頂彈出兩個(gè)操作數(shù)opd1和

15、opd2bool GetTwoOperands(double& opd1,double& opd2); / 取兩個(gè)操作數(shù)，并按op對(duì)兩個(gè)操作數(shù)進(jìn)行計(jì)算void Compute(char op); public: Calculator(void) ;/ 創(chuàng)建計(jì)算器實(shí)例，開辟一個(gè)空棧 void Run(void);/ 讀入后綴表達(dá)式，遇到符號(hào)=時(shí)，求值計(jì)算結(jié)束 void Clear(void); /清除計(jì)算器，為下一次計(jì)算做準(zhǔn)備 ;3.1.5 棧與遞歸函數(shù)的遞歸定義 主程序和子程序的參數(shù)傳遞 棧在實(shí)現(xiàn)函數(shù)遞歸調(diào)用中所發(fā)揮的作用 遞歸作為數(shù)學(xué)和計(jì)算機(jī)科學(xué)的基本概念，遞歸是解決復(fù)雜問題的一個(gè)有力手段符

16、合人類解決問題的思維方式，遞歸能夠描述和解決很多問題，為此許多程序設(shè)計(jì)語言都提供了遞歸的機(jī)制而計(jì)算機(jī)則只能按照指令集來順序地執(zhí)行。計(jì)算機(jī)內(nèi)（編譯程序）是如何將程序設(shè)計(jì)中的便于人類理解的遞歸程序轉(zhuǎn)換為計(jì)算機(jī)可處理的非遞歸程序的? 遞歸定義階乘n！函數(shù) 階乘n！的遞歸定義如下： 遞歸定義由兩部分組成：遞歸基礎(chǔ)/出口遞歸規(guī)則 計(jì)算階乘n！的循環(huán)迭代程序 / 使用循環(huán)迭代方法，計(jì)算階乘n!的程序long factorial(long n) int m = 1;int i ;if (n0)for ( i = 1; i = n; i+ )m = m * i ;return m ; 計(jì)算階乘n！的遞歸程序/

17、 遞歸定義的計(jì)算階乘n!的函數(shù)long factorial(long n) if (n = 0)return 1;elsereturn n * factorial( n-1) ; / 遞歸調(diào)用遞歸問題求解過程示例：階乘回推： 遞推： 4！= 4*3！ 4！= 4*3! = 24 3！= 3*2！ 3！= 3*2！= 6 2！= 2*1！ 2！= 2*1！= 2 1！= 1*0！ 1！=1*0！= 1 0！= 1已知遞歸函數(shù)的實(shí)現(xiàn)棧的一個(gè)最為廣泛的應(yīng)用也許是用戶所看不到，此即大多數(shù)程序設(shè)計(jì)語言運(yùn)行環(huán)境都提供的函數(shù)調(diào)用機(jī)制。運(yùn)行時(shí)環(huán)境指的是目標(biāo)計(jì)算機(jī)上用來管理存儲(chǔ)器并保存指導(dǎo)執(zhí)行過程所需的信息的寄

18、存器及存儲(chǔ)器的結(jié)構(gòu)。 函數(shù)調(diào)用在非遞歸情況下，數(shù)據(jù)區(qū)的分配可以在程序運(yùn)行前進(jìn)行，一直到整個(gè)程序運(yùn)行結(jié)束才釋放，這種分配稱為靜態(tài)分配。采用靜態(tài)分配時(shí)，函數(shù)的調(diào)用和返回處理比較簡(jiǎn)單，不需要每次分配和釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)在遞歸調(diào)用的情況下，被調(diào)函數(shù)的局部變量不能靜態(tài)地分配某些固定單元，而必須每調(diào)用一次就分配一份，以存放當(dāng)前所使用的數(shù)據(jù)，當(dāng)返回時(shí)隨即釋放。故其存儲(chǔ)分配只能在執(zhí)行調(diào)用時(shí)才能進(jìn)行，即所謂的動(dòng)態(tài)分配：在內(nèi)存中開辟一個(gè)稱為運(yùn)行棧（runtime stack）的足夠大的動(dòng)態(tài)區(qū)函數(shù)運(yùn)行時(shí)的動(dòng)態(tài)存儲(chǔ)分配用作動(dòng)態(tài)數(shù)據(jù)分配的存儲(chǔ)區(qū)可按多種方式組織。典型的組織是將這個(gè)存儲(chǔ)器分為棧（stack）區(qū)域和堆（h

19、eap）區(qū)域棧區(qū)域用于分配發(fā)生在后進(jìn)先出LIFO風(fēng)格中的數(shù)據(jù)（諸如函數(shù)的調(diào)用）堆區(qū)域則用于不符合LIFO（諸如指針的分配）的動(dòng)態(tài)分配運(yùn)行棧中的活動(dòng)記錄函數(shù)活動(dòng)記錄（activation record）是動(dòng)態(tài)存儲(chǔ)分配中一個(gè)重要的單元當(dāng)調(diào)用或激活函數(shù)時(shí)，函數(shù)的活動(dòng)記錄包含了為其局部數(shù)據(jù)分配的存儲(chǔ)空間 運(yùn)行棧中的活動(dòng)記錄運(yùn)行棧隨著程序執(zhí)行時(shí)發(fā)生的調(diào)用鏈或生長(zhǎng)或縮小每次調(diào)用時(shí)，執(zhí)行進(jìn)棧操作，把被調(diào)函數(shù)的活動(dòng)信息壓入棧中，即當(dāng)進(jìn)行一個(gè)新的函數(shù)調(diào)用時(shí)，每個(gè)新的活動(dòng)記錄都分配在棧的頂部而在每次從函數(shù)返回時(shí)，執(zhí)行出棧操作，釋放本次的活動(dòng)記錄，恢復(fù)到上次調(diào)用所分配的數(shù)據(jù)區(qū)中被調(diào)函數(shù)中變量地址全部采用相對(duì)于棧頂?shù)?/p>

20、相對(duì)地址來表示一個(gè)函數(shù)在運(yùn)行棧上可以有若干不同的活動(dòng)記錄，每個(gè)都代表了一個(gè)不同的調(diào)用對(duì)于遞歸函數(shù)來說，遞歸的深度就決定了其在運(yùn)行棧中活動(dòng)記錄的數(shù)目。當(dāng)函數(shù)遞歸調(diào)用時(shí)，函數(shù)體的同一個(gè)局部變量，在不同的遞歸層次被分配給不同的存儲(chǔ)空間，放在內(nèi)部棧的不同位置函數(shù)調(diào)用與返回處理調(diào)用可以分解成以下三步來實(shí)現(xiàn)：調(diào)用函數(shù)發(fā)送調(diào)用信息。調(diào)用信息包括調(diào)用方要傳送給被調(diào)方的信息，諸如實(shí)參、返回地址等。分配被調(diào)方需要的局部數(shù)據(jù)區(qū)，用來存放被調(diào)方定義的局部變量、形參變量（存放實(shí)參）、返回地址等，并接受調(diào)用方傳送來的調(diào)用信息。調(diào)用方暫停，把計(jì)算控制轉(zhuǎn)到被調(diào)方，亦即自動(dòng)轉(zhuǎn)移到被調(diào)用的函數(shù)的程入口。當(dāng)被調(diào)方結(jié)束運(yùn)行，返回到調(diào)

21、用方時(shí)，其返回處理一般也分解為三步進(jìn)行：傳送返回信息，包括被調(diào)方要傳回給調(diào)用方的信息，諸如計(jì)算結(jié)果等。釋放分配給被調(diào)方的數(shù)據(jù)區(qū)。按返回地址把控制轉(zhuǎn)回調(diào)用方。遞歸時(shí)運(yùn)行棧的變化示例以階乘為例：#include main() int x;scanf(“%d”, &x)；printf(“%dn”, factorial(4);計(jì)算階乘時(shí)的運(yùn)行棧n: 4控制鏈返回地址第1次調(diào)用factorial時(shí)的活動(dòng)記錄x: 4主程序main的活動(dòng)記錄棧生長(zhǎng)方向棧生長(zhǎng)方向n: 4控制鏈返回地址第1次調(diào)用factorial時(shí)的活動(dòng)記錄x: 4主程序main的活動(dòng)記錄n: 3控制鏈返回地址第2次調(diào)用factorial時(shí)的

22、活動(dòng)記錄計(jì)算階乘時(shí)的運(yùn)行棧遞歸算法的非遞歸實(shí)現(xiàn)以階乘為例，非遞歸方式建立迭代遞歸轉(zhuǎn)換為非遞歸以Hanoi塔為例呢？計(jì)算階乘n！的循環(huán)迭代程序 / 使用循環(huán)迭代方法，計(jì)算階乘n!的程序long factorial(long n) int m = 1;int i ;if (n0)for ( i = 1; i 0) / ?s.push(n-);while (!isEmpty(s) / ?m *= s.pop(s);return m ; 遞歸轉(zhuǎn)換為非遞歸的方法機(jī)械方法設(shè)置一工作棧當(dāng)前工作記錄設(shè)置 t+2個(gè)語句標(biāo)號(hào)增加非遞歸入口替換第 i (i = 1, , t)個(gè)遞歸規(guī)則所有遞歸出口處增加語句：got

23、o label t+1;標(biāo)號(hào)為t+1的語句的格式改寫循環(huán)和嵌套中的遞歸優(yōu)化處理1. 設(shè)置一工作棧記錄當(dāng)前工作記錄在函數(shù)中出現(xiàn)的所有參數(shù)和局部變量都必須用棧中相應(yīng)的數(shù)據(jù)成員代替返回語句標(biāo)號(hào)域 (t+2個(gè)數(shù)值)函數(shù)參數(shù)(值參、引用型)局部變量 typedef struct elem / 棧數(shù)據(jù)元素類型int rd; / 返回語句的標(biāo)號(hào)Datatypeofp1 p1; / 函數(shù)參數(shù) Datatypeofpm pm;Datatypeofq1 q1; / 局部變量 Datatypeofqn qn; ELEM;2. 設(shè)置t+2個(gè)語句標(biāo)號(hào)label 0 ：第一個(gè)可執(zhí)行語句label t+1 ：設(shè)在函數(shù)體結(jié)束

24、處label i (1=i=t)： 第i個(gè)遞歸返回處3. 增加非遞歸入口/ 入棧S.push(t+1，p1, ，pm，q1，qn);4. 替換第i (i=1,t)個(gè)遞歸規(guī)則假設(shè)函數(shù)體中第i (i=1, , t)個(gè)遞歸調(diào)用語句為：recf(a1, a2, ,am)；則用以下語句替換：S.push(i, a1, , am)； / 實(shí)參進(jìn)棧goto label 0；.label i： x = S.pop()；/* 退棧，然后根據(jù)需要，將x中某些值賦給棧頂?shù)墓ぷ饔涗汼.top () 相當(dāng)于把引用型參數(shù)的值回傳給局部變量 */5. 所有遞歸出口處增加語句 goto label t+1;6.標(biāo)號(hào)為t+1的

25、語句switch (x=S.top ().rd) case 0 : goto label 0;break;case 1 : goto label 1;break;.case t+1 : item = S.pop()/ 返回處理break;default : break;7. 改寫循環(huán)和嵌套中的遞歸對(duì)于循環(huán)中的遞歸，改寫成等價(jià)的goto型循環(huán)對(duì)于嵌套遞歸調(diào)用譬如，recf ( recf()改為：exmp1 = recf ( );exmp2 = recf (exmp1);exmpk = recf (exmpk-1)然后應(yīng)用規(guī)則 4 解決8. 優(yōu)化處理經(jīng)過上述變換所得到的是一個(gè)帶goto語句的非遞歸

26、程序。可以進(jìn)一步優(yōu)化 去掉冗余進(jìn)棧/出棧 根據(jù)流程圖找出相應(yīng)的循環(huán)結(jié)構(gòu)，從而消去goto語句遞歸的非遞歸實(shí)現(xiàn)請(qǐng)大家思考，用機(jī)械的轉(zhuǎn)換方法階乘函數(shù)2階斐波那契函數(shù)f0=0, f1=1, fn = fn-1+ fn-2Hanoi塔3.2 隊(duì)列先進(jìn)先出（FirstInFirstOut）限制訪問點(diǎn)的線性表 按照到達(dá)的順序來釋放元素所有的插入在表的一端進(jìn)行，所有的刪除都在表的另一端進(jìn)行主要元素隊(duì)頭（front）隊(duì)尾（rear）隊(duì)列示意圖隊(duì)頭隊(duì)尾進(jìn)隊(duì)出隊(duì)k0 k1 k2 . kn-1隊(duì)列的主要操作入隊(duì)列（enQueue）出隊(duì)列（deQueue）取隊(duì)首元素（getFront）判斷隊(duì)列是否為空（isEmpty

27、）3.2.1 隊(duì)列的抽象數(shù)據(jù)類型template class Queue public: / 隊(duì)列的運(yùn)算集void clear();/ 變?yōu)榭贞?duì)列bool enQueue(const T item); / 將item插入隊(duì)尾，成功則返回真，否則返回假bool deQueue(T& item); / 返回隊(duì)頭元素并將其從隊(duì)列中刪除，成功則返回真bool getFront(T& item); / 返回隊(duì)頭元素，但不刪除，成功則返回真bool isEmpty(); / 返回真，若隊(duì)列已空bool isFull(); / 返回真，若隊(duì)列已滿;隊(duì)列的實(shí)現(xiàn)方式順序隊(duì)列關(guān)鍵是如何防止假溢出鏈?zhǔn)疥?duì)列用單鏈表方

28、式存儲(chǔ)，隊(duì)列中每個(gè)元素對(duì)于鏈表中的一個(gè)結(jié)點(diǎn)3.2.2 順序隊(duì)列 使用順序表來實(shí)現(xiàn)隊(duì)列用向量存儲(chǔ)隊(duì)列元素，并用兩個(gè)變量分別指向隊(duì)列的前端和尾端 76543210Q.frontQ.reark0k1k2Q.frontQ.rearQ.rearQ.frontk5隊(duì)列空再進(jìn)隊(duì)一個(gè)元素如何？隊(duì)列示意：普通k4隊(duì)列的溢出上溢當(dāng)隊(duì)列滿時(shí)，再做進(jìn)隊(duì)操作，所出現(xiàn)的現(xiàn)象下溢當(dāng)隊(duì)列空時(shí)，再做刪除操作，所出現(xiàn)的現(xiàn)象假溢出當(dāng) rear = MAXNUM時(shí)，再作插入運(yùn)算就會(huì)產(chǎn)生溢出，如果這時(shí)隊(duì)列的前端還有許多空的（可用的）位置，這種現(xiàn)象稱為假溢出k4k5k6Q.frontQ.rearQ.rearQ.frontk6k5隊(duì)列滿隊(duì)

29、列示意：環(huán)形k0k1k2k3Q.rearQ.front隊(duì)列空k4Q.rearQ.frontk1k2k7k6k5k4k3Q.frontQ.rear空隊(duì)列隊(duì)列滿，判斷(Q.rear+1) = Q.front隊(duì)列示意：環(huán)形順序隊(duì)列的類定義 class arrQueue: public Queue private: int mSize; / 存放隊(duì)列的數(shù)組的大小int front;/ 表示隊(duì)頭所在位置的下標(biāo)int rear;/ 表示隊(duì)尾所在位置的下標(biāo)T *qu;/ 存放類型為T的隊(duì)列元素的數(shù)組public: / 隊(duì)列的運(yùn)算集 arrQueue(int size) / 創(chuàng)建隊(duì)列的實(shí)例mSize = si

30、ze +1; / 浪費(fèi)一個(gè)存儲(chǔ)空間，以區(qū)別隊(duì)列空和隊(duì)列滿qu = new T mSize;front = rear = 0; arrQueue() / 消除該實(shí)例，并釋放其空間delete qu;新元素插入隊(duì)列尾端1234frontrear1234frontrear5插入5到隊(duì)列中隊(duì)列的插入bool arrQueue : enQueue(const T item) / item入隊(duì)，插入隊(duì)尾if (rear + 1 ) % mSize) = front) cout 隊(duì)列已滿，溢出 endl;return false;qurear = item;rear = (rear +1) % mSize; / 循環(huán)后繼return true;從隊(duì)列前端取出/刪除bool arrQueue : deQueue(T& item) / 返回隊(duì)頭元素并從隊(duì)列中刪除if ( front = rear) cout 隊(duì)列為空 endl;return false;item = qufront;front = (front +1) % mSize;return true; 隊(duì)列的運(yùn)行示意圖frontrearfrontrear1234frontrearfrontrear1隊(duì)列的運(yùn)行示意圖