數(shù)據(jù)結(jié)構(gòu)與算法（Python語(yǔ)言版）課件 第6章 棧VIP

第6章棧2025/6/111棧的特點(diǎn)

列表?yè)?dān)當(dāng)棧角色棧與遞歸棧與括號(hào)匹配棧與深度搜素棧與后綴表達(dá)式棧與undo操作6.1棧的特點(diǎn)2025/6/112棧擅長(zhǎng)在線性表的尾部，即棧頂操作，棧是受限的線性表。壓棧時(shí)，最先進(jìn)棧的節(jié)點(diǎn)在棧底，最后進(jìn)棧的節(jié)點(diǎn)在棧頂（俗話(huà)說(shuō)，壘墻的磚，后來(lái)者居上），彈棧時(shí)，從棧頂開(kāi)始彈出節(jié)點(diǎn)，最后一個(gè)彈出的節(jié)點(diǎn)是棧底節(jié)點(diǎn)。棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱(chēng)LIFO（LastInFirstout）6.2列表?yè)?dān)當(dāng)棧角色2025/6/113

6.2列表?yè)?dān)當(dāng)棧角色2025/6/114回文串是指和其反轉(zhuǎn)（倒置）相同的字符串，例如："racecar","123321"，"level”，"toot"，"civic"，"pop"，"eye"，"rotator"，"pip"都是回文串。我們?cè)诘?章例子4，使用遞歸方法判斷一個(gè)字符串是否是回文串。2025/6/1156.2列表?yè)?dān)當(dāng)棧角色ch6_1.py例子2如果一個(gè)字符串的長(zhǎng)度是偶數(shù)，只要判斷字符串的前一半和后一半是否相同即可，如果一個(gè)字符串的長(zhǎng)度是奇數(shù)，只要忽略字符串中間的字符，然后判斷字符串的前一半和后一半是否相同即可。那么利用棧的特點(diǎn)，首先將字符串的字符逐個(gè)進(jìn)棧，然后彈出一半字符壓入另一個(gè)棧，然后比較兩個(gè)棧中的字符是否相同，就可以判斷一個(gè)字符串是否是回文串。利用棧判斷一個(gè)字符串是否為回文串6.3棧與遞歸2025/6/116遞歸過(guò)程就是方法地址被壓棧、彈棧的一個(gè)過(guò)程，所以，也可以利用棧這種數(shù)據(jù)結(jié)構(gòu)，把某些遞歸算法改寫(xiě)為迭代算法。2025/6/1176.3棧與遞歸ch6_2.py例子2ch6_2.py中利用棧輸出Fibonacci序列的前16項(xiàng)（有關(guān)Fibonacci序列的知識(shí)點(diǎn)和遞歸算法參見(jiàn)第3章中的例3-2）。利用棧輸出Fibonacci序列的前幾項(xiàng)6.4棧與括號(hào)匹配2025/6/118棧的特點(diǎn)使得它很適合被用來(lái)檢查一個(gè)字符串中的括號(hào)是否是匹配的，即左、右括號(hào)是否是成對(duì)的。算法如下：2025/6/1196.4棧與括號(hào)匹配例子3檢查括號(hào)是否匹配算法描述如下：（1）遍歷字符串的每個(gè)字符，遇到左括號(hào)時(shí)壓棧。（2）遇到右括號(hào)，如果此時(shí)棧為空，字符串中就出現(xiàn)了括號(hào)不匹配現(xiàn)象。如果棧不空，彈棧。如果字符串中的括號(hào)是匹配的，按著棧的特點(diǎn)，當(dāng)遍歷字符串遇到右括號(hào)時(shí)，此刻棧頂節(jié)點(diǎn)中的括號(hào)一定是和它相匹配的左括號(hào)，如果不是這樣，字符串中的括號(hào)就出現(xiàn)了不匹配現(xiàn)象。ch6_3.py6.5棧與深度搜索2025/6/1110深度優(yōu)先搜索算法，在進(jìn)行遍歷或者說(shuō)搜索的時(shí)候，選擇一個(gè)沒(méi)有被搜過(guò)的節(jié)點(diǎn)，按照深度優(yōu)先：一直往該節(jié)點(diǎn)的后續(xù)路徑節(jié)點(diǎn)進(jìn)行訪問(wèn)，直到該路徑的最后一個(gè)節(jié)點(diǎn)，然后再?gòu)奈幢辉L問(wèn)的鄰節(jié)點(diǎn)進(jìn)行深度優(yōu)先搜索，重復(fù)以上過(guò)程，直至所有點(diǎn)都被訪問(wèn)或搜索到指定的某些特殊節(jié)點(diǎn)，算法結(jié)束。深度優(yōu)先搜索（DepthFirstSearch，DFS）和廣度優(yōu)先搜索（BreadthFirstSearch，BFS）都是圖論里關(guān)于圖的遍歷的算法（見(jiàn)第13章13.5），但DFS算法的思想可以用于任何恰好適合使用DFS的數(shù)據(jù)搜索問(wèn)題，不僅僅限于圖論中的問(wèn)題。6.5棧與深度搜索2025/6/1111講解DFS思想的一個(gè)很好的例子是老鼠走迷宮。2025/6/11126.5棧與深度搜索例子4模擬老鼠走迷宮ch6_4.pych6_4.py中使用move_in_maze(maze,rows,columns)函數(shù)走迷宮。老鼠走過(guò)迷宮后，列表中元素值是1表示墻，0表示老鼠未走過(guò)的路，-1表示老鼠走過(guò)的路，2表示出口。對(duì)于其中一個(gè)迷宮，老鼠無(wú)法到達(dá)路口，因?yàn)槿魏温范紵o(wú)法到達(dá)出口，對(duì)于另外一個(gè)迷宮，老鼠成功到達(dá)出口.6.6棧與后綴表達(dá)式2025/6/1113后綴表達(dá)式（也稱(chēng)為逆波蘭表達(dá)式）是由波蘭數(shù)學(xué)家JanLukasiewicz在1920年發(fā)明的（那個(gè)時(shí)候還沒(méi)有計(jì)算機(jī)）。后綴表達(dá)式是一種數(shù)學(xué)表達(dá)式的表示方式，其中運(yùn)算符寫(xiě)在操作數(shù)的后面。例如：前面的中綴表達(dá)式(13+17)*6的后綴表達(dá)式是：1317+6*6.6棧與后綴表達(dá)式2025/6/1114使用棧計(jì)算后綴表達(dá)式的步驟：2025/6/11156.6棧與后綴表達(dá)式計(jì)算后綴表達(dá)式：1317+6*按照上述步驟形成的入棧（壓棧），彈棧的示意圖如圖：中綴表達(dá)式是(13+17)*6后綴表達(dá)式2025/6/11166.6棧與后綴表達(dá)式ALG_suffix.py例子5使用棧計(jì)算后綴表達(dá)式ch6_5.py后綴表達(dá)式ALG_suffix.py中的string_to_array(expression)函數(shù)把后綴表達(dá)式expression中的運(yùn)算數(shù)和運(yùn)算符號(hào)存儲(chǔ)到列表中（后綴表達(dá)式expression中的運(yùn)算符和運(yùn)算數(shù)之間、運(yùn)算數(shù)之間要用空格分隔）；suffix(a)函數(shù)使用棧計(jì)算后綴表達(dá)式(a是string_to_array(expression)函數(shù)返回的列表).2025/6/11176.6棧與后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式2025/6/11186.6棧與后綴表達(dá)式例子6把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式ch6_6.py●中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式ALG_suffix.py將例5中的ALG_suffix.py文件和本例ch6_6.py保存在同一目錄中。本例中的infix_to_suffix(infix)函數(shù)把中綴表達(dá)式infix轉(zhuǎn)換為后綴表達(dá)式，本例首先把一個(gè)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式、計(jì)算后綴表達(dá)式的值（并顯示后綴表達(dá)式）,然后讓有戶(hù)從鍵盤(pán)輸出一個(gè)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式、計(jì)算后綴表達(dá)式的值（不再顯示后綴表達(dá)式）.6.7棧與undo操作2025/6/1119棧的“后進(jìn)先出”的特點(diǎn)，適合用于設(shè)計(jì)undo操作，即撤銷(xiāo)操作。撤銷(xiāo)操作就是取消當(dāng)前操作結(jié)果、恢復(fù)到上一次操作的結(jié)果。我們經(jīng)常使用撤銷(xiāo)操作，對(duì)此并不陌生，比如我們?cè)诰庉嬑谋緯r(shí)，經(jīng)常單擊編輯器提供的“撤銷(xiāo)”快捷按鈕撤銷(xiāo)剛剛鍵入文字，讓文檔恢復(fù)到上一次編輯操作的樣子?？梢杂脳?lái)實(shí)現(xiàn)undo操作，即把一系列操作結(jié)果壓入棧中，當(dāng)用戶(hù)想回到上一步驟時(shí)，進(jìn)行彈棧、彈出棧頂節(jié)點(diǎn)的對(duì)象，剛好是上一次的操作結(jié)果，恢復(fù)這個(gè)結(jié)果即可?？梢圆粩嗟剡M(jìn)行彈棧操作，直到棧為空，即恢復(fù)到最初的操作結(jié)果。2025/6/11206.7棧與undo操作ch6_7.py例子7撤銷(xiāo)顯示的漢字ch6_7.py中的窗體有一個(gè)標(biāo)簽組件，用戶(hù)單擊“