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

棧第三章：棧與隊(duì)列

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

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

Stack_Size

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

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

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

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

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

()、[]、{}

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

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