數(shù)據(jù)結(jié)構(gòu)與算法（Java語言版）課件 第7章 棧與Stack類

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

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

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