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