第6章棧2025/6/111棧的特點

列表擔當棧角色棧與遞歸棧與括號匹配棧與深度搜素棧與后綴表達式棧與undo操作6.1棧的特點2025/6/112棧擅長在線性表的尾部，即棧頂操作，棧是受限的線性表。壓棧時，最先進棧的節點在棧底，最后進棧的節點在棧頂（俗話說，壘墻的磚，后來者居上），彈棧時，從棧頂開始彈出節點，最后一個彈出的節點是棧底節點。棧是一種后進先出的數據結構，簡稱LIFO（LastInFirstout）6.2列表擔當棧角色2025/6/113

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