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