第7章棧與Stack類2024/11/917.1棧的特點2024/11/92棧擅長在線性表的尾部，即棧頂操作，棧是受限的線性表。壓棧時，最先進棧的節點在棧底，最后進棧的節點在棧頂（俗話說，壘墻的磚，后來者居上），彈棧時，從棧頂開始彈出節點，最后一個彈出的節點是棧底節點。棧是一種后進先出的數據結構，簡稱LIFO（LastInFirstout）7.2棧的創建與獨特方法2024/11/93Stack<E>是Vector<E>的子類，因此Stack<E>類的實例屬于順序表，即其中的節點的邏輯結構是線性結構，節點的存儲結構是順序存儲。Stack<E>泛型類的實例使用數組管理節點，因此節點就是對象，后面的敘述不再說節點里的對象。2024/11/947.2棧的創建與獨特方法●創建棧使用Stack<E>泛型類聲明棧時，必須要指定E的具體類型，類型是類或接口類型（不可以是基本類型，比如int、float、char等），即指定棧中節點的類型。例如，指定E是String類型：Stack<String>stack=newStack<>();或Stack<String>stack=newStack<String>();Stack<E>泛型類的實例使用數組管理節點，因此節點就是對象，后面的敘述不再說節點里的對象。空棧默認的內部數組的長度是10（可以將內部數組理解為一塊連續的內存空間）。2024/11/957.2棧的創建與獨特方法●獨特的方法

例子1中的主類Example7_1使用了棧的獨特方法。Example7_1.java例子17.3棧與回文串2024/11/96回文串是指和其反轉（倒置）相同的字符串，例如："racecar","123321"，"level”，"toot"，"civic"，"pop"，"eye"，"rotator"，"pip"都是回文串。我們曾在第3章例子4，使用遞歸方法判斷一個字符串是否是回文串。2024/11/977.3棧與回文串Example7_2.java例子2如果一個字符串的長度是偶數，只要判斷字符串的前一半和后一半是否相同即可，如果一個字符串的長度是奇數，只要忽略字符串中間的字符，然后判斷字符串的前一半和后一半是否相同即可。那么利用棧的特點，首先將字符串的字符逐個進棧，然后彈出一半字符壓入另一個棧，然后比較兩個棧中的字符是否相同，就可以判斷一個字符串是否是回文串。7.4棧與遞歸2024/11/98遞歸過程就是方法地址被壓棧、彈棧的一個過程，所以，也可以利用棧這種數據結構，把某些遞歸算法改寫為迭代算法。2024/11/997.4棧與遞歸Example7_3.java例子3例子3主類Example7_3中利用棧輸出Fibonacci序列的前16項（有關Fibonacci序列的知識點和遞歸算法，參見第3章例子2）。2024/11/9107.4棧與遞歸Example7_4.java例子4例子4主類Example7_4中利用棧描述漢諾塔搬運盤子，這里的迭代算法，盡管比第3章例子12簡單，但卻無法顯示盤子的號碼，所以不是嚴格意義的替代遞歸的迭代算法（有關漢諾塔的知識點和遞歸、迭代算法，參見第3章例子11和例子12）。7.5棧與undo操作2024/11/911棧的“后進先出”的特點，適合用于設計undo操作，即撤銷操作。撤銷操作就是取消當前操作結果、恢復到上一次操作的結果。我們經常使用撤銷操作，對此并不陌生，比如我們在編輯文本時，經常單擊編輯器提供的“撤銷”快捷按鈕撤銷剛剛鍵入文字，讓文檔恢復到上一次編輯操作的樣子。可以用棧來實現undo操作，即把一系列操作結果壓入棧中，當用戶想回到上一步驟時，進行彈棧、彈出棧頂節點的對象，剛好是上一次的操作結果，恢復這個結果即可。可以不斷地進行彈棧操作，直到棧為空，即恢復到最初的操作結果。2024/11/9127.5棧與undo操作Example7_5.java例子5例子5的主類中的窗體有一個標簽組件，用戶單擊“顯示一個漢字”按鈕可以在標簽上顯示一個漢字。但標簽上只保留最后一次顯示的漢字。當用戶單擊“撤銷”按鈕時，將取消用戶最近一次單擊“顯示一個漢字”按鈕產生的操作效果，即將標簽上的漢字恢復為上一次單擊“顯示一個漢字”按鈕所得到的漢字。7.6棧與括號匹配2024/11/913棧的特點使得它很適合被用來檢查一個字符串中的括號是否是匹配的，即左、右括號是否是成對的。算法如下：2024/11/9147.6棧與括號匹配Match.java例子6例子6中的Match類的isMatch(Strings)方法判斷一個s中的字符串中的括號是否是匹配的。例子6的主類Example7_6中，判斷了幾個字符串中的而括號是否匹配。Example7_6.java7.6棧與深度搜索2024/11/915深度優先搜索算法，在進行遍歷或者說搜索的時候，選擇一個沒有被搜過的節點，按照深度優先：一直往該節點的后續路徑節點進行訪問，直到該路徑的最后一個節點，然后再從未被訪問的鄰節點進行深度優先搜索，重復以上過程，直至所有點都被訪問或搜索到指定的某些特殊節點，算法結束。深度優先搜索（DepthFirstSearch，DFS）和廣度優先搜索（BreadthFirstSearch，BFS）都是圖論里關于圖的遍歷的算法（見第13章13.5），但DFS算法的思想可以用于任何恰好適合使用DFS的數據搜索問題，不僅僅限于圖論中的問題。7.6棧與深度搜索2024/11/916講解DFS思想的一個很好的例子是老鼠走迷宮。2024/11/9177.6棧與深度搜索MouseStack.java例子7Example7_7.java

例子7的主類Example7_7使用move(int[][]maze)方法走迷宮，輸出該方法返回的一個二維數組，老鼠走過迷宮后，該二維數組元素值是1表示墻，0表示老師未走過的路，-1表示老鼠走過的路，2表示出口。在輸出該二維數組時用☆表示老鼠走過的路，■表示墻，★表示出口，□表示老鼠未走過的路。7.7棧與后綴表達式2024/11/918后綴表達式（也稱為逆波蘭表達式）是由波蘭數學家JanLukasiewicz在1920年發明的（那個時候還沒有計算機）。后綴表達式是一種數學表達式的表示方式，其中運算符寫在操作數的后面。例如：前面的中綴表達式(13+17)*6的后綴表達式是：1317+6*7.7棧與后綴表達式2024/11/919使用棧計算后綴表達式的步驟：2024/11/9207.7棧與后綴表達式計算后綴表達式：1317+6*按照上述步驟形成的入棧（壓棧），彈棧的示意圖如圖：中綴表達式是(13+17)*6●后綴表達式2024/11/9217.7棧與后綴表達式CalculateSuffix.java例子8Example7_8.java例子8的中的Decompose類的stringToArray(Stringexpression)把參數expression表示的表達式中的操作數和運算符依次放到數組中，并返回該數組。CalculateSuffix類的doublesuffix(String[]a)方法使用棧計算后綴表達式。●后綴表達式例子8的中的主類Example7_8使用CalculateSuffix類的doublesuffix(String[]a)方法計算了幾個后綴表達式的值。Decompose.java2024/11/9227.7棧與后綴表達式●中綴表達式轉換為后綴表達式中綴表達式中的小括號，運算符和操作數存在一個String數組a中。例如，對于(3+7)*10-6，數組a為["(","3","+","7",")","*","10","-","6"]初始化inti=0,一個棧stack，用于求后綴表達式。一個順序表list，用于存放后綴表達式的操作數和運算符。2024/11/9237.7棧與后綴表達式例子9Example7_9