數(shù)據(jù)結(jié)構(gòu)（從概念到算法）課件

第3章棧與隊列01020304目錄CONTENTS棧隊列應(yīng)用實例本章小結(jié)01PART棧3.1.1棧的基本概念棧是限定在表尾做插入、刪除操作的線性表。向棧中插入元素叫作進棧，從棧中刪除元素叫作出棧，棧的表頭叫作棧底，棧的表尾叫作棧頂。為了明晰棧底和棧頂?shù)母拍?，通常使用“井”狀圖形表示一個棧。進棧：向棧中插入一個元素。其也稱為入棧、推入、壓入、push。出棧：從棧刪除一個元素。其也稱為退棧、上托、彈出、pop。棧頂：允許插入、刪除元素的一端（表尾）。棧頂元素：處在棧頂位置的元素（表尾元素）。棧底：表中不允許插入、刪除元素的一端（表頭）?？諚＃翰缓氐臈?。棧中元素的進出原則：“后進先出”（Last

In

First

Out）。棧的別名：“后進先出”表、LIFO

表、反轉(zhuǎn)存儲器、堆棧。棧3.1.2棧的抽象數(shù)據(jù)類型棧3.1.3棧的操作特性下面以火車調(diào)度站為例來理解棧的操作特性。假定火車調(diào)度站滿足棧的插入、刪除規(guī)則，列車只能在一端進站、出站，現(xiàn)有3輛列車

A、B、C依次進入火車調(diào)度站，那么列車A、B、C的出站順序會有下面幾種不同組合：棧3.1.3棧的操作特性第一種組合：輸入順序為A,B,C，產(chǎn)生輸出為A,B,C。其過程為：A進?！鶤出棧→B進?！鶥出棧→C進棧→C出棧。在此進、出棧順序下，列車出站順序（棧的輸出序列）即為A,B,C。棧3.1.3棧的操作特性第二種組合：輸入順序為A,B,C，產(chǎn)生輸出為C,B,A。其過程為：A進棧→B

進?！鶦

進棧→C

出?！鶥

出棧→A

出棧。在此進、出棧順序下，列車出站順序（棧的輸出序列）即為C,B,A。類似地，可以得出另外組合：B,C,A、A,C,B

和B,A,C。然而，以A,B,C

為輸入序列時，無論采用何種進、出棧順序都無法產(chǎn)生C,A,B的輸出序列。其原因為：C

的輸出需要以C

的進棧為前提，輸出

C

之前，所有尚未輸出的、C

的前序元素（A

和

B）都需要存儲在棧中，而輸出

C

之后，所有尚未輸出的、C

的前序元素均應(yīng)以逆序順序輸出（即

C,B,A），故無法輸出序列C,A,B。擴展上述結(jié)論可知，以(…,ai,…,aj,…,ak,…)作為棧的輸入序列時，無法得到輸出序列(…,ak,…,ai,…,aj,…)。棧3.1.4棧的順序存儲結(jié)構(gòu)使用順序存儲結(jié)構(gòu)構(gòu)建的棧稱為順序棧。對順序棧進行操作時，需要考慮以下幾點：存儲空間的分配方式；棧頂標識top：top是指向棧頂元素還是指向棧頂元素下一位置；滿棧和空棧的條件：是top指向棧頂元素情況下的滿棧、空棧條件還是top指向棧頂元素下一位置情況下的滿棧、空棧條件。棧3.1.4棧的順序存儲結(jié)構(gòu)假定

top

始終指向棧頂元素，任意棧

s

的特征如下。（1）非空棧條件：top>=0（2）滿棧條件：top==maxlength-1（3）空棧條件：top==-1（4）進棧過程：先對top加1，使top指向棧頂元素下一空位置，然后將待插入數(shù)據(jù)賦予s[top]，完成進棧操作（5）出棧過程：先取出棧頂元素s[top]，然后對top減1，使top指向新的棧頂元素，完成出棧操作棧3.1.4棧的順序存儲結(jié)構(gòu)當

top

始終指向棧頂元素下一位置時，任意棧

s

的特征如下。（1）非空棧條件：top>=1（2）滿棧條件：top==maxlength（3）空棧條件：top==0（4）進棧過程：先將待插入數(shù)據(jù)賦予s[top]，然后對top加1，使top指向棧頂元素下一空位置，完成進棧操作（5）出棧過程：對top減1，使top指向原來的棧頂元素棧3.1.4棧的順序存儲結(jié)構(gòu)接下來，介紹順序棧的靜態(tài)分配與動態(tài)分配。其中，靜態(tài)分配時需要定義棧的空間和棧頂標識；動態(tài)分配需要定義棧的首地址、棧頂標識和當前?？臻g的大小。具體分配方式如下：（1）靜態(tài)分配棧3.1.4棧的順序存儲結(jié)構(gòu)（2）動態(tài)分配：對比線性表靜態(tài)（動態(tài)）分配方式與棧的靜態(tài)（動態(tài)）分配方式可知，在棧的分配方式中，使用了棧頂標識top替代線性表分配方式中的表長。根據(jù)上述分析，約定top指向棧頂元素下一位置，給出如下動態(tài)分配順序棧的基本操作算法。棧3.1.4棧的順序存儲結(jié)構(gòu)設(shè)計動態(tài)分配順序棧的初始化算法——InitStack函數(shù)。首先，調(diào)用malloc函數(shù)為順序棧分配存儲空間，然后為棧頂標識top和當前空間大小stacksize賦值。棧3.1.4棧的順序存儲結(jié)構(gòu)設(shè)計進棧算法——Push函數(shù)。首先，判斷棧是否已滿，如果棧已滿，就運用realloc函數(shù)重新開辟更大的?？臻g。如果realloc函數(shù)返回值為空，提示溢出，則更新棧的地址以及棧的當前空間大小。最終，新元素入棧，棧頂標識top加1。棧3.1.4棧的順序存儲結(jié)構(gòu)設(shè)計出棧算法——Pop函數(shù)。首先，根據(jù)棧頂標識top判斷當前棧是否是一個空棧，如果當前棧是一個空棧，提示下溢，否則，更新棧頂標識，取出棧頂元素。棧3.1.5棧的鏈式存儲結(jié)構(gòu)對于棧的鏈式存儲結(jié)構(gòu)，通常只考慮采用單鏈表作為棧的存儲結(jié)構(gòu)。假定元素進棧順序為a1,a2,…,an，如果用普通無頭結(jié)點的單鏈表表示，按其元素輸入順序表示元素間的線性關(guān)系，每個新進入的元素結(jié)點應(yīng)鏈接在表尾，這樣構(gòu)造得到的鏈式棧如圖所示。棧3.1.5棧的鏈式存儲結(jié)構(gòu)但是，上面的結(jié)構(gòu)進、出棧的時間開銷大，時間復(fù)雜度為O(n)。為了解決這一問題以提高進、出棧的效率，我們可以將結(jié)點指針順序顛倒過來，即每個元素結(jié)點的指針由原來的指向邏輯上直接后繼元素結(jié)點改成指向邏輯上直接前驅(qū)元素的結(jié)點，如將top指向

an，同樣也能夠正確地維護元素間的線性關(guān)系。這樣進棧時只是簡單地將新結(jié)點作為首結(jié)點，出棧時刪除首結(jié)點即可，因為棧具有后進先出的特性。那么進、出棧不需要遍歷整個鏈表，時間開銷就為常數(shù)，時間復(fù)雜度為O(1)。棧3.1.6棧的應(yīng)用棧的“后進先出”特性在實際操作中應(yīng)用非常廣泛。例如，在高級語言中允許函數(shù)之間的嵌套調(diào)用和函數(shù)的遞歸調(diào)用，編譯程序就是通過棧這種數(shù)據(jù)結(jié)構(gòu)來完成這些執(zhí)行順序的控制的；借助棧也可以將一些遞歸算法改寫成非遞歸算法，從而提高算法效率。一般情況下，如果訪問到的數(shù)據(jù)在后續(xù)處理中還需繼續(xù)被訪問，此時就需要用某種數(shù)據(jù)結(jié)構(gòu)將其保存起來。在后續(xù)重復(fù)訪問這些數(shù)據(jù)時，其順序是“后保存的數(shù)據(jù)先被訪問，先保存的數(shù)據(jù)后被訪問”，這種情況下可運用棧這個數(shù)據(jù)結(jié)構(gòu)來保存這些數(shù)據(jù)和控制相關(guān)數(shù)據(jù)的訪問順序。下面列舉了棧的應(yīng)用實例表達式求值。棧3.1.6棧的應(yīng)用運用棧來對表達式求值，四則混合運算的規(guī)則如下。（1）先乘除，后加減（2）先括號內(nèi)，后括號外（3）同類運算，從左至右在這里，約定在運算過程中，當兩個運算符相鄰出現(xiàn)時，q1表示左運算符，q2表示右運算符。另外，新增一個運算符“#”作為一個表達式的開始符和結(jié)束符，即將待求值的表達式表示為#待求值的表達式#。棧3.1.6棧的應(yīng)用運算符的優(yōu)先級關(guān)系表在運算過程中非常重要，它是判定進棧、出棧的重要依據(jù)。θ2θ1+-*/()#+>

>

<

<

<

>

>

->

>

<

<

<

>

>

*>

>

>

>

<

>

>

/>

>

>

>

<

>

>

(<

<

<

<

<

=

)>

>

>

>

>

>

#<

<

<

<

<

=棧3.1.6棧的應(yīng)用下面以分析表達式4+2*3-12/(7-5)為例來說明求解過程，從而總結(jié)出表達式求值的算法。求解中設(shè)置兩個棧：操作數(shù)棧和運算符棧。從左至右掃描表達式：#4+2*3-12/(7-5)#，最左邊是開始符，最右邊是結(jié)束符。表達式求值的過程如下表所示：步驟號操作數(shù)棧運算符棧輸入串下步操作說明0

#4+2*3-12/(7-5)#操作數(shù)進棧14#+2*3-12/(7-5)#p(#)<p(+)，進棧24#+2*3-12/(7-5)#操作數(shù)進棧342#+*3-12/(7-5)#p(+)<p(*)，進棧442#+*3-12/(7-5)#操作數(shù)進棧5423#+*-12/(7-5)#p(*)>p(-)，退棧op=*6423#+-12/(7-5)#操作數(shù)退棧，b=3742#+-12/(7-5)#操作數(shù)退棧，a=284#+-12/(7-5)#a*b得c=6，進棧946#+-12/(7-5)#p(+)>p(-)，退棧op=+1046#-12/(7-5)#操作數(shù)退棧，b=6114#-12/(7-5)#操作數(shù)退棧，a=412

#-12/(7-5)#a+b得c=10，進棧1310#-12/(7-5)#p(#)<p(-)，進棧1410#-12/(7-5)#操作數(shù)進棧棧151012#-/(7-5)#p(-)<p(/)，進棧161012#-

/(7-5)#p(/)<p(()，進棧171012#-

/(7-5)#操作數(shù)進棧1810127#-

/(-5)#p(()<p(-)，進棧1910127#-/(-5)#操作數(shù)進棧20101275#-

/(-)#p(-)>p())，退棧op=-21101275#-

/()#操作數(shù)退棧，b=52210127#-

/()#操作數(shù)退棧，a=7231012#-

/()#a-b得c=2，進棧2410122#-

/()#p(()=p())，去括號2510122#-/#p(/)>p(#，退棧op=/2610122#-#操作數(shù)退棧，b=2271012#-#操作數(shù)退棧，a=122810#-#a/b得c=6，進棧29106#-#p(-)>p(#)，退棧op=-30106##操作數(shù)退棧，b=63110##操作數(shù)退棧，a=1032

##a-b得c=4，進棧334##p(#)=p(#)，算法結(jié)束棧3.1.6棧的應(yīng)用通過觀察中對一個表達式的求解過程，我們可以發(fā)現(xiàn)：掃描到的操作數(shù)總是會被推入操作數(shù)棧；掃描到的運算符q

2，一般會與運算符棧的棧頂元素q1進行優(yōu)先級比較，再依據(jù)優(yōu)先級的大小進行不同的操作，直到表達式只剩結(jié)束符、運算符棧只剩開始符。操作數(shù)棧的元素即是最后表達式的求值。算法的主要思想如下。設(shè)s1—操作數(shù)棧，存放暫不參與運算的數(shù)和中間結(jié)果；

s2—運算符棧，存放暫不參與運算的運算符。棧3.1.6棧的應(yīng)用（1）置s1、s2為空棧；開始符#進s2。（2）從表達式讀取w，w可為操作數(shù)或運算符。（3）當w!='#'||s2的棧頂運算符!='#'時，重復(fù)以下操作。①若w為操作數(shù)，則w進s1，讀取下一w。②若w為運算符q

2，則：prior(s2

的棧頂運算符q1)<prior(w(q

2))時，w

進s2；讀取下一w；prior(s2

的棧頂運算符q1)=prior(w(q

2))，且w=‘)’時，去括號，Pop(s2)；讀取下一w；prior(s2

的棧頂運算符(q1))>prior(w(q2))時，Pop(s1,a);Pop(s1,b);Pop(s2,op);c=b

op

a;Push(s1,c);/*op為q1*/q1

和q

2

沒定義優(yōu)先級關(guān)系，表達式有語法錯誤，會報錯（4）s1

的棧頂元素為表達式的值。02PART隊列3.2.1隊列的基本概念隊列也是插入和刪除操作位置受限的線性表，只允許在表的一端刪除元素，在另一端插入元素。隊列的別名是“先進先出”表、FIFO表、queue等。與隊列有關(guān)的概念包括以下幾個。空隊列：不含元素的隊列隊首：隊列中只允許刪除元素的一端。其一般稱為head、front。隊尾：隊列中只允許插入元素的一端。其一般稱為rear、tail。隊首元素：處于隊首的元素隊尾元素：處于隊尾的元素。進隊：插入一個元素到隊列中。其也稱為入隊。出隊：從隊列中刪除一個元素。隊列3.2.2隊列的抽象數(shù)據(jù)類型隊列3.2.3順序隊列的基本運算及實現(xiàn)順序隊列是指用一片連續(xù)的地址空間來存儲元素的隊列。同樣地，為了方便進隊和出隊操作，我們需要設(shè)置兩個標識，分別代表隊首和隊尾。例如，一維數(shù)組Q[5]表示順序隊列，設(shè)置兩個標識f和r，約定f指向隊首元素，r指向隊尾元素后的一個空單元。這樣r減去f就正好表示隊列中元素的個數(shù)；當f=r時，表示隊列為空。進隊操作，先將新元素保存在r所標識的單元中，然后向后移動r；出隊操作，先取出f指向的隊首元素，然后向后移動f。隊列3.2.3順序隊列的基本運算及實現(xiàn)在第（5）步，D,E,F

依次進隊后，r

往后移動，r

就會指向5

單元后面的單元。如果此時有元素G

進隊，就會判斷隊列已滿而出現(xiàn)“溢出”的情況。但這種“溢出”是假溢出，因為其實隊列里面還有空單元Q[0]、Q[1]和Q[2]可以用來存放元素。解決假溢出的問題有以下兩種解決方案：第一種解決方案是移動元素。在上面的例子中，如果G想進隊，就先將D,E,F整體往隊列前端空單元處移動，f也移動到指向隊首單元；G進隊后，r往后移動指向4單元。這種方法比較費時，移動元素的開銷較大，需要考慮其他更有效的方案避免元素移動，提高進隊與出隊的效率。隊列3.2.3順序隊列的基本運算及實現(xiàn)第二種解決方案是將隊列Q

當循環(huán)表使用，從而使得隊列成為一個循環(huán)隊列。接著上面的例子，D,E,F

進隊后，r

循環(huán)地指向第0

單元；G

進隊后存儲在0

單元，r

往后移動，并指向1

單元。隊列3.2.3順序隊列的基本運算及實現(xiàn)接著上面的例子，目前隊列中有D、E、F3個元素，f指向3單元，r指向1單元。如果此時H,I進隊，r往后移動，并指向3單元，而f也指向3單元，那么f=r，如圖所示。前文中，f=r是空隊列的條件，但這里f=r表示滿隊列，這樣就會出現(xiàn)二義性，違反算法的基本特性。隊列3.2.3順序隊列的基本運算及實現(xiàn)解決循環(huán)隊列的二義性問題有兩個方案：方案一是增加一個標識變量，例如用一個變量表示隊列中元素的個數(shù)來區(qū)分是滿隊列還是空隊列；方案二是留出一個單元位置不使用，作為元素進隊前測試之用，即若(r+1)%maxlength==f，表明還剩最后一個單元可用，此時可以認為隊列已滿（maxlength是隊列最大元素個數(shù)）。若隊列為Q[maxlength-1]，即系統(tǒng)會為循環(huán)隊列Q分配maxlength個元素的空間，但只能存儲maxlength-1個元素。方案二比較直觀，循環(huán)隊列的入隊算法基本采取這種方式。隊列3.2.4鏈式隊列的基本運算及實現(xiàn)鏈式隊列是用鏈式結(jié)構(gòu)存儲的隊列。一般用帶表頭結(jié)點的單鏈表來表示隊列，但隊列的頭指針與單鏈表的頭指針有所不同。隊列的插入和刪除在兩端，為提高插入、刪除的效率，頭指針中設(shè)置了Q.front和Q.rear兩個指針。Q.front是隊首指針，指向表頭結(jié)點；Q.rear是隊尾指針，指向隊尾結(jié)點?？贞犃校篞.front和Q.rear均指向表頭結(jié)點，表頭結(jié)點的指針域為空。非空隊列：Q.front->next指向隊首結(jié)點a1，Q.rear指向隊尾結(jié)點

。03PART應(yīng)用實例3.3.1棧的應(yīng)用實例編碼是信息傳輸中一種常見的操作。現(xiàn)有一種簡易的編碼規(guī)則為“k[encoded_string]”，它表示其中方括號內(nèi)部的encoded_string正好重復(fù)k次。encoded_string中的基本字符為小寫英文字母；數(shù)字k（k必須為正整數(shù)）表示對應(yīng)字符串重復(fù)出現(xiàn)的次數(shù)。利用該編碼規(guī)則，可以求返回解碼后的字符串。例如，字符串2[ab]3[c]def，表示ab出現(xiàn)2次、c出現(xiàn)3次、def出現(xiàn)1次，解碼后返回的字符串為ababcccdef。另外，這種編碼允許嵌套的表達形式，解碼的過程需要由里向外、從左到右進行解碼。例

如，字符串3[a2[bc]]2[d]，先對里層的2[bc]進行解碼得到3[abcbc]2[d]，再對3[abcbc]解碼得到abcbcabcbcabcbc2[d]，最后解碼得到的字符串為abcbcabcbcabcbcdd。應(yīng)用實例3.3.1棧的應(yīng)用實例通過分析上述解碼過程可知，我們可以借助棧來實現(xiàn)嵌套編碼的解碼。其算法思想如下。（1）初始化兩個棧，分別為記錄重復(fù)次數(shù)的數(shù)字棧s1和記錄字符串的字符串棧s2（2）掃描待解碼的字符串。①若當前字符為數(shù)字，解析出完整的數(shù)字并入棧s1②若當前字符為字母或左中括號，入棧s2③若當前字符為