數(shù)據(jù)結(jié)構(gòu)與算法 課件 第三章棧和隊列

全國高等教育自學(xué)考試指定教材

計算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第三章棧和隊列學(xué)習(xí)目標(biāo)掌握棧和隊列的邏輯定義、特點及基本操作，了解它們的邏輯表示方法及使用場掌握棧的兩種存儲方式及各自的特點，掌握兩種方式下基本操作的實現(xiàn)及復(fù)雜度分析掌握隊列的兩種存儲方式及各自的特點，掌握兩種方式下基本操作的實現(xiàn)，重點掌握循環(huán)隊列的實現(xiàn)及復(fù)雜度分析掌握結(jié)合了棧和隊列特點的雙端隊列了解線性表與棧及隊列的關(guān)系靈活運(yùn)用棧和隊列的基本操作，設(shè)計算法解決與此相關(guān)的實際問題本章主要內(nèi)容棧12進(jìn)一步討論棧與隊列3隊列4棧和隊列的應(yīng)用棧和隊列是線性表的兩個經(jīng)典特例，它們都是操作受限的線性表，即操作的位置需要滿足各自的條件因為這些條件的特殊性，使得實現(xiàn)各自的操作時過程簡捷，效率更高第一節(jié)

棧棧是一種特殊的線性表，它的特殊性體現(xiàn)在操作的位置上。在含n個元素的線性表中進(jìn)行插入或刪除時，操作位置可以有n+1個或n個當(dāng)將操作位置限定在線性表的同一端時，得到的數(shù)據(jù)結(jié)構(gòu)就是棧它是一種受限的線性表棧的定義及其基本操作定義3-1棧（stack）是限定僅在一端進(jìn)行插入和刪除的線性表能進(jìn)行插入和刪除的這一端稱為棧頂，線性表的另一端稱為棧底在棧頂插入一個元素稱為入棧（push）、進(jìn)棧或壓棧，從棧頂刪除一個元素稱為出棧（pop）或退棧棧的表示將棧S表示為：S=(a0,a1,…,an-1)

通常指定an-1一端為棧頂，a0一端是棧底棧中元素個數(shù)n稱為棧的長度，當(dāng)n=0時，稱為空棧棧具有后進(jìn)先出（LIFO，LastInFirstOut）的特性只要棧不空，就允許出棧只要棧不滿，就允許入棧當(dāng)沒有其他的特殊限制時，對于同一個入棧序列，可能會得到很多個合理正確的出棧序列棧的基本操作出棧序列個數(shù)

例3-1設(shè)有5個元素1,2,3,4,5依次入棧，以push(x)表示x入棧，pop(x)表示x出棧，試寫出得到出棧序列2,1,4,3,5的操作過程操作過程為push(1),push(2),pop(2),pop(1),push(3),

push(4),pop(4),pop(3),push(5),pop(5)例3-2依次讀入數(shù)據(jù)元素序列a,b,c,d,e,f,g并入棧。下列選項中，不可能是出棧序列的是（）A．d,e,c,f,b,g,aB．c,d,b,e,f,a,gC．e,f,d,g,c,b,aD．f,e,g,d,a,c,b答案為D例3-3一個棧的輸入序列為1,2,3,…,n，若輸出序列的第一個元素是n，則第i（1<i≤n）個輸出的元素是（）A．不確定B．n-i+1C．iD．n-i答案為B例3-4元素a,b,c,d,e依次進(jìn)入初始為空的棧中，在所有可能的出棧序列中，以元素d開頭的序列個數(shù)是（）A．3 B．4 C．5 D．6

答案為B例3-5入棧序列是1,2,3,4，出棧序列是2,4,3,1，則棧的容量最小是（）。A．1B．2C．3D．4答案為C棧的存儲及其實現(xiàn)棧有兩種主要的存儲方式順序存儲鏈?zhǔn)酱鎯樞虼鎯Ψ绞绞褂脭?shù)組保存棧元素，得到的是順序棧鏈?zhǔn)酱鎯Ψ绞绞褂脝捂湵肀４鏃Ｔ?，得到的是鏈?zhǔn)綏ｍ樞驐＜捌鋵崿F(xiàn)在順序棧中，棧中的元素保存在一維數(shù)組中，將棧底定義在數(shù)組下標(biāo)為0的位置同時使用一個變量標(biāo)記棧頂?shù)奈恢?，即棧頂位置棧頂位置也稱為棧頂指針順序棧的定義typedefintELEMType; //以int類型為例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是數(shù)組最大容量，已定義的常量 inttop; //棧頂位置}SeqStack;順序棧的基本操作棧頂位置top的兩種定義方式本書采用(a)的方式初始化棧、清空棧判空、判滿入棧入棧時，新元素放在element[top]處，然后top加1第1個元素入棧時放在數(shù)組下標(biāo)為0的位置因為數(shù)組空間有限，最大容量是maxSize，所以入棧時需要判定棧不能是滿的出棧出棧時，需要先將top值減1，然后將element[top]處的值通過參數(shù)x返回出棧時需要判定棧不是空的獲取棧頂元素效率top的值既是保存下一個入棧元素的位置，也是棧中所含元素個數(shù)的計數(shù)器因為棧的入棧操作及出棧操作都在棧頂進(jìn)行，所以入棧、出棧、獲取棧頂元素時都不需要移動棧中已有的元素，故時間復(fù)雜度都是O(1)判定棧空及棧滿等操作的時間復(fù)雜度也是O(1)例3-6也可以將數(shù)組下標(biāo)最大的一端作為棧底若一個棧保存在數(shù)組V[0..n-1]中，初始時棧頂指針top為n，則下列選項中，能夠正確實現(xiàn)x入棧操作的語句序列是（）。A．top=top+1;V[top]=x;B．V[top]=x;top=top+1;C．top=top-1;V[top]=x;D．V[top]=x;top=top-1;答案為C對頂棧數(shù)組的兩個端點分別作為兩個棧的棧底左側(cè)棧占用數(shù)組0到k的單元，棧頂在k+1位置右側(cè)棧占用數(shù)組m-1到h的單元，棧頂在h-1位置此時必須滿足k<h，才能保證兩個棧不會重疊棧S1入棧時，棧頂值增大，出棧時棧頂值減小棧S2剛好相反，入棧時棧頂值減小，出棧時棧頂值增大例3-7若棧采用順序存儲方式存儲，現(xiàn)有兩個棧共享空間V[0..m-1]，棧1的底在v[0]，棧2的底在V[m-1]，初始時，棧1的棧頂top1=0，棧2的棧頂top2=m-1。則棧滿的條件是（）A．|top2-top1|==0B．top1==top2+1C．top1+top2==m-1D．top1==top2答案為B鏈?zhǔn)綏Ｋ^的鏈?zhǔn)綏?，可以看作是一個僅在表頭位置進(jìn)行操作的單鏈表將頭指針?biāo)傅倪@一端作為棧頂，表尾一端作為棧底入棧操作及出棧操作都可以通過頭指針完成。所以，在鏈?zhǔn)綏Ｖ校梢灾欢x頭指針，尾指針及頭結(jié)點都可以不定義鏈?zhǔn)綏５亩xtypedefintELEMType;typedefstructnode{ //鏈?zhǔn)綏＝Y(jié)點 ELEMTypedata; structnode*next;}LinkStackNode;typedefLinkStackNode*LinkStack; //鏈?zhǔn)綏３跏蓟瘲３跏紩r是個空棧，所以指向棧頂?shù)闹羔樫x值NULL出棧僅當(dāng)棧不為空時才能執(zhí)行出棧操作，所以pop函數(shù)中要先判斷棧不為空出棧后，將棧頂元素的值通過x返回給調(diào)用者元素所占用的空間要釋放掉清空棧及判棧空入棧入棧時，需要創(chuàng)建一個新結(jié)點，并將新結(jié)點插入在棧頂位置順序棧與鏈?zhǔn)綏５谋容^實現(xiàn)順序棧和鏈?zhǔn)綏５乃胁僮鞫贾恍枰?shù)時間，因此棧的兩種實現(xiàn)方式的優(yōu)劣僅體現(xiàn)在它們的存儲效率上順序棧需要預(yù)先申請一個固定長度的一維數(shù)組，并自始至終全部占用，當(dāng)棧中元素個數(shù)相對較少時，空間浪費較大鏈?zhǔn)綏５拈L度雖然可變，但是每個元素都需要一個指針域，這又產(chǎn)生了結(jié)構(gòu)性空間開銷棧與函數(shù)調(diào)用棧是保存調(diào)用信息的最佳結(jié)構(gòu)系統(tǒng)內(nèi)部會開辟一個函數(shù)調(diào)用棧用來保存函數(shù)在調(diào)用過程中所需要的一些信息第二節(jié)

隊列隊列也是一種特殊的線性表，其特殊性也體現(xiàn)在操作的位置上它具有優(yōu)先的特性，即先來的先得到服務(wù)這種先來先服務(wù)的特性稱為先進(jìn)先出（FirstInFirstOut），簡稱FIFO隊列的定義及其基本操作定義3-2隊列（queue）是只能在表的一端插入、在另一端刪除的線性表能進(jìn)行插入的一端稱為隊列尾，簡稱隊尾；能進(jìn)行刪除的一端稱為隊列頭，簡稱隊頭在隊尾插入元素稱為入隊（enqueue），從隊頭刪除元素稱為出隊（dequeue）仍然可以沿用線性表的方法來表示隊列，隊列Q可以表示為 Q=(a0,a1,…,an-1)a0稱為隊頭元素，an-1稱為隊尾元素，元素個數(shù)n稱為隊列長度當(dāng)給定隊列的入隊序列后，僅能得到一個出隊序列，而且是與入隊序列完全相同的序列。這是由隊列先進(jìn)先出的特性決定的隊列的定義隊列中元素的類型是ELEMType，另外，還有指標(biāo)隊頭和隊尾的兩個量定義如下所示typedefintELEMType;intfront,rear; //隊頭、隊尾指針隊列的操作定義隊列的存儲及實現(xiàn)與線性表及棧一樣，隊列也有兩種實現(xiàn)方式，分別得到順序隊列和鏈?zhǔn)疥犃许樞蜿犃惺褂靡粋€一維數(shù)組A（下標(biāo)從0到n-1）來保存隊列，假定隊列中含有m（m≤n）個元素選擇A[0]作為隊頭，那么A[m-1]就是隊尾當(dāng)出隊時，隊頭A[0]從數(shù)組中刪除，此時要依次將后面的m-1個元素均前移一個位置這種情況下出隊操作的時間開銷是O(m)存儲結(jié)構(gòu)現(xiàn)在交換隊頭和隊尾的位置，選擇A[m-1]是隊頭，那么A[0]是隊尾入隊時，隊列中原有的m個元素均需后移一個位置，騰出A[0]的位置放置新元素此時入隊操作的時間開銷將為O(m)存儲結(jié)構(gòu)可以使用變量front指示隊頭位置，使用變量rear指示隊尾位置稱front為隊頭指針，rear為隊尾指針表示的是數(shù)組下標(biāo)通常，front指示的是隊頭元素所在的位置，rear指示的是隊尾元素后面的空位置按照慣例，還是將第一個入隊的元素保存在數(shù)組下標(biāo)0的位置入隊的新元素放置到所有元素的后面經(jīng)過若干次入隊、出隊操作后，含m個元素的隊列的示意圖如下所示，其中陰影部分表示隊列中的元素實際占用的數(shù)組單元

a0…am-1

↑front

↑rear

當(dāng)再進(jìn)行若干次入隊操作后，rear會到達(dá)數(shù)組的末尾，即最后一個下標(biāo)位置。之后再進(jìn)行入隊操作時，導(dǎo)致數(shù)組下標(biāo)越界。但數(shù)組的前半段可能會因出隊操作而有空閑的單元

x…y

↑front

↑rear可以重復(fù)利用數(shù)組中前面的空閑單元保存后續(xù)入隊的元素…v

……u…

↑rear

↑front

例3-8設(shè)隊列保存在最大容量為7的數(shù)組A中，從空隊列開始，依次執(zhí)行下列各步操作，分別畫出得到的隊列示意圖依次將5,12,9,37入隊列將5,12依次出隊列，并依次將25,8入隊列將16入隊列，再將9出隊列，再將7,4入隊列循環(huán)隊列順序隊列都實現(xiàn)為循環(huán)隊列在循環(huán)隊列中，入隊操作會涉及到隊尾rear值的變化，rear=(rear+1)%n，出隊操作會涉及到隊頭front值的變化，front=(front+1)%n，其中n是數(shù)組的大小可以把這個數(shù)組想象成一個首尾相接的圓環(huán)，A[n-1]的后面是A[0]“循環(huán)”一詞的含義正是如此空與滿數(shù)組滿時，rear==front條件rear==front也代表空隊列解決方法：讓數(shù)組中始終剩余至少一個空位置。當(dāng)數(shù)組中僅有一個空位置時，就認(rèn)為已經(jīng)達(dá)到隊列的最大長度了，隊列已滿初始時，front=0且rear=0例3-9已知循環(huán)隊列存儲在一維數(shù)組A[0..n-1]中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列為空，且要求第一個進(jìn)入隊列的元素存儲在A[0]處，則初始時front和rear的值分別是（）A．0,0B．0,n-1C．n-1,0D．n-1,n-1答案是B循環(huán)隊列的定義typedefintELEMType;typedefstruct{ ELEMTypeelement[maxSize]; intfront,rear;}SeqQueue;循環(huán)隊列初始化構(gòu)造一個空隊列，隊頭和隊尾指針均賦初值0清空隊列隊列置空也得到一個空隊列，可以將隊頭和隊尾指針均賦值0，和初始化隊列的結(jié)果一樣也可以讓隊頭和隊尾指針的值相等，表示是一個空隊列判空與判滿隊列為空的條件是rear==front隊列為滿的條件是(rear+1)%n==front求隊列長度入隊與出隊鏈?zhǔn)疥犃墟準(zhǔn)疥犃胁捎脦ь^指針及尾指針的單鏈表作為隊列的存儲結(jié)構(gòu)單鏈表的頭指針可以當(dāng)作隊頭指針front，尾指針可以當(dāng)作隊尾指針rear鏈?zhǔn)疥犃械亩xtypedefintELEMType;typedefstructnode{ //鏈?zhǔn)疥犃兄薪Y(jié)點 ELEMTypedata; structnode*next;}LinkQueueNode;typedefstruct{ //鏈?zhǔn)疥犃?LinkQueueNode*front,*rear; //隊頭指針、隊尾指針}LinkQueue;初始化、清空隊列判空循環(huán)隊列中，當(dāng)隊頭指針和隊尾指針相等時，隊列為空空鏈?zhǔn)疥犃兄?，隊頭指針和隊尾指針都為NULL在內(nèi)存足夠大的情況下，鏈?zhǔn)疥犃型ǔ２粫M入隊列出隊例3-10若使用不帶頭結(jié)點的單鏈表存儲隊列，則進(jìn)行入隊列操作時（）。A．僅需要修改隊頭指針，不需要修改隊尾指針B．僅需要修改隊尾指針，不需要修改隊頭指針C．隊尾指針一定要修改，隊頭指針也一定要修改D．隊尾指針一定要修改，隊頭指針可能要修改答案為D采用鏈?zhǔn)椒绞綄崿F(xiàn)隊列時，也可以配合使用一個空閑單元鏈表，使得入隊、出隊時盡量少地調(diào)用malloc函數(shù)及free函數(shù)在鏈?zhǔn)疥犃兄?，可以將這兩個鏈表合在一起，形成一個圓環(huán)，即使用一個循環(huán)鏈表來表示鏈?zhǔn)疥犃屑皩?yīng)的空閑單元鏈表。在這個循環(huán)鏈表中，結(jié)點分為兩部分，一部分結(jié)點用來保存實際數(shù)據(jù)，另一部分結(jié)點是空閑結(jié)點帶空閑單元鏈表的鏈?zhǔn)疥犃谐跏紶顟B(tài)第一個元素入隊第三節(jié)

進(jìn)一步討論棧與隊列雙端隊列輸入受限的雙端隊列輸出受限的雙端隊列例3-11若以1,2,3,4作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是（）。A．1,2,3,4B．4,1,3,2C．4,2,3,1D．4,2,1,3答案是C例3-12循環(huán)隊列存放在一維數(shù)組A[0..M-1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設(shè)隊列兩端均可進(jìn)行入隊和出隊操作，隊列中最多能容納M-1個元素，初始時為空。下列判斷隊空和隊滿的條件中，正確的是（）。A．隊空：end1==end2；隊滿：end1==(end2+1)modMB．隊空：end1==end2；隊滿：end2==(end1+1)mod(M-1)C．隊空：end2==(end1+1)modM；隊滿：end1==(end2+1)modMD．隊空：end1==(end2+1)modM；隊滿：end2==(end1+1)mod(M-1)答案是A棧與隊列的相互模擬使用棧來模擬隊列使用棧模擬的隊列類型定義typedefstruct{ SeqStackS,T;}simuQueue; //隊列typedefintELEMType;初始化入隊列出隊列判空、判滿使用隊列來模擬棧使用隊列模擬的棧類型typedefstruct{ SeqQueueP,Q;}simuStack; //使用隊列來模擬棧typedefintELEMType;初始化、清空棧判空、判滿求長度入棧操作出棧第四節(jié)

棧和隊列的應(yīng)用——括號的匹配檢查程序中有很多符號是成對出現(xiàn)的，并且它們的出現(xiàn)次序必須正確，可以嵌套但不能交錯“左”符號稱為“開”符號，“右”符號稱為“閉”符號如果表達(dá)式中符號匹配正確，則表達(dá)式稱為平衡的表達(dá)式可以用棧來實現(xiàn)檢驗符號平衡性的算法檢驗括號匹配算法的思想從左至右掃描給定的符號串，忽略所有非括號的符號當(dāng)遇到開括號時，保存它當(dāng)遇到一個閉括號時，看看它是否對應(yīng)于最近遇到的開括號如果是，則丟掉開括號，并繼續(xù)掃描符號串如果能掃描完整個符號串，且沒有遇到不匹配的情況，則給定的符號串代表的表達(dá)式是平衡的可以使用棧來保存遇到的開括號表達(dá)式不平衡的情況剛掃描到的閉括號與棧頂開括號不匹配，說明括號有交錯已掃描到表達(dá)式尾，但棧不空，說明開括號數(shù)多于閉括號數(shù)掃描到閉括號時發(fā)現(xiàn)棧為空，說明缺少與此閉括號對應(yīng)的開括號檢驗括號平衡性算法的實現(xiàn)檢驗括號平衡性算法例3-13檢查表達(dá)式[a+(d+e)]時棧的變化過程例3-14檢查表達(dá)式{[(])}時棧的變化過程表達(dá)式的計算表達(dá)式的表示