數(shù)據(jù)結(jié)構(gòu)與算法（Java語(yǔ)言版）課件 第7、8章 棧與Stack類(lèi)、隊(duì)列與ArrayDeque類(lèi)

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

例子1中的主類(lèi)Example7_1使用了棧的獨(dú)特方法。Example7_1.java例子17.3棧與回文串2024/11/96回文串是指和其反轉(zhuǎn)（倒置）相同的字符串，例如："racecar","123321"，"level”，"toot"，"civic"，"pop"，"eye"，"rotator"，"pip"都是回文串。我們?cè)诘?章例子4，使用遞歸方法判斷一個(gè)字符串是否是回文串。2024/11/977.3棧與回文串Example7_2.java例子2如果一個(gè)字符串的長(zhǎng)度是偶數(shù)，只要判斷字符串的前一半和后一半是否相同即可，如果一個(gè)字符串的長(zhǎng)度是奇數(shù)，只要忽略字符串中間的字符，然后判斷字符串的前一半和后一半是否相同即可。那么利用棧的特點(diǎn)，首先將字符串的字符逐個(gè)進(jìn)棧，然后彈出一半字符壓入另一個(gè)棧，然后比較兩個(gè)棧中的字符是否相同，就可以判斷一個(gè)字符串是否是回文串。7.4棧與遞歸2024/11/98遞歸過(guò)程就是方法地址被壓棧、彈棧的一個(gè)過(guò)程，所以，也可以利用棧這種數(shù)據(jù)結(jié)構(gòu)，把某些遞歸算法改寫(xiě)為迭代算法。2024/11/997.4棧與遞歸Example7_3.java例子3例子3主類(lèi)Example7_3中利用棧輸出Fibonacci序列的前16項(xiàng)（有關(guān)Fibonacci序列的知識(shí)點(diǎn)和遞歸算法，參見(jiàn)第3章例子2）。2024/11/9107.4棧與遞歸Example7_4.java例子4例子4主類(lèi)Example7_4中利用棧描述漢諾塔搬運(yùn)盤(pán)子，這里的迭代算法，盡管比第3章例子12簡(jiǎn)單，但卻無(wú)法顯示盤(pán)子的號(hào)碼，所以不是嚴(yán)格意義的替代遞歸的迭代算法（有關(guān)漢諾塔的知識(shí)點(diǎn)和遞歸、迭代算法，參見(jiàn)第3章例子11和例子12）。7.5棧與undo操作2024/11/911棧的“后進(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)用戶想回到上一步驟時(shí)，進(jìn)行彈棧、彈出棧頂節(jié)點(diǎn)的對(duì)象，剛好是上一次的操作結(jié)果，恢復(fù)這個(gè)結(jié)果即可?？梢圆粩嗟剡M(jìn)行彈棧操作，直到棧為空，即恢復(fù)到最初的操作結(jié)果。2024/11/9127.5棧與undo操作Example7_5.java例子5例子5的主類(lèi)中的窗體有一個(gè)標(biāo)簽組件，用戶單擊“顯示一個(gè)漢字”按鈕可以在標(biāo)簽上顯示一個(gè)漢字。但標(biāo)簽上只保留最后一次顯示的漢字。當(dāng)用戶單擊“撤銷(xiāo)”按鈕時(shí)，將取消用戶最近一次單擊“顯示一個(gè)漢字”按鈕產(chǎn)生的操作效果，即將標(biāo)簽上的漢字恢復(fù)為上一次單擊“顯示一個(gè)漢字”按鈕所得到的漢字。7.6棧與括號(hào)匹配2024/11/913棧的特點(diǎn)使得它很適合被用來(lái)檢查一個(gè)字符串中的括號(hào)是否是匹配的，即左、右括號(hào)是否是成對(duì)的。算法如下：2024/11/9147.6棧與括號(hào)匹配Match.java例子6例子6中的Match類(lèi)的isMatch(Strings)方法判斷一個(gè)s中的字符串中的括號(hào)是否是匹配的。例子6的主類(lèi)Example7_6中，判斷了幾個(gè)字符串中的而括號(hào)是否匹配。Example7_6.java7.6棧與深度搜索2024/11/915深度優(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)題。7.6棧與深度搜索2024/11/916講解DFS思想的一個(gè)很好的例子是老鼠走迷宮。2024/11/9177.6棧與深度搜索MouseStack.java例子7Example7_7.java

例子7的主類(lèi)Example7_7使用move(int[][]maze)方法走迷宮，輸出該方法返回的一個(gè)二維數(shù)組，老鼠走過(guò)迷宮后，該二維數(shù)組元素值是1表示墻，0表示老師未走過(guò)的路，-1表示老鼠走過(guò)的路，2表示出口。在輸出該二維數(shù)組時(shí)用☆表示老鼠走過(guò)的路，■表示墻，★表示出口，□表示老鼠未走過(guò)的路。7.7棧與后綴表達(dá)式2024/11/918后綴表達(dá)式（也稱為逆波蘭表達(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*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類(lèi)的stringToArray(Stringexpression)把參數(shù)expression表示的表達(dá)式中的操作數(shù)和運(yùn)算符依次放到數(shù)組中，并返回該數(shù)組。CalculateSuffix類(lèi)的doublesuffix(String[]a)方法使用棧計(jì)算后綴表達(dá)式?！窈缶Y表達(dá)式例子8的中的主類(lèi)Example7_8使用CalculateSuffix類(lèi)的doublesuffix(String[]a)方法計(jì)算了幾個(gè)后綴表達(dá)式的值。Decompose.java2024/11/9227.7棧與后綴表達(dá)式●中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式中綴表達(dá)式中的小括號(hào)，運(yùn)算符和操作數(shù)存在一個(gè)String數(shù)組a中。例如，對(duì)于(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.java●中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式InfixToSuffix.java例子9中的InfixToSuffix類(lèi)的String[]suffix(String[]infix)方法把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。例子9的主類(lèi)Example7_9讓用戶從鍵盤(pán)輸入中綴表達(dá)式，然后程序?qū)⑵滢D(zhuǎn)換為后綴表達(dá)式，并計(jì)算后綴表達(dá)式（用到了例子8中的類(lèi)），輸出計(jì)算結(jié)果。第8章隊(duì)列與ArrayDeque類(lèi)2024/11/9248.1隊(duì)列的特點(diǎn)2024/11/925隊(duì)列擅長(zhǎng)在線性表的頭、尾兩端實(shí)施刪除和添加操作，甚至可以把線性表實(shí)現(xiàn)成只在頭、尾兩端操作，所以人們也稱隊(duì)列是受限的線性表。入列時(shí)，最先進(jìn)入的節(jié)點(diǎn)在隊(duì)頭，最后進(jìn)入的節(jié)點(diǎn)在隊(duì)尾。出列時(shí)，從隊(duì)列的頭開(kāi)始刪除節(jié)點(diǎn)，最后一個(gè)刪除的節(jié)點(diǎn)是隊(duì)尾的節(jié)點(diǎn)。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱FIFO（FirstInFirstout）8.1隊(duì)列的特點(diǎn)2024/11/926頭節(jié)點(diǎn)（隊(duì)頭）在左邊、尾節(jié)點(diǎn)（隊(duì)尾）在右邊。8.2隊(duì)列的創(chuàng)建與獨(dú)特方法2024/11/927ArrayDeque<E>泛型類(lèi)繼承了Deque泛型接口中的default關(guān)鍵字修飾的方法（去掉了該關(guān)鍵字），實(shí)現(xiàn)了Deque泛型接口中的抽象方法。ArrayDeque<E>采用數(shù)組方式實(shí)現(xiàn)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，其實(shí)例屬于順序表，即節(jié)點(diǎn)的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)。ArrayDeque<E>泛型類(lèi)的實(shí)例的節(jié)點(diǎn)就是對(duì)象，后面的敘述不再說(shuō)節(jié)點(diǎn)里的對(duì)象。8.2隊(duì)列的創(chuàng)建與獨(dú)特方法2024/11/928隊(duì)列由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayDeque<E>泛型類(lèi)所實(shí)現(xiàn)。2024/11/9298.2隊(duì)列的創(chuàng)建與獨(dú)特方法●創(chuàng)建隊(duì)列ArrayDeque<E>采用數(shù)組方式實(shí)現(xiàn)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，其實(shí)例屬于順序表，即節(jié)點(diǎn)的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)。ArrayDeque<E>泛型類(lèi)的實(shí)例的節(jié)點(diǎn)就是對(duì)象，后面的敘述不再說(shuō)節(jié)點(diǎn)里的對(duì)象。使用ArrayDeque<E>泛型類(lèi)聲明隊(duì)列時(shí)，必須要指定E的具體類(lèi)型，類(lèi)型是類(lèi)或接口類(lèi)型（不可以是基本類(lèi)型，比如int、float、char等）即指定隊(duì)列中節(jié)點(diǎn)（對(duì)象）的類(lèi)型。。例如，指定E是Integer類(lèi)型：ArrayDeque<Integer>queue=newArrayDeque<>();或ArrayDeque<Integer>queue=newArrayDeque<Integer>();空隊(duì)列默認(rèn)的內(nèi)部數(shù)組的長(zhǎng)度是8（可以將內(nèi)部數(shù)組理解為一塊連續(xù)的內(nèi)存空間）。2024/11/9308.2隊(duì)列的創(chuàng)建與獨(dú)特方法●獨(dú)特的方法例子1中的主類(lèi)Example8_1使用了隊(duì)列的獨(dú)特方法。Example8_1.java例子1

8.3隊(duì)列與回文串2024/11/931回文串是指和其反轉(zhuǎn)（倒置）相同的字符串，例如："racecar","123321"，"level”，"toot"，"civic"，"pop"，"eye"，"rotator"，"pip"都是回文串。我們?cè)诘?章例子4，使用遞歸方法判斷一個(gè)字符串是否是回文串。2024/11/9328.3隊(duì)列與回文串Example8_2.java例子2使用隊(duì)列也可以判斷一個(gè)字符串是否是回文串。將字符串中的全部字符按順序依次入列，然后開(kāi)始分別從頭、尾出列，如果字符串是回文串，那么從頭出列的節(jié)點(diǎn)一定和從尾出列的節(jié)點(diǎn)相同，當(dāng)隊(duì)列中剩余的節(jié)點(diǎn)數(shù)目不足2個(gè)時(shí)，停止出列。例子2主類(lèi)Example8_2中利用隊(duì)列判斷幾個(gè)字符串是否是回文串，讀者可以和第7章例子2進(jìn)行比較，體會(huì)棧和隊(duì)列的各自特點(diǎn)。8.4隊(duì)列與加密解密2024/11/933用隊(duì)列可以方便地對(duì)字符串實(shí)施加密（解密）操作。出列的對(duì)象參與加密字符串中一個(gè)字符（出列的對(duì)象參與解密字符串中一個(gè)字符），然后再重新入列，一直到字符串中的字符全部被加密完畢（字符串中的全部字符被解密完畢）。2024/11/9348.4隊(duì)列與加密解密EncryptionDecryption.java例子3Example8_3.javaExample8_3中的主類(lèi)Example8_3使用EncryptionDecryption類(lèi)的方法對(duì)字符串了加密，然后再解密8.5隊(duì)列與約瑟夫問(wèn)題2024/11/935簡(jiǎn)單再重復(fù)一下約瑟夫問(wèn)題：若干個(gè)人圍成一圈，從某個(gè)人開(kāi)始順時(shí)針（或逆時(shí)針）數(shù)到第3個(gè)人，該人從圈中退出，然后繼續(xù)順時(shí)針（或逆時(shí)針）數(shù)到第3個(gè)人，該人從圈中退出，依此類(lèi)推，程序輸出圈中最后剩下的一個(gè)人。

2024/11/9368.5隊(duì)列與約瑟夫問(wèn)題Joseph.java例子4和第4章的例子9以及第5章的例子12相比較，使用隊(duì)列的算法不僅更加容易理解，而且所實(shí)現(xiàn)的代碼也具有很好的可讀性。例子4的Joseph類(lèi)的solveJoseph(intperson[])方法使用隊(duì)列，解決約瑟夫問(wèn)題.Example8_4.java8.6隊(duì)列與廣度搜索2024/11/937廣度優(yōu)先搜索（BreadthFirstSearch，BFS）是圖的另一種遍歷方式，與深度搜索（DFS）相對(duì)，是以廣度優(yōu)先進(jìn)行搜索。其特點(diǎn)是先訪問(wèn)圖的頂點(diǎn)，然后廣度優(yōu)先：依次進(jìn)行被訪問(wèn)點(diǎn)的鄰接點(diǎn)，一層一層訪問(wèn)，直至訪問(wèn)完所有節(jié)點(diǎn)或搜索到指定的節(jié)點(diǎn)，算法結(jié)束。棧的特點(diǎn)是后進(jìn)先出，恰好能體現(xiàn)深度優(yōu)先。隊(duì)列的特點(diǎn)是，先進(jìn)先出，恰好體現(xiàn)廣度優(yōu)先。8.6隊(duì)列與廣度搜索2024/11/938

8.6隊(duì)列與廣度搜索2024/11/939排雷算法描述如下：①將開(kāi)始的排雷點(diǎn)入列，進(jìn)行②②檢查隊(duì)列是否是空列，如果為空（雷就都被排除了）進(jìn)行④，否則進(jìn)行③③隊(duì)列進(jìn)行出列操作，將出列點(diǎn)的東西南北方向，沒(méi)有被排雷的點(diǎn)入列，然后檢查出列點(diǎn)是否是雷，并標(biāo)記此點(diǎn)已排雷：如果是雷給出一個(gè)排雷的標(biāo)記，如果是路給出一個(gè)路的標(biāo)記，進(jìn)行②④結(jié)束。2024/11/9408.6隊(duì)列與廣度搜索Deminers.java例子5Example8_5.java

注不可以一行、一行的排雷，這樣做顯然沒(méi)有體現(xiàn)廣度優(yōu)先。8.7隊(duì)列與網(wǎng)絡(luò)爬蟲(chóng)2024/11/941一個(gè)網(wǎng)站往往維護(hù)著很多網(wǎng)頁(yè)，這些網(wǎng)頁(yè)之間通過(guò)超鏈接實(shí)現(xiàn)彼此的鏈接。網(wǎng)絡(luò)爬蟲(chóng)的意思就是從網(wǎng)站的某個(gè)網(wǎng)頁(yè)開(kāi)始，通過(guò)網(wǎng)頁(yè)之間的超鏈接、遍歷該網(wǎng)站的所有網(wǎng)頁(yè)來(lái)尋找滿足要求的數(shù)據(jù)或信息。網(wǎng)絡(luò)爬蟲(chóng)，一般都采用廣度搜索。8.7隊(duì)列與網(wǎng)絡(luò)爬蟲(chóng)2024/11/942廣度搜索算法中使用隊(duì)列，就可以實(shí)現(xiàn)對(duì)網(wǎng)站的廣度搜索，算法描述如下：①將開(kāi)始的網(wǎng)頁(yè)點(diǎn)入列，進(jìn)行②②檢查隊(duì)列是否是空列，如果為空（所有網(wǎng)頁(yè)就都訪問(wèn)過(guò)了）進(jìn)行④,否則進(jìn)行③③隊(duì)列進(jìn)行出列操作，將出列的網(wǎng)頁(yè)中的所有沒(méi)有被訪問(wèn)過(guò)的超鏈接入列，然后按著需求檢索當(dāng)前出列網(wǎng)頁(yè)中的信息，并標(biāo)記此網(wǎng)頁(yè)已被訪問(wèn)過(guò)，進(jìn)行②。④結(jié)束。2024/11/9438.7隊(duì)列與網(wǎng)絡(luò)爬蟲(chóng)SaveHtml.java例子6Example8_6.java例子6的中的SaveHtml類(lèi)的saveHtml(Stringsource)方法負(fù)責(zé)將網(wǎng)頁(yè)保存為本地的文本文件。例子6的中的FindData類(lèi)的findData(Filefile,Stringregex)方法，根據(jù)正則表達(dá)式regex從本地文件file中挖掘數(shù)據(jù)，