數(shù)據(jù)結(jié)構(gòu)-基于Python語言（微課版） 課件T6-棧與隊列(棧)

棧第三章：棧與隊列

主講：周翔回顧請從存儲結(jié)構(gòu)、基本操作兩方面簡述順序表與鏈表的不同之處預(yù)習(xí)檢查請概括一下棧的概念請概括一下隊列的概念本章目標(biāo)3棧的應(yīng)用循環(huán)隊列重點了解掌握2棧、隊列的鏈?zhǔn)綄崿F(xiàn)棧、隊列的定義和性質(zhì)棧、隊列的順序?qū)崿F(xiàn)1什么是棧什么是棧？什么是棧棧（Stack）棧也是一種線性表，但它是受到限制的線性表用鐵路調(diào)度站表示棧什么是棧棧(Stack)定義：只能在表的一端（棧頂）進行插入和刪除運算的線性表邏輯結(jié)構(gòu)：與線性表相同，仍為一對一關(guān)系存儲結(jié)構(gòu)：用順序?；蜴湕４鎯桑皂樞驐８Ｒ娺\算規(guī)則：只能在棧頂運算，且訪問結(jié)點時依照后進先出（LIFO）或先進后出（FILO）的原則實現(xiàn)方式：關(guān)鍵是編寫入棧和出棧函數(shù)，具體實現(xiàn)依順序?；蜴湕５牟煌煌静僮饔腥霔！⒊鰲?、讀棧頂元素值、建棧、判斷棧滿、棧空等什么是棧棧(Stack)（1）棧中允許執(zhí)行插入和刪除操作的一端稱為棧頂，不允許執(zhí)行插入和刪除操作的一端稱為棧底；（2）向一個棧中插入新元素又稱為入棧、壓棧。入棧之后該元素被放在棧頂元素的上面，成為新的棧頂元素；（3）從一個棧中刪除元素又稱為出棧、彈棧，是把棧頂元素刪除，使其相鄰元素成為新的棧頂元素。什么是棧設(shè)有一個棧，元素的進棧次序為A,B,C,D,E,下列是不可能的出棧序列____。 A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,B,A543210-1ECABDADECBAEDCB什么是棧設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push,push,pop,push,pop,push,push后，輸出序列是_________。 2，3，5，4，112453棧的表示和實現(xiàn)棧（stack）是一種特殊的線性表，其插入和刪除操作只允許在線性表的一端進行ADTStack{

數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)對象 結(jié)論關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系 基本操作： InitStack(S); //將S初始化為空棧Push(S,x); //進棧Pop(S,x); //出?！瓆棧的表示和實現(xiàn)——順序棧棧的順序存儲也稱為順序棧，它利用一組地址連續(xù)的存儲單元，依次存放自棧底到棧頂?shù)脑?，同時附設(shè)棧頂標(biāo)識top來指示棧頂元素在順序棧中的位置用數(shù)組實現(xiàn)棧數(shù)組elem存儲棧元素elem[0]為最早入棧的元素，即為數(shù)組的底部數(shù)組向下標(biāo)增大方向擴展棧底elem[0]0123456789

Stack_Size

top(?？?elem棧頂elem[top]棧的表示和實現(xiàn)——順序棧順序棧插入元素：進棧棧的表示和實現(xiàn)——順序棧順序棧刪除元素：出棧棧的表示和實現(xiàn)——雙端棧棧的應(yīng)用非常廣泛，經(jīng)常會出現(xiàn)在一個程序中需要同時使用多個棧的情況若使用順序棧，會因為對?？臻g難以估計而產(chǎn)生有的棧溢出、有的?？臻g還很空閑的情況。解決方案：讓多個棧共享一個足夠大的數(shù)組空間最常用的是兩個棧的共享技術(shù)－－雙端棧棧的表示和實現(xiàn)——雙端棧雙棧共享一個棧空間兩個棧共享一個數(shù)組空間Stack[0:M-1]兩棧棧底分別放在一維數(shù)組的兩端，分別是0和M-1兩個棧頂動態(tài)變化初始情況：top[0]=-1,top[1]=M棧滿條件：top[0]+1==top[1]//兩個棧頂指針相遇

top[0]top[1]0n-1StackM-1棧的表示和實現(xiàn)——鏈?zhǔn)綏５逆準(zhǔn)酱鎯σ卜Q為鏈棧，它和鏈表的存儲原理一樣，都可以利用閑散空間來存儲元素，用指針來建立各結(jié)點之間的邏輯關(guān)系。鏈棧也會設(shè)置一個棧頂元素的標(biāo)識符top，稱為棧頂指針。它和鏈表的區(qū)別是，只能在一端進行各種操作。棧的表示和實現(xiàn)——鏈?zhǔn)綏Ｓ弥羔槍崿F(xiàn)棧鏈?zhǔn)綏o棧滿問題，空間可擴充插入與刪除僅在棧頂處執(zhí)行即：在鏈表的表頭進行！鏈表的表頭指針就作為棧頂指針?？詹僮鳎簍op→next=NULL;top棧頂棧底a1an0an-1棧的表示和實現(xiàn)——鏈?zhǔn)綏＿M棧topa1an0an-1tempx棧的表示和實現(xiàn)——鏈?zhǔn)綏３鰲opa10an-1tempxanan棧的表示和實現(xiàn)——多棧運算若同時使用兩個以上的棧，采用順序棧處理極不方便。采用多個單鏈表實現(xiàn)多個鏈棧是很好的實現(xiàn)途徑！棧的表示和實現(xiàn)——多棧運算E1M-1......543210C1C2NULLD1NULLNULLF1NULLE2E3NULLG1G2NULLdatanextLinkStackNodeLinkStacktop[M]棧的表示和實現(xiàn)——多棧運算E1M-1......543210C1C2NULLD1NULLNULLF1NULLE2E3NULLG1G2NULLtop[M]top[0]、top[1]，…，top[M-1]分別是M個鏈棧的棧頂指針分別指向M個不同的鏈棧！遞歸的概念遞歸：在定義自身的同時又出現(xiàn)了對自身的引用遞歸函數(shù)：直接地或間接地調(diào)用自身的算法走迷宮騎士游歷遞歸的概念遞歸函數(shù)調(diào)用時，按照“后調(diào)用先返回”的原則處理調(diào)用遞歸過程必須通過棧來實現(xiàn)遞歸調(diào)用時需完成調(diào)用返回時需完成保留本層參數(shù)與返回地址保存被調(diào)函數(shù)的計算結(jié)果為被調(diào)用算法的局部變量分配存儲區(qū)，給下層參數(shù)賦值釋放分配給調(diào)用算法的數(shù)據(jù)區(qū)，恢復(fù)上層參數(shù)將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)回調(diào)用函數(shù)遞歸的概念所謂遞歸就是程序調(diào)用自身的過程，它可以把一個大型的、復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的、規(guī)模較小的問題來求解，遞歸策略只需少量的代碼就可描述出解題過程中所需要的多次重復(fù)計算，大大地減少了程序的代碼量。一般來說，遞歸需要有臨界條件：遞歸前進和遞歸返回段。否則遞歸將無限調(diào)用，永遠無法結(jié)束程序，最后會造成內(nèi)存崩潰。以下三種情況常常用到遞歸方法遞歸定義的數(shù)學(xué)函數(shù)具有遞歸特性的數(shù)據(jù)結(jié)構(gòu)可遞歸求解的問題遞歸的應(yīng)用——遞歸定義的數(shù)學(xué)函數(shù)遞歸在數(shù)學(xué)方面的應(yīng)用xn=x*x*x*...*x*xS(n)=1+2+...+(n-1)+n要計算xn+1或S(n+1)，可利用前面計算過的結(jié)果以求得答案:xn+1=xn*xS(n+1)=S(n)+(n+1)這種利用前面運算來求得答案的過程就叫遞歸過程遞歸的應(yīng)用——遞歸定義的數(shù)學(xué)函數(shù)階乘函數(shù)（Factorial）//求解階乘函數(shù)的遞歸算法longfact(intn){ if(n==0) return1; else returnn*fact(n-1);}每個遞歸函數(shù)都必須有非遞歸定義的初始值！遞歸的應(yīng)用——遞歸定義的數(shù)學(xué)函數(shù)f(n)=n×f(n-1)遞歸的應(yīng)用——遞歸定義的數(shù)學(xué)函數(shù)參數(shù)傳遞主程序

main:fact(4)參數(shù)4計算4*fact(3)參數(shù)3計算3*fact(2)參數(shù)2計算2*fact(1)參數(shù)1計算1*fact(0)參數(shù)0直接定值=1結(jié)果返回遞歸調(diào)用回歸求值返回24返回6返回2返回1返回1遞歸的應(yīng)用——遞歸定義的數(shù)學(xué)函數(shù)求Fibonacci序列intfib(intn){ if(n<=1) return1; return

fib(n-1)+fib(n-2);}Fibonacci數(shù)列：1,1,2,3,5,8,13,21,34,55,...遞歸的應(yīng)用——具有遞歸特性的數(shù)據(jù)結(jié)構(gòu)樹

RootLchildRchild廣義表A=(a,A)遞歸的應(yīng)用——可遞歸求解的問題Hanoi塔（漢諾塔）問題設(shè)a,b,c是三個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小的疊在一起各圓盤從小到大編號為1,2,...,n如圖所示acb遞歸的應(yīng)用——可遞歸求解的問題目的：將塔座x上的這一疊圓盤移到塔座z上，并仍按照同樣順序疊置。xyz遞歸的應(yīng)用——可遞歸求解的問題在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則①和②的前提下，可將圓盤移至x,y,z中任一塔座上。遞歸的應(yīng)用——可遞歸求解的問題xyz321121321很難理解它的道理也很難理解它的設(shè)計思想遞歸的應(yīng)用12…nxyz21…n-1遞歸算法將一個復(fù)雜的大問題，分割成一些規(guī)模較小的類似的子問題規(guī)模最小的子問題具有直接解原問題子問題1子問題2子問題3...遞歸算法遞歸算法分治法：對于一個較為復(fù)雜的問題，能夠分解成幾個相對簡單的且解法相同或類似的子問題來求解必備的三個條件：能將一個問題轉(zhuǎn)變成一個新問題，而新問題與原問題的解法相同或類同，不同的僅是處理的對象，且這些處理對象是變化有規(guī)律的可以通過上述轉(zhuǎn)化而使問題簡化必須有一個明確的遞歸出口，或稱遞歸的邊界遞歸算法使用遞歸算法的前提：原問題可以層層分解為類似的規(guī)模更小的子問題；規(guī)模最小的子問題具有直接解。 如求n!中，n==0時，0!=1若遞歸設(shè)計時遞歸出口設(shè)計不當(dāng)……//無窮遞歸的例子//講不完的故事voidStory(){

printf("從前有座山，山上有座廟，廟里有一個老和尚和一個小和尚，有一天，老和尚對小和尚說：");

Story();}遞歸算法遞歸算法的優(yōu)缺點：優(yōu)點：結(jié)構(gòu)清晰，程序易讀缺點：每次調(diào)用要生成工作記錄，保存狀態(tài)信息，入棧；返回時要出棧，恢復(fù)狀態(tài)信息。時間開銷大遞歸算法的效率分析空間效率：與遞歸樹的深度成正比，O(n)時間效率：與遞歸樹的結(jié)點數(shù)成正比，O(2n)遞歸算法把復(fù)雜的問題分解為簡單問題，分而治之，因此，對求解某些復(fù)雜問題，遞歸算法的分析方法十分有效。但，遞歸算法的效率較低。棧的應(yīng)用棧是嵌套調(diào)用機制的實現(xiàn)基礎(chǔ)使用棧以非遞歸方式實現(xiàn)遞歸算法棧的應(yīng)用——括號匹配問題表達式中包含三種括號

()、[]、{}

例如：正確格式——{[(x+6)+(x+y)]+(y-x)}

錯誤格式——{[]})對于給定的表達式，從左到右逐個字符掃描：每個右圓括號與最近遇到的尚未匹配的左圓括號匹配；每個右花括號與最近遇到的尚未匹配的左花括號匹配；每個右方括號與最近遇到的尚未匹配的左方括號匹配。棧的應(yīng)用——括號匹配問題判斷表達式中圓括號是否匹配棧的應(yīng)用——括號匹配問題算法：在掃描過程中將所遇到“左圓括號(、左方括號[、左花括號{”存入棧中①遇到“右圓括號)、右方括號]、右花括號}”時若?？?，則遇到的“右”不匹配；②若棧非空棧頂元素是同類型的“左”型括號，則將棧頂元素作出棧操作；③棧頂元素不是同類型的“左”型括號，不合法。④讀入序列已結(jié)束，而棧中仍有等待匹配的左括號，不合法!⑤讀入序列與棧同時結(jié)束，則所有括號匹配?、迼５膽?yīng)用——用棧實現(xiàn)四則運算1、中綴轉(zhuǎn)后綴對于數(shù)字：直接輸出；對于符號：左括號：進棧，不管棧中是否有元素。運算符：若此時棧為空，直接進棧。若棧中有元素，則與棧頂符號進行優(yōu)先級比較：若新符號優(yōu)先級高，則新符號進棧（默認左