3數據結構與算法北京大學 張銘 棧和隊列

1、數據結構與算法 第3章 棧與 隊列本章由趙海燕主寫北京大學張銘，王騰蛟，趙海燕高等教育出版社，2012. 6?！笆晃濉眹壹壱?guī)劃教材操作受限的線性表棧（Stack）運算只在表的一端進行隊列（Queue）運算只在表的兩端進行3.1 棧后進先出（LastInFirstOut）一種限制訪問端口的線性表棧存儲和刪除元素的順序與元素到達的順序相反也稱為“下推表”棧的主要元素棧頂（top）元素：棧的唯一可訪問元素元素插入棧稱為“入?！被颉皦簵！保╬ush）刪除元素稱為“出?！被颉皬棾觥保╬op）棧底：另一端 棧的示意圖 每次取出（并被刪除）的總是剛壓進的元素，而最先壓入的元素則被放在棧的底部 當棧中沒有

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

3、isEmpty(; / 若棧已空返回真 bool isFull(); / 若棧已滿返回真 ;棧的實現(xiàn)方式順序棧（Array-based Stack）使用向量實現(xiàn)，本質上是順序表的簡化版棧的大小關鍵是確定哪一端作為棧頂鏈式棧（Linked Stack）用單鏈表方式存儲，其中指針的方向是從棧頂向下鏈接 3.1.2 順序棧 template class arrStack : public Stack private: / 棧的順序存儲int mSize;/ 棧中最多可存放的元素個數inttop;/ 棧頂位置，應小于mSizeT *st;/ 存放棧元素的數組public: / 棧的運算的順序實現(xiàn)arr

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

5、棧中已經有maxsize個元素時，如果再做進棧運算，所產生的現(xiàn)象下溢（Underflow）對空棧進行出棧運算時所產生的現(xiàn)象順序棧 若入棧的順序為1,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、棧的順序實現(xiàn)if (top = -1) / 棧為空cout 棧為空，不能執(zhí)行出棧操作 endl; return false;else item = sttop-;/ 返回棧頂元素并修改棧頂指針return true;從棧頂讀取，但不彈出 bool arrStack: top(T & item) / 返回棧頂內容，但不彈出if (top = -1) / ?？誧out 棧為空，不能讀取棧頂元素 endl; return false;else item = sttop;return true; 其他算法 把棧清空void arrStack:clear() top = -1;棧滿時，返回非零值（真值t

7、rue） bool arrStack: isFull() return (top = maxsize-1) ;棧的變種兩個獨立的棧底部相連：雙棧迎面增長哪一種更好些？迎面增長的棧top1top23.1.3 鏈式棧 ki+2 ki+1 ki k0 topdatanext用單鏈表方式存儲指針的方向從棧頂向下鏈接 鏈式棧的創(chuàng)建 template class lnkStack : public Stack private: / 棧的鏈式存儲Link*top;/ 指向棧頂的指針int size;/ 存放元素的個數public: / 棧運算的鏈式實現(xiàn)lnkStack(int defSize) / 構造函數

8、top = NULL;size = 0;lnkStack() / 析構函數clear();壓入棧頂 / 入棧操作的鏈式實現(xiàn)bool lnksStack: push(const T item) Link* tmp = new Link(item, top); top = tmp; size+; return true;自單鏈棧彈出 / 出棧操作的鏈式實現(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;順序棧和鏈式棧的比較時間效率所有操作都只需常數時間順序棧和鏈式棧在時間效率上難分伯仲空間效率順序棧須說明一個固定的長度鏈式棧的長度可變，但增加結構性開銷順序棧和鏈式棧的比較實際應用中，順序棧比鏈式棧用得更廣泛些 順序棧容易根據棧頂位置，進行相對位移，快速定位并讀取棧的內部元素 順序棧讀取內部元素的時間為O(1)，而鏈式棧則需要沿著指針鏈游走，顯然慢些，讀取第k個元素需要時間為O(k) 一般來說，棧不允許“讀取內部元素”，只能在棧頂操作 3.1.4 棧的應用棧的特點：后進先出體現(xiàn)了元素之間的透明性常用來處理具有遞歸結構的數據深度優(yōu)先搜索表達式求值子程序函數調用的管理消除遞歸

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

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

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

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

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

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

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

17、 遞歸定義的計算階乘n!的函數long factorial(long n) if (n = 0)return 1;elsereturn n * factorial( n-1) ; / 遞歸調用遞歸問題求解過程示例：階乘回推： 遞推： 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已知遞歸函數的實現(xiàn)棧的一個最為廣泛的應用也許是用戶所看不到，此即大多數程序設計語言運行環(huán)境都提供的函數調用機制。運行時環(huán)境指的是目標計算機上用來管理存儲器并保存指導執(zhí)行過程所需的信息的寄

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

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

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

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

22、活動記錄計算階乘時的運行棧遞歸算法的非遞歸實現(xiàn)以階乘為例，非遞歸方式建立迭代遞歸轉換為非遞歸以Hanoi塔為例呢？計算階乘n！的循環(huán)迭代程序 / 使用循環(huán)迭代方法，計算階乘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 ; 遞歸轉換為非遞歸的方法機械方法設置一工作棧當前工作記錄設置 t+2個語句標號增加非遞歸入口替換第 i (i = 1, , t)個遞歸規(guī)則所有遞歸出口處增加語句：got

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

24、處label i (1=i=t)： 第i個遞歸返回處3. 增加非遞歸入口/ 入棧S.push(t+1，p1, ，pm，q1，qn);4. 替換第i (i=1,t)個遞歸規(guī)則假設函數體中第i (i=1, , t)個遞歸調用語句為：recf(a1, a2, ,am)；則用以下語句替換：S.push(i, a1, , am)； / 實參進棧goto label 0；.label i： x = S.pop()；/* 退棧，然后根據需要，將x中某些值賦給棧頂的工作記錄S.top () 相當于把引用型參數的值回傳給局部變量 */5. 所有遞歸出口處增加語句 goto label t+1;6.標號為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)和嵌套中的遞歸對于循環(huán)中的遞歸，改寫成等價的goto型循環(huán)對于嵌套遞歸調用譬如，recf ( recf()改為：exmp1 = recf ( );exmp2 = recf (exmp1);exmpk = recf (exmpk-1)然后應用規(guī)則 4 解決8. 優(yōu)化處理經過上述變換所得到的是一個帶goto語句的非遞歸

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

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

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

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

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