抽象數(shù)據(jù)類型—隊(duì)列 知識(shí)目標(biāo) 你可以 在抽象層次描述隊(duì)列和其實(shí)現(xiàn) 定義隊(duì)列接口 描述用數(shù)組實(shí)現(xiàn)隊(duì)列操作的算法 比較基于數(shù)組實(shí)現(xiàn)隊(duì)列的固定隊(duì)頭和浮動(dòng)隊(duì)頭方法 說(shuō)明如何用數(shù)組實(shí)現(xiàn)無(wú)界隊(duì)列 描述用鏈表實(shí)現(xiàn)隊(duì)列操作的算法 用增長(zhǎng)階分析描述及比較隊(duì)列算法的效率 定義隊(duì)列中元素的間隔時(shí)間、服務(wù)時(shí)間、周轉(zhuǎn)時(shí)間和等待時(shí)間 說(shuō)明并發(fā)線程如何互相干擾、引發(fā)出錯(cuò)，以及如何預(yù)防該干擾 技能目標(biāo) 你可以 用數(shù)組實(shí)現(xiàn)有界隊(duì)列抽象數(shù)據(jù)類型（ADT） 用數(shù)組實(shí)現(xiàn)無(wú)界隊(duì)列ADT 用鏈表實(shí)現(xiàn)無(wú)界隊(duì)列ADT 繪制圖表表示特定隊(duì)列實(shí)現(xiàn)的隊(duì)列操作效果 使用隊(duì)列ADT作為應(yīng)用程序的一部分 給定到達(dá)時(shí)間和服務(wù)要求，計(jì)算隊(duì)列元素的周轉(zhuǎn)時(shí)間和等待時(shí)間 用隊(duì)列模擬系統(tǒng)調(diào)研真實(shí)世界中的隊(duì)列屬性 實(shí)現(xiàn)一個(gè)程序，它能正確使用線程以利用問(wèn)題解決方案內(nèi)置的平行性 本章我們將討論隊(duì)列。在邏輯上隊(duì)列與棧相對(duì)應(yīng)，棧屬于“后進(jìn)先出”結(jié)構(gòu)，而 隊(duì)列屬于“先進(jìn)先出”結(jié)構(gòu)。在隊(duì)列中時(shí)間最長(zhǎng)的元素就是最先移除的元素。與棧 一樣，隊(duì)列有多種與系統(tǒng)編程有關(guān)的重要用法，而且該結(jié)構(gòu)也適用于其他多種應(yīng)用 程序。 我們把隊(duì)列當(dāng)成一種抽象數(shù)據(jù)類型，從抽象層次、應(yīng)用層次和實(shí)現(xiàn)層次來(lái)對(duì)待。 在抽象層次，隊(duì)列用Java接口定義。我們將討論數(shù)種隊(duì)列應(yīng)用程序，特別是探討如何 用隊(duì)列確定某個(gè)字符串是否屬于回文，并調(diào)研真實(shí)世界中的隊(duì)列屬性。我們將用兩種 基本方法實(shí)現(xiàn)隊(duì)列：數(shù)組和鏈表。除了用數(shù)組實(shí)現(xiàn)有界隊(duì)列之外，我們也會(huì)學(xué)習(xí)如何 用數(shù)組實(shí)現(xiàn)無(wú)界隊(duì)列。與我們處理視圖的正常順序有所不同，本章的最后一節(jié)討論了 如何使用隊(duì)列來(lái)保存旨在執(zhí)行并行的任務(wù)，而如果這種并行性能夠用于提高性能，我 們?cè)撊绾问褂肑ava來(lái)妥善利用并列。 4.1  隊(duì)列 在Chapter 2中學(xué)習(xí)的棧結(jié)構(gòu)，通常是在同一端進(jìn)行元素添加和移除。但如果我們 需要介紹一種有不同操作方式的集合，又該怎么辦呢？假設(shè)我們模擬洗車場(chǎng)洗車，車 輛從車場(chǎng)的一頭進(jìn)去，從另一頭出來(lái)。元素從一端進(jìn)入，再?gòu)南喾吹牧硪欢顺鰜?lái)的數(shù) 據(jù)結(jié)構(gòu)稱為隊(duì)列。隊(duì)列數(shù)據(jù)結(jié)構(gòu)，就跟洗車場(chǎng)一樣，其特點(diǎn)就是最先進(jìn)去的元素（車 輛）是最先出來(lái)的元素（車輛）。 這種隊(duì)列的基本形式存在數(shù)種變體，為了進(jìn)行區(qū)別，我們一般引用先進(jìn)先出的隊(duì) 列。其他隊(duì)列版本將在第4.7節(jié)“隊(duì)列變體”和Chapter 9“抽象數(shù)據(jù)類型－優(yōu)先級(jí)隊(duì) 列”中進(jìn)行介紹�，F(xiàn)在我們把注意力集中在隊(duì)列的常見(jiàn)版本，即一般所說(shuō)的“隊(duì)列” 是指先進(jìn)先出的隊(duì)列。與棧的情況一樣，我們從三個(gè)層次把隊(duì)列視為一種抽象數(shù)據(jù)類 型：抽象、實(shí)現(xiàn)和應(yīng)用層次。 隊(duì)列操作 書(shū)店的例子暗示了可以應(yīng)用于隊(duì)列的兩種操作。首先，我們可以在隊(duì)尾添加新元 素，這個(gè)操作叫入隊(duì)（enqueue）；其次，我們可以從隊(duì)頭移除元素，這個(gè)操作叫出隊(duì) （dequeue）。圖4.2用方塊模擬隊(duì)列元素，向我們展示了上述操作對(duì)隊(duì)列產(chǎn)生的影響。 與棧操作的壓棧和退棧不一樣，隊(duì)列的添加和移除操作沒(méi)有標(biāo)準(zhǔn)的名稱。 enqueue 操作有時(shí)也會(huì)叫enq、 enque、 add（添加）或者insert（插入）， dequeue的別稱也有 deq、 deque、 remove（移除）、或serve。 使用隊(duì)列 Chapter 2中討論了操作系統(tǒng)和編譯程序如何使用棧。同樣地，隊(duì)列也經(jīng)常用于系 統(tǒng)編程。例如，某個(gè)操作系統(tǒng)通常備有隨時(shí)可執(zhí)行的處理隊(duì)列，或者等待特定事件發(fā) 生便可執(zhí)行的處理隊(duì)列。 另一個(gè)例子是，計(jì)算機(jī)系統(tǒng)通常必須提供“存儲(chǔ)區(qū)”，以存放在兩個(gè)處理進(jìn)程、兩 個(gè)程序甚至兩個(gè)系統(tǒng)之間傳送的信息。這個(gè)存儲(chǔ)區(qū)通常稱為“緩存”，通常作為隊(duì)列實(shí) 現(xiàn)。例如，如果一個(gè)郵件伺服器在同一時(shí)間收到大量郵件信息，這些信息會(huì)先存放在 緩存區(qū)，直到該郵件伺服器做好準(zhǔn)備處理這些信息。如果伺服器是按照信息到達(dá)的先 后順序—先進(jìn)先出的順序進(jìn)行處理的話，那么該緩存就屬于隊(duì)列。 很多其他應(yīng)用程序在處理之前都要先存儲(chǔ)請(qǐng)求。試想一下為顧客提供服務(wù)的應(yīng)用 程序，比如出售飛機(jī)票或者電影票。這些應(yīng)用程序通常會(huì)用隊(duì)列來(lái)處理請(qǐng)求。 如書(shū)店的例子所示，軟件所用的隊(duì)列在現(xiàn)實(shí)世界中有相對(duì)應(yīng)的例子。類似的還有 我們要排隊(duì)買比薩、排隊(duì)進(jìn)影院、排隊(duì)過(guò)收費(fèi)站、排隊(duì)坐過(guò)山車等。隊(duì)列數(shù)據(jù)結(jié)構(gòu)的 另一種重要應(yīng)用是幫助我們模擬和分析現(xiàn)實(shí)世界的這些隊(duì)列，有關(guān)這點(diǎn)我們將在第4.8 節(jié)“應(yīng)用程序：平均等待時(shí)間”中的范例應(yīng)用中介紹。 4.2  隊(duì)列接口 本節(jié)將正式指定隊(duì)列ADT。除了enqueue和dequeue操作與push、 pop和top不同之 外，隊(duì)列所使用的基本方法與棧ADT一樣： 隊(duì)列都是泛型的—特定隊(duì)列持有的對(duì)象類型在該隊(duì)列實(shí)例化時(shí)由客戶端指示。 定義支持隊(duì)列的類在ch04.queues package中成組呈現(xiàn)。 提供觀察函數(shù)操作size（大�。�，以便應(yīng)用程序確定隊(duì)列的大小。隊(duì)列的大小對(duì)于 應(yīng)用程序而言很重要，因?yàn)樗�意味著元素可以待在�?duì)列多久。 提供觀察函數(shù)操作isEmpty（為空）和isFull（為滿），以便客戶端在合適的情況下 能夠預(yù)防自己嘗試從空隊(duì)列中移除元素，或者在滿隊(duì)列中添加元素。 創(chuàng)建QueueUnderflowException（隊(duì)列下溢異常）和QueueOverflowException（隊(duì)列 溢出異常）兩個(gè)類。 創(chuàng)建一個(gè)QueueInterface（隊(duì)列接口），定義隊(duì)列方法的特征。實(shí)現(xiàn)隊(duì)列應(yīng)該要實(shí) 現(xiàn)這個(gè)接口。 兩個(gè)異常類的代碼基本上與Chapter 2中棧所用的兩個(gè)異常類的代碼一樣，所以這 里不予展示。與棧的情況一樣，應(yīng)用程序員能夠在訪問(wèn)隊(duì)列之前，決定使用isFull和 isEmpty兩個(gè)觀察函數(shù)來(lái)預(yù)防出現(xiàn)問(wèn)題，或者應(yīng)用程序能夠嘗試訪問(wèn)操作，“捕獲并處 理”引發(fā)的異常。 以下為QueueInterface。該接口定義隊(duì)列五個(gè)方法的特征—enqueue、 dequeue、 isEmpty、 isFull和size。