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

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

計(jì)算機(jī)及應(yīng)用專(zhuān)業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第三章棧和隊(duì)列學(xué)習(xí)目標(biāo)掌握棧和隊(duì)列的邏輯定義、特點(diǎn)及基本操作，了解它們的邏輯表示方法及使用場(chǎng)掌握棧的兩種存儲(chǔ)方式及各自的特點(diǎn)，掌握兩種方式下基本操作的實(shí)現(xiàn)及復(fù)雜度分析掌握隊(duì)列的兩種存儲(chǔ)方式及各自的特點(diǎn)，掌握兩種方式下基本操作的實(shí)現(xiàn)，重點(diǎn)掌握循環(huán)隊(duì)列的實(shí)現(xiàn)及復(fù)雜度分析掌握結(jié)合了棧和隊(duì)列特點(diǎn)的雙端隊(duì)列了解線性表與棧及隊(duì)列的關(guān)系靈活運(yùn)用棧和隊(duì)列的基本操作，設(shè)計(jì)算法解決與此相關(guān)的實(shí)際問(wèn)題本章主要內(nèi)容棧12進(jìn)一步討論棧與隊(duì)列3隊(duì)列4棧和隊(duì)列的應(yīng)用棧和隊(duì)列是線性表的兩個(gè)經(jīng)典特例，它們都是操作受限的線性表，即操作的位置需要滿足各自的條件因?yàn)檫@些條件的特殊性，使得實(shí)現(xiàn)各自的操作時(shí)過(guò)程簡(jiǎn)捷，效率更高第一節(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稱為棧的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空棧棧具有后進(jìn)先出（LIFO，LastInFirstOut）的特性只要棧不空，就允許出棧只要棧不滿，就允許入棧當(dāng)沒(méi)有其他的特殊限制時(shí)，對(duì)于同一個(gè)入棧序列，可能會(huì)得到很多個(gè)合理正確的出棧序列棧的基本操作出棧序列個(gè)數(shù)

例3-1設(shè)有5個(gè)元素1,2,3,4,5依次入棧，以push(x)表示x入棧，pop(x)表示x出棧，試寫(xiě)出得到出棧序列2,1,4,3,5的操作過(guò)程操作過(guò)程為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一個(gè)棧的輸入序列為1,2,3,…,n，若輸出序列的第一個(gè)元素是n，則第i（1<i≤n）個(gè)輸出的元素是（）A．不確定B．n-i+1C．iD．n-i答案為B例3-4元素a,b,c,d,e依次進(jìn)入初始為空的棧中，在所有可能的出棧序列中，以元素d開(kāi)頭的序列個(gè)數(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棧的存儲(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類(lèi)型為例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是數(shù)組最大容量，已定義的常量 inttop; //棧頂位置}SeqStack;順序棧的基本操作棧頂位置top的兩種定義方式本書(shū)采用(a)的方式初始化棧、清空棧判空、判滿入棧入棧時(shí)，新元素放在element[top]處，然后top加1第1個(gè)元素入棧時(shí)放在數(shù)組下標(biāo)為0的位置因?yàn)閿?shù)組空間有限，最大容量是maxSize，所以入棧時(shí)需要判定棧不能是滿的出棧出棧時(shí)，需要先將top值減1，然后將element[top]處的值通過(guò)參數(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)例3-6也可以將數(shù)組下標(biāo)最大的一端作為棧底若一個(gè)棧保存在數(shù)組V[0..n-1]中，初始時(shí)棧頂指針top為n，則下列選項(xiàng)中，能夠正確實(shí)現(xiàn)x入棧操作的語(yǔ)句序列是（）。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對(duì)頂棧數(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í)棧頂值增大例3-7若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)有兩個(gè)棧共享空間V[0..m-1]，棧1的底在v[0]，棧2的底在V[m-1]，初始時(shí)，棧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)綏?，可以看作是一個(gè)僅在表頭位置進(jìn)行操作的單鏈表將頭指針?biāo)傅倪@一端作為棧頂，表尾一端作為棧底入棧操作及出棧操作都可以通過(guò)頭指針完成。所以，在鏈?zhǔn)綏Ｖ?，可以只定義頭指針，尾指針及頭結(jié)點(diǎn)都可以不定義鏈?zhǔn)綏５亩xtypedefintELEMType;typedefstructnode{ //鏈?zhǔn)綏＝Y(jié)點(diǎn) ELEMTypedata; structnode*next;}LinkStackNode;typedefLinkStackNode*LinkStack; //鏈?zhǔn)綏３跏蓟瘲３跏紩r(shí)是個(gè)空棧，所以指向棧頂?shù)闹羔樫x值NULL出棧僅當(dāng)棧不為空時(shí)才能執(zhí)行出棧操作，所以pop函數(shù)中要先判斷棧不為空出棧后，將棧頂元素的值通過(guò)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ù)先申請(qǐng)一個(gè)固定長(zhǎng)度的一維數(shù)組，并自始至終全部占用，當(dāng)棧中元素個(gè)數(shù)相對(duì)較少時(shí)，空間浪費(fèi)較大鏈?zhǔn)綏５拈L(zhǎng)度雖然可變，但是每個(gè)元素都需要一個(gè)指針域，這又產(chǎn)生了結(jié)構(gòu)性空間開(kāi)銷(xiāo)棧與函數(shù)調(diào)用棧是保存調(diào)用信息的最佳結(jié)構(gòu)系統(tǒng)內(nèi)部會(huì)開(kāi)辟一個(gè)函數(shù)調(diào)用棧用來(lái)保存函數(shù)在調(diào)用過(guò)程中所需要的一些信息第二節(jié)

隊(duì)列隊(duì)列也是一種特殊的線性表，其特殊性也體現(xiàn)在操作的位置上它具有優(yōu)先的特性，即先來(lái)的先得到服務(wù)這種先來(lái)先服務(wù)的特性稱為先進(jìn)先出（FirstInFirstOut），簡(jiǎn)稱FIFO隊(duì)列的定義及其基本操作定義3-2隊(duì)列（queue）是只能在表的一端插入、在另一端刪除的線性表能進(jìn)行插入的一端稱為隊(duì)列尾，簡(jiǎn)稱隊(duì)尾；能進(jìn)行刪除的一端稱為隊(duì)列頭，簡(jiǎn)稱隊(duì)頭在隊(duì)尾插入元素稱為入隊(duì)（enqueue），從隊(duì)頭刪除元素稱為出隊(duì)（dequeue）仍然可以沿用線性表的方法來(lái)表示隊(duì)列，隊(duì)列Q可以表示為 Q=(a0,a1,…,an-1)a0稱為隊(duì)頭元素，an-1稱為隊(duì)尾元素，元素個(gè)數(shù)n稱為隊(duì)列長(zhǎng)度當(dāng)給定隊(duì)列的入隊(duì)序列后，僅能得到一個(gè)出隊(duì)序列，而且是與入隊(duì)序列完全相同的序列。這是由隊(duì)列先進(jìn)先出的特性決定的隊(duì)列的定義隊(duì)列中元素的類(lèi)型是ELEMType，另外，還有指標(biāo)隊(duì)頭和隊(duì)尾的兩個(gè)量定義如下所示typedefintELEMType;intfront,rear; //隊(duì)頭、隊(duì)尾指針隊(duì)列的操作定義隊(duì)列的存儲(chǔ)及實(shí)現(xiàn)與線性表及棧一樣，隊(duì)列也有兩種實(shí)現(xiàn)方式，分別得到順序隊(duì)列和鏈?zhǔn)疥?duì)列順序隊(duì)列使用一個(gè)一維數(shù)組A（下標(biāo)從0到n-1）來(lái)保存隊(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í)間開(kāi)銷(xiāo)是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í)間開(kāi)銷(xiāo)將為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)過(guò)若干次入隊(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

例3-8設(shè)隊(duì)列保存在最大容量為7的數(shù)組A中，從空隊(duì)列開(kāi)始，依次執(zhí)行下列各步操作，分別畫(huà)出得到的隊(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ì)列的最大長(zhǎng)度了，隊(duì)列已滿初始時(shí)，front=0且rear=0例3-9已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A[0..n-1]中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空，且要求第一個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A[0]處，則初始時(shí)front和rear的值分別是（）A．0,0B．0,n-1C．n-1,0D．n-1,n-1答案是B循環(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ì)列長(zhǎng)度入隊(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{ //鏈?zhǔn)疥?duì)列中結(jié)點(diǎn) ELEMTypedata; structnode*next;}LinkQueueNode;typedefstruct{ //鏈?zhǔn)疥?duì)列 LinkQueueNode*front,*rear; //隊(duì)頭指針、隊(duì)尾指針}LinkQueue;初始化、清空隊(duì)列判空循環(huán)隊(duì)列中，當(dāng)隊(duì)頭指針和隊(duì)尾指針相等時(shí)，隊(duì)列為空空鏈?zhǔn)疥?duì)列中，隊(duì)頭指針和隊(duì)尾指針都為NULL在內(nèi)存足夠大的情況下，鏈?zhǔn)疥?duì)列通常不會(huì)滿入隊(duì)列出隊(duì)例3-10若使用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，則進(jìn)行入隊(duì)列操作時(shí)（）。A．僅需要修改隊(duì)頭指針，不需要修改隊(duì)尾指針B．僅需要修改隊(duì)尾指針，不需要修改隊(duì)頭指針C．隊(duì)尾指針一定要修改，隊(duì)頭指針也一定要修改D．隊(duì)尾指針一定要修改，隊(duì)頭指針可能要修改答案為D采用鏈?zhǔn)椒绞綄?shí)現(xiàn)隊(duì)列時(shí)，也可以配合使用一個(gè)空閑單元鏈表，使得入隊(duì)、出隊(duì)時(shí)盡量少地調(diào)用malloc函數(shù)及free函數(shù)在鏈?zhǔn)疥?duì)列中，可以將這兩個(gè)鏈表合在一起，形成一個(gè)圓環(huán)，即使用一個(gè)循環(huán)鏈表來(lái)表示鏈?zhǔn)疥?duì)列及對(duì)應(yīng)的空閑單元鏈表。在這個(gè)循環(huán)鏈表中，結(jié)點(diǎn)分為兩部分，一部分結(jié)點(diǎn)用來(lái)保存實(shí)際數(shù)據(jù)，另一部分結(jié)點(diǎn)是空閑結(jié)點(diǎn)帶空閑單元鏈表的鏈?zhǔn)疥?duì)列初始狀態(tài)第一個(gè)元素入隊(duì)第三節(jié)

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

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