數(shù)據(jù)結(jié)構(gòu)（自考） 課件 第三章棧和隊(duì)列

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

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

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

通常指定an-1一端為棧頂，a0一端是棧底棧中元素個(gè)數(shù)n稱為棧的長度，當(dāng)n=0時(shí)，稱為空棧棧具有后進(jìn)先出（LIFO，LastInFirstOut）的特性只要棧不空，就允許出棧只要棧不滿，就允許入棧當(dāng)沒有其他的特殊限制時(shí)，對于同一個(gè)入棧序列，可能會(huì)得到很多個(gè)合理正確的出棧序列示例例3.1設(shè)有5個(gè)元素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并入棧。下列選項(xiàng)中，不可能是出棧序列的是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元素a,b,c,d,e依次進(jìn)入初始為空的棧中，在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是A．3 B．4 C．5 D．6

答案為B棧的存儲(chǔ)及其實(shí)現(xiàn)棧有兩種主要的存儲(chǔ)方式，分別是順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)順序存儲(chǔ)方式使用數(shù)組保存棧元素，得到的是順序棧鏈?zhǔn)酱鎯?chǔ)方式使用單鏈表保存棧元素，得到的是鏈?zhǔn)綏ｍ樞驐＜捌鋵?shí)現(xiàn)在順序棧中，棧中的元素保存在一維數(shù)組中，將棧底定義在數(shù)組下標(biāo)為0的位置同時(shí)使用一個(gè)變量標(biāo)記棧頂?shù)奈恢?，即棧頂位置棧頂位置也稱為棧頂指針順序棧的定義typedefintELEMType; //以int類型為例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是數(shù)組最大容量 //已定義的常量 inttop; //棧頂位置}SeqStack;棧頂位置top的兩種定義方式本書采用(a)的方式相應(yīng)操作的實(shí)現(xiàn)入棧入棧時(shí)，新元素放在element[top]處，然后top加1第1個(gè)元素入棧時(shí)放在數(shù)組下標(biāo)為0的位置因?yàn)閿?shù)組空間有限，最大容量是maxSize，所以入棧時(shí)需要判定棧不能是滿的出棧出棧時(shí)，需要先將top值減1，然后將element[top]處的值通過參數(shù)x返回出棧時(shí)需要判定棧不是空的效率top的值既是保存下一個(gè)入棧元素的位置，也是棧中所含元素個(gè)數(shù)的計(jì)數(shù)器因?yàn)闂５娜霔２僮骷俺鰲２僮鞫荚跅ｍ斶M(jìn)行，所以入棧及出棧時(shí)都不需要移動(dòng)棧中已有的元素，故時(shí)間復(fù)雜度都是O(1)判定棧空及棧滿等操作的時(shí)間復(fù)雜度也是O(1)對頂棧數(shù)組的兩個(gè)端點(diǎn)分別作為兩個(gè)棧的棧底左側(cè)棧占用數(shù)組0到k的單元，棧頂在k+1位置右側(cè)棧占用數(shù)組m-1到h的單元，棧頂在h-1位置此時(shí)必須滿足k<h，才能保證兩個(gè)棧不會(huì)重疊棧S1入棧時(shí)，棧頂值增大，出棧時(shí)棧頂值減小棧S2剛好相反，入棧時(shí)棧頂值減小，出棧時(shí)棧頂值增大鏈?zhǔn)綏Ｋ^的鏈?zhǔn)綏?，可以看作是一個(gè)僅在表頭位置進(jìn)行操作的單鏈表將頭指針?biāo)傅倪@一端作為棧頂，表尾一端作為棧底入棧操作及出棧操作都可以通過頭指針完成。所以，在鏈?zhǔn)綏Ｖ?，可以只定義頭指針，尾指針及頭結(jié)點(diǎn)都可以不定義鏈?zhǔn)綏５亩xtypedefintELEMType;typedefstructnode{ ELEMTypedata; structnode*next;}LinkedStackNode;typedefLinkedStackNode*LinkedStack; //鏈?zhǔn)綏３跏蓟瘲３跏紩r(shí)是個(gè)空棧，所以指向棧頂?shù)闹羔樫x值NULL出棧僅當(dāng)棧不為空時(shí)才能執(zhí)行出棧操作，所以pop函數(shù)中要先判斷棧不為空出棧后，將棧頂元素的值通過x返回給調(diào)用者元素所占用的空間要釋放掉清空棧及判棧空入棧入棧時(shí)，需要?jiǎng)?chuàng)建一個(gè)新結(jié)點(diǎn)，并將新結(jié)點(diǎn)插入在棧頂位置順序棧與鏈?zhǔn)綏５谋容^實(shí)現(xiàn)順序棧和鏈?zhǔn)綏５乃胁僮鞫贾恍枰?shù)時(shí)間，因此棧的兩種實(shí)現(xiàn)方式的優(yōu)劣僅體現(xiàn)在它們的存儲(chǔ)效率上順序棧需要預(yù)先申請一個(gè)固定長度的一維數(shù)組，并自始至終全部占用，當(dāng)棧中元素個(gè)數(shù)相對較少時(shí)，空間浪費(fèi)較大鏈?zhǔn)綏５拈L度雖然可變，但是每個(gè)元素都需要一個(gè)指針域，這又產(chǎn)生了結(jié)構(gòu)性空間開銷棧與函數(shù)調(diào)用棧是保存調(diào)用信息的最佳結(jié)構(gòu)系統(tǒng)內(nèi)部會(huì)開辟一個(gè)函數(shù)調(diào)用棧用來保存函數(shù)在調(diào)用過程中所需要的一些信息第二節(jié)

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

a0…am-1

↑front

↑rear

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

x…y

↑front

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

……u…

↑rear

↑front

示例設(shè)隊(duì)列保存在最大容量為7的數(shù)組A中，從空隊(duì)列開始，依次執(zhí)行下列各步操作，分別畫出得到的隊(duì)列示意圖依次將5,12,9,37入隊(duì)列將5,12依次出隊(duì)列，并依次將25,8入隊(duì)列將16入隊(duì)列，再將9出隊(duì)列，再將7,4入隊(duì)列循環(huán)隊(duì)列順序隊(duì)列都實(shí)現(xiàn)為循環(huán)隊(duì)列在循環(huán)隊(duì)列中，入隊(duì)操作會(huì)涉及到隊(duì)尾rear值的變化，rear=(rear+1)%n，出隊(duì)操作會(huì)涉及到隊(duì)頭front值的變化，front=(front+1)%n，其中n是數(shù)組的大小可以把這個(gè)數(shù)組想象成一個(gè)首尾相接的圓環(huán)，A[n-1]的后面是A[0]“循環(huán)”一詞的含義正是如此空與滿數(shù)組滿時(shí)，rear==front條件rear==front也代表空隊(duì)列解決方法：讓數(shù)組中始終剩余至少一個(gè)空位置。當(dāng)數(shù)組中僅有一個(gè)空位置時(shí)，就認(rèn)為已經(jīng)達(dá)到隊(duì)列的最大長度了，隊(duì)列已滿初始時(shí)，front=0且rear=0循環(huán)隊(duì)列的定義typedefintELEMType;typedefstruct{ ELEMTypeelement[maxSize]; intfront,rear;}SeqQueue;循環(huán)隊(duì)列初始化構(gòu)造一個(gè)空隊(duì)列，隊(duì)頭和隊(duì)尾指針均賦初值0清空隊(duì)列隊(duì)列置空也得到一個(gè)空隊(duì)列，可以將隊(duì)頭和隊(duì)尾指針均賦值0，和初始化隊(duì)列的結(jié)果一樣也可以讓隊(duì)頭和隊(duì)尾指針的值相等，表示是一個(gè)空隊(duì)列判空與判滿隊(duì)列為空的條件是rear==front隊(duì)列為滿的條件是(rear+1)%n==front求隊(duì)列長度入隊(duì)與出隊(duì)鏈?zhǔn)疥?duì)列鏈?zhǔn)疥?duì)列采用帶頭指針及尾指針的單鏈表作為隊(duì)列的存儲(chǔ)結(jié)構(gòu)單鏈表的頭指針可以當(dāng)作隊(duì)頭指針front，尾指針可以當(dāng)作隊(duì)尾指針rear鏈?zhǔn)疥?duì)列的定義typedefintELEMType;typedefstructnode{ ELEMTypedata; structnode*next;}LinkedQueueNode;typedefstruct{ LinkedQueueNode*front,*rear; //隊(duì)頭、隊(duì)尾指針}LinkedQueue;初始化、清空隊(duì)列判空循環(huán)隊(duì)列中，當(dāng)隊(duì)頭指針和隊(duì)尾指針相等時(shí)，隊(duì)列為空空鏈?zhǔn)疥?duì)列中，隊(duì)頭指針和隊(duì)尾指針都為NULL在內(nèi)存足夠大的情況下，鏈?zhǔn)疥?duì)列通常不會(huì)滿入隊(duì)列出隊(duì)第三節(jié)

棧和隊(duì)列的應(yīng)用——括號的匹配檢查程序中有很多符號是成對出現(xiàn)的，并且它們的出現(xiàn)次序必須正確，可以嵌套但不能交錯(cuò)“左”符號稱為“開”符號，“右”符號稱為“閉”符號如果表達(dá)式中符號匹配正確，則表達(dá)式稱為平衡的表達(dá)式可以用棧來實(shí)現(xiàn)檢驗(yàn)符號平衡性的算法檢驗(yàn)括號匹配算法的思想從左至右掃描給定的符號串，忽略所有非括號的符號當(dāng)遇到開括號時(shí)，保存它當(dāng)遇到一個(gè)閉括號時(shí)，看看它是否對應(yīng)于最近遇到的開括號如果是，則丟掉開括號，并繼續(xù)掃描符號串如果能掃描完整個(gè)符號串，且沒有遇到不匹配的情況，則給定的符號串代表的表達(dá)式是平衡的可以使用棧來保存遇到的開括號表達(dá)式不平衡的情況剛掃描到的閉括號與棧頂開括號不匹配，說明括號有交錯(cuò)已掃描到表達(dá)式尾，但棧不空，說明開括號數(shù)多于閉括號數(shù)掃描到閉括號時(shí)發(fā)現(xiàn)棧為空，說明缺少與此閉括號對應(yīng)的開括號檢驗(yàn)括號平衡性算法的實(shí)現(xiàn)檢驗(yàn)括號平衡性算法示例檢查表達(dá)式[a+(d+e)]時(shí)棧的變化過程檢查表達(dá)式{[(])}時(shí)棧的變化過程表達(dá)式的計(jì)算表達(dá)式的表示形式及計(jì)算次序中綴表達(dá)式： <操作數(shù)><運(yùn)算符><操作數(shù)> c*(a+b)前綴表達(dá)式 <運(yùn)算符><操作數(shù)><操作數(shù)>后綴表達(dá)式 <操作數(shù)><操作數(shù)><運(yùn)算符>將中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y表達(dá)式——手算給中綴表達(dá)式中的每個(gè)運(yùn)算符加括號，這樣的表達(dá)式稱為帶完全括號的中綴表達(dá)式接下來，將每個(gè)運(yùn)算符右移，