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

第8章隊(duì)列與ArrayDeque類2024/11/918.1隊(duì)列的特點(diǎn)2024/11/92隊(duì)列擅長(zhǎng)在線性表的頭、尾兩端實(shí)施刪除和添加操作，甚至可以把線性表實(shí)現(xiàn)成只在頭、尾兩端操作，所以人們也稱隊(duì)列是受限的線性表。入列時(shí)，最先進(jìn)入的節(jié)點(diǎn)在隊(duì)頭，最后進(jìn)入的節(jié)點(diǎn)在隊(duì)尾。出列時(shí)，從隊(duì)列的頭開始刪除節(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/93頭節(jié)點(diǎn)（隊(duì)頭）在左邊、尾節(jié)點(diǎn)（隊(duì)尾）在右邊。8.2隊(duì)列的創(chuàng)建與獨(dú)特方法2024/11/94ArrayDeque<E>泛型類繼承了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>泛型類的實(shí)例的節(jié)點(diǎn)就是對(duì)象，后面的敘述不再說節(jié)點(diǎn)里的對(duì)象。8.2隊(duì)列的創(chuàng)建與獨(dú)特方法2024/11/95隊(duì)列由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayDeque<E>泛型類所實(shí)現(xiàn)。2024/11/968.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>泛型類的實(shí)例的節(jié)點(diǎn)就是對(duì)象，后面的敘述不再說節(jié)點(diǎn)里的對(duì)象。使用ArrayDeque<E>泛型類聲明隊(duì)列時(shí)，必須要指定E的具體類型，類型是類或接口類型（不可以是基本類型，比如int、float、char等）即指定隊(duì)列中節(jié)點(diǎn)（對(duì)象）的類型。。例如，指定E是Integer類型：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/978.2隊(duì)列的創(chuàng)建與獨(dú)特方法●獨(dú)特的方法例子1中的主類Example8_1使用了隊(duì)列的獨(dú)特方法。Example8_1.java例子1

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

2024/11/9138.5隊(duì)列與約瑟夫問題Joseph.java例子4和第4章的例子9以及第5章的例子12相比較，使用隊(duì)列的算法不僅更加容易理解，而且所實(shí)現(xiàn)的代碼也具有很好的可讀性。例子4的Joseph類的solveJoseph(intperson[])方法使用隊(duì)列，解決約瑟夫問題.Example8_4.java8.6隊(duì)列與廣度搜索2024/11/914廣度優(yōu)先搜索（BreadthFirstSearch，BFS）是圖的另一種遍歷方式，與深度搜索（DFS）相對(duì)，是以廣度優(yōu)先進(jìn)行搜索。其特點(diǎn)是先訪問圖的頂點(diǎn)，然后廣度優(yōu)先：依次進(jìn)行被訪問點(diǎn)的鄰接點(diǎ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/915

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

注不可以一行、一行的排雷，這樣做顯然沒有體現(xiàn)廣度優(yōu)先。8.7隊(duì)列與網(wǎng)絡(luò)爬蟲2024/11/918一個(gè)網(wǎng)站往往維護(hù)著很多網(wǎng)頁(yè)，這些網(wǎng)頁(yè)之間通過超鏈接實(shí)現(xiàn)彼此的鏈接。網(wǎng)絡(luò)爬蟲的意思就是從網(wǎng)站的某個(gè)網(wǎng)頁(yè)開始，通過網(wǎng)頁(yè)之間的超鏈接、遍歷該網(wǎng)站的所有網(wǎng)頁(yè)來尋找滿足要求的數(shù)據(jù)或信息。網(wǎng)絡(luò)爬蟲，一般都采用廣度搜索。8.7隊(duì)列與網(wǎng)絡(luò)爬蟲2024/11/919廣度搜索算法中使用隊(duì)列，就可以實(shí)現(xiàn)對(duì)網(wǎng)站的廣度搜索，算法描述如下：①將開始的網(wǎng)頁(yè)點(diǎn)入列，進(jìn)行②②檢查隊(duì)列是否是空列，如果為空（所有網(wǎng)頁(yè)就都訪問過了）進(jìn)行④,否則進(jìn)行③③隊(duì)列進(jìn)行出列操作，將出列的網(wǎng)頁(yè)中的所有沒有被訪問過的超鏈接入列，然后按著需求檢索當(dāng)前出列網(wǎng)頁(yè)中的信息，并標(biāo)記此網(wǎng)頁(yè)已被訪問過，進(jìn)行②。④結(jié)束。2024/11/9208.7隊(duì)列與網(wǎng)絡(luò)爬蟲SaveHtml.java例子6Example8_6.java例子6的中的SaveHtml類的saveHtml(Stringsource)方法負(fù)責(zé)將網(wǎng)頁(yè)保存為本地的文本文件。例子6的中的FindData類的findData(Filefile,Stringregex)方法，根據(jù)正則表達(dá)式regex從本地文件file中挖掘數(shù)據(jù)，比如挖掘網(wǎng)頁(yè)中的所有超鏈接，所有g(shù)if圖像的名字等。例子6的中的WeBSpider類的spider(Stringaddress,Stringdata)方法使用廣度搜索算法搜索地址是address的網(wǎng)站上的多個(gè)網(wǎng)頁(yè)中，匹配正則表達(dá)式data的數(shù)據(jù)，即WeBSpider類的spider(Stringaddress,Stringdata,intmax)方法就是所謂的網(wǎng)絡(luò)爬蟲。FindData.javaWeBSpider.java2024/11/9218.7隊(duì)列與網(wǎng)絡(luò)爬蟲例子6的中的主類Example8_6使用WeBSpider類的spider(Stringaddress,Stringdata,intmax)方法爬取百度網(wǎng)站上20個(gè)網(wǎng)頁(yè)上的gif圖像的名字和含有百度一詞的句子.8.8隊(duì)列與排隊(duì)2024/11/922假設(shè)一個(gè)營(yíng)業(yè)廳有2個(gè)服務(wù)窗口，低峰期間有一個(gè)窗口營(yíng)業(yè)，高峰期間有2個(gè)窗口營(yíng)業(yè)，每個(gè)窗口為一位顧客辦理業(yè)務(wù)的耗時(shí)不盡相同。程序模擬營(yíng)業(yè)廳服務(wù)若干顧客，觀察兩個(gè)窗口分別服務(wù)了多少顧客，停止?fàn)I業(yè)后，看看還有多少顧客未能辦理業(yè)務(wù)。2024/11/9238.8隊(duì)列與排隊(duì)ServiceWindow.java例子7Example8_7.jav