Java/佇列之道
本章介紹了兩個 ADT：佇列和優先順序佇列。在現實生活中，佇列是客戶等待某種服務的排隊。在大多數情況下，排在最前面的顧客是下一個被服務的顧客。不過也有一些例外。例如，在機場，即將起飛的航班的乘客有時會被從佇列中間帶走。同樣，在超市裡，禮貌的顧客可能會讓只有幾件商品的人先走。
決定誰下一個的規則稱為排隊規則。最簡單的排隊規則稱為 FIFO，代表 “先進先出”。最一般的排隊規則是優先順序排隊，其中每個顧客都被分配一個優先順序，優先順序最高的顧客先走，無論他們到達的順序如何。我之所以說這是最一般的規則是因為優先順序可以基於任何東西：航班離開的時間、顧客購買的商品數量或顧客的重要性。當然，並非所有排隊規則都是“公平的”，但公平與否見仁見智。
佇列 ADT 和優先順序佇列 ADT 有一組相同的操作，它們的介面也相同。區別在於操作的語義：佇列使用 FIFO 策略，而優先順序佇列（顧名思義）使用優先順序排隊策略。
與大多數 ADT 一樣，有很多方法可以實現佇列。由於佇列是專案的集合，我們可以使用任何用於儲存集合的基本機制，包括陣列和列表。我們在它們之間進行選擇將部分基於它們的效能——執行我們想要執行的操作所需的時間——以及部分基於實現的難易程度。
ADT!Queue Queue ADT implementation!Queue queue!List implementation
佇列 ADT 由以下操作定義
描述
[建構函式：] 建立一個新的空佇列。
[插入：] 向佇列新增一個新專案。
[移除：] 從佇列中移除並返回一個專案。返回的專案是第一個新增的專案。
[空：] 檢查佇列是否為空。
描述
為了演示佇列的實現，我將利用來自列表章節的 LinkedList 類。此外，我將假設我們有一個名為 Customer 的類，它定義了每個客戶的所有資訊以及我們可以對客戶執行的操作。
就我們的實現而言，佇列中是什麼型別的物件並不重要，因此我們可以使它成為泛型的。以下是實現的程式碼：
逐字 public class Queue
public LinkedList list;
public Queue ()
list = new List ();
public boolean empty ()
return list.empty ();
public void insert (Object obj)
list.addLast (obj);
public Object remove ()
return list.removeFirst ();
逐字
佇列物件包含一個例項變數，它就是實現它的列表。對於其他每個方法，我們只需要呼叫 LinkedList 類中的一個方法。
veneer performance hazard performance analysis
這樣的實現稱為飾面。在現實生活中，飾面是指傢俱製作中使用的薄層優質木材，用來隱藏下面的低品質木材。計算機科學家使用這個比喻來描述隱藏實現細節並提供更簡單或更標準介面的一小段程式碼。
這個例子展示了飾面的好處之一，即它易於實現，以及使用飾面的危險之一，即效能風險！
通常，當我們呼叫一個方法時，我們不會關心它的實現細節。但是，我們可能想了解一個“細節”——方法的效能特徵。作為列表中專案數量的函式，它需要多長時間才能執行？
首先讓我們看一下 removeFirst。
逐字
public Object removeFirst ()
Object result = head;
if (head != null)
head = head.next;
return result;
逐字
這裡沒有迴圈或函式呼叫，這表明此方法的執行時間每次都是相同的。這樣的方法稱為恆定時間操作。實際上，當列表為空時，該方法可能稍微快一些，因為它跳過了條件語句的主體，但這種差異並不顯著。
constant time
addLast 的效能則大不相同。
逐字
public void addLast (Object obj)
// special case: empty list
if (head == null)
head = new Node (obj, null);
return;
Node last;
for (last = head; last.next != null; last = last.next)
// traverse the list to find the last node
last.next = new Node (obj, null);
逐字
第一個條件語句處理向空列表新增新節點的特殊情況。在這種情況下，同樣，執行時間也不依賴於列表的長度。但是，在一般情況下，我們必須遍歷列表以找到最後一個元素，以便可以使其引用新節點。
這種遍歷所需的時間與列表的長度成正比。由於執行時間是長度的線性函式，我們說這種方法是線性時間。與恆定時間相比，這非常糟糕。
linear time
queue!linked implementation linked queue
我們希望有一個佇列 ADT 的實現，它可以在恆定時間內執行所有操作。實現這一點的一種方法是實現連結串列佇列，它類似於連結串列，因為它是用一個或多個連結的 Node 物件組成的。區別在於佇列維護對第一個節點和最後一個節點的引用，如圖所示。
figure=figs/queue1.eps,width=4in
以下是連結串列佇列實現的程式碼：
逐字 public class Queue
public Node first, last;
public Queue ()
first = null;
last = null;
public boolean empty ()
return first == null;
逐字
到目前為止，它很簡單。在空佇列中，first 和 last 都是 null。要檢查列表是否為空，我們只需要檢查其中一個。
插入稍微複雜一些，因為我們必須處理幾個特殊情況。
逐字
public void insert (Object obj)
Node node = new Node (obj, null);
if (last != null)
last.next = node;
last = node;
if (first == null)
first = last;
逐字
第一個條件語句檢查 last 是否引用一個節點；如果引用了，則我們必須使它引用新的節點。
第二個條件語句處理列表最初為空的特殊情況。在這種情況下，first 和 last 都引用新的節點。
移除也處理了幾個特殊情況。
逐字
public Object remove ()
Node result = first;
if (first != null)
first = first.next;
if (first == null)
last = null;
return result;
逐字
第一個條件語句檢查佇列中是否還有節點。如果有，我們必須將下一個節點複製到 first。第二個條件語句處理列表現在為空的特殊情況，在這種情況下，我們必須將 last 設定為 null。
作為練習，繪製一些圖表，顯示這兩種操作在正常情況下和特殊情況下的情況，並說服自己它們是正確的。
顯然，這個實現比飾面實現更加複雜，而且更難以證明它是正確的。優點是實現了我們的目標：插入和移除都是恆定時間。
queue!circular buffer implementation circular buffer buffer!circular
佇列的另一種常見實現是迴圈緩衝區。“緩衝區”是臨時儲存位置的通用名稱，儘管它通常是指陣列，在本例中就是這樣。為什麼要說緩衝區是“迴圈的”將在下面解釋。
迴圈緩衝區的實現類似於棧的陣列實現，如陣列棧部分。佇列專案儲存在陣列中，我們使用索引來跟蹤我們在陣列中的位置。在棧的實現中，有一個索引指向下一個可用空間。在佇列的實現中，有兩個索引：first 指向陣列中包含佇列中第一個客戶的空間，next 指向下一個可用空間。
下圖顯示了一個包含兩個專案（用點表示）的佇列。
figure=figs/queue2.eps,width=4in
有兩種方法可以理解 first 和 last 變數。從字面上講，它們是整數，它們的值顯示在右側的方框中。然而，從抽象的角度來說，它們是陣列的索引，因此它們通常被繪製成指向陣列中位置的箭頭。箭頭表示很方便，但請記住，索引不是引用，它們只是整數。
以下是一個不完整的佇列陣列實現：
逐字 public class Queue
public Object[] array; public int first, next;
public Queue ()
array = new Object[128];
first = 0;
next = 0;
public boolean empty ()
return first == next;
逐字
例項變數和建構函式很簡單，儘管我們仍然面臨著必須為陣列選擇一個任意大小的問題。稍後，我們將解決這個問題，就像我們在棧中所做的那樣，如果陣列滿了，我們將調整陣列的大小。
空實現有點出乎意料。你可能認為 first == 0 表示空佇列，但這忽略了佇列的頭部並不一定位於陣列的開頭這一事實。相反，我們知道佇列為空，如果 head 等於 next，在這種情況下，沒有剩餘的專案。一旦我們看到 insert 和 remove 的實現，這種情況就更有意義了。
逐字
public void insert (Object item)
array[next] = item;
next++;
public Object remove ()
Object result = array[first];
first++;
return result;
逐字
insert 看起來非常像陣列棧部分中的 push；它將新專案放入下一個可用空間，然後增加索引。
remove 類似。它從佇列中取出第一個專案，然後增加 first，使其指向佇列的新頭部。下圖顯示了移除所有專案後佇列的樣子。
figure=figs/queue3.eps,width=4in
next 始終指向一個可用空間。如果 first 追上 next 並指向同一個空間，那麼 first 就指向一個“空”位置，並且佇列為空。我將“空”放在引號中，因為 first 指向的位置實際上可能包含一個值（我們不做任何操作來確保空位置包含 null）；另一方面，由於我們知道佇列為空，因此我們永遠不會讀取這個位置，因此我們可以從抽象的角度認為它為空。
作為練習，修復 remove，使其在佇列為空時返回 null。
此實現的下一個問題是它最終會耗盡空間。當我們新增一個專案時，我們遞增 next，當我們移除一個專案時，我們遞增 first，但我們從未遞減任何一個。當我們到達陣列末尾時會發生什麼？
下圖顯示了我們在新增四個專案後佇列的狀態。
figure=figs/queue4.eps,width=4in
陣列現在已滿。沒有“下一個可用空間”，所以 next 無處可指。一種可能性是我們可能調整陣列大小，就像我們在堆疊實現中所做的那樣。但那樣的話，無論佇列中實際有多少專案，陣列都會不斷變大。更好的解決方案是環繞回陣列的開頭並重用那裡的空間。這種“環繞”是這種實現被稱為迴圈緩衝區的原因。
一種環繞索引的方法是在每次遞增索引時新增一個特殊情況。
逐字
next++;
if (next == array.length) next = 0;
逐字
一個更巧妙的替代方案是使用模運算子。
逐字
next = (next + 1)
逐字
無論哪種方式，我們都還有一個問題需要解決。我們如何知道佇列是否真的已滿，這意味著我們無法插入另一個專案？下圖顯示了佇列“已滿”時的樣子。
figure=figs/queue5.eps,width=4in
陣列中仍然有一個空位，但佇列已滿，因為如果我們插入另一個專案，那麼我們必須遞增 next 使其等於 first，在這種情況下，它看起來像是佇列為空！
為了避免這種情況，我們犧牲了陣列中的一個空間。那麼我們如何判斷佇列是否已滿呢？
逐字
if ((next + 1)
逐字
如果陣列已滿該怎麼辦？在這種情況下，調整陣列大小可能是唯一的選擇。
作為練習，將本節中的所有程式碼整理在一起，編寫一個使用迴圈緩衝區的佇列實現，該迴圈緩衝區在必要時調整自身大小。
優先佇列
[edit | edit source]priority queue!ADT ADT!Priority Queue
優先佇列 ADT 與佇列 ADT 具有相同的介面，但語義不同。介面是
描述
[建構函式：] 建立一個新的空佇列。
[插入：] 向佇列新增一個新專案。
[remove:] 從佇列中移除並返回一個專案。返回的專案是優先順序最高的專案。
[空：] 檢查佇列是否為空。
描述
語義上的差異在於，從佇列中移除的專案不一定是第一個新增的專案。相反，它是佇列中優先順序最高的任何專案。優先順序是什麼以及它們如何相互比較，由優先佇列實現未指定。它取決於佇列中專案的型別。
例如，如果佇列中的專案有名稱，我們可能會按字母順序選擇它們。如果它們是保齡球分數，我們可能會從最高到最低進行選擇，但如果它們是高爾夫分數，我們將從最低到最高進行選擇。
generic data structure!generic
所以我們面臨著一個新問題。我們想要一個優先佇列實現，它是通用的——它應該適用於任何型別的物件——但同時，實現優先佇列的程式碼需要有能力比較它包含的物件。
我們已經看到了使用 Objects 實現泛型資料結構的一種方法，但這並不能解決這個問題，因為除非我們知道它們的型別，否則沒有辦法比較 Objects。
答案在於 Java 的一項新功能，稱為抽象類。
抽象類
[edit | edit source]abstract class class!abstract Comparable abstract class!Comparable
抽象類是一組類。抽象類定義指定了類必須滿足的要求才能成為成員。
抽象類通常以“able”結尾，以指示抽象類所需的基本功能。例如，任何提供名為 draw 的方法的類都可以是名為 Drawable 的抽象類的成員。任何包含名為 start 的方法的類都可以是名為 Runnable 的抽象類的成員。
從 Java 2 開始，Java 提供了一個內建的抽象類，我們可以在優先佇列的實現中使用它。它被稱為 Comparable，它的含義正如它所說。任何屬於 Comparable 抽象類的類都必須提供一個名為 compareTo 的方法，該方法比較兩個物件並返回一個值，指示一個物件是否大於或小於另一個物件，或者它們是否相同。
許多內建的 Java 類都是 Comparable 抽象類的成員，包括數字包裝類，如 Integer 和 Double。
在下一節中，我將展示如何編寫一個操作抽象類的 ADT。然後，我們將看到如何編寫一個屬於現有抽象類的新的（具體）類。然後，我們將看到如何編寫一個新的抽象類。
優先佇列的陣列實現
[edit | edit source]implementation!Priority Queue priority queue!array implementation
在優先佇列的實現中，每次我們指定佇列中專案的型別時，我們都指定抽象類 Comparable。例如，例項變數是 Comparables 陣列和一個整數。
verbatim public class PriorityQueue
private Comparable[] array; private int index;
逐字
像往常一樣，index 是陣列中下一個可用位置的索引。例項變數被宣告為 private，以便其他類無法直接訪問它們。
建構函式和 empty 與我們之前看到的類似。我任意選擇了陣列的初始大小。
逐字
public PriorityQueue ()
array = new Comparable [16];
index = 0;
public boolean empty ()
return index == 0;
逐字
insert 與 push 類似。
逐字
public void insert (Comparable item)
if (index == array.length)
resize ();
array[index] = item;
index++;
逐字
我省略了 resize 的實現。類中唯一實質性的方法是 remove，它必須遍歷陣列以找到並刪除最大的專案。
逐字
public Comparable remove ()
if (index == 0) return null;
int maxIndex = 0;
// find the index of the item with the highest priority
for (int i=1; i<index; i++)
if (array[i].compareTo (array[maxIndex]) > 0)
maxIndex = i;
Comparable result = array[maxIndex];
// move the last item into the empty slot
index--;
array[maxIndex] = array[index];
return result;
逐字
當我們遍歷陣列時，maxIndex 會跟蹤我們迄今為止看到的最大元素的索引。什麼是“最大”由 compareTo 決定。在本例中，compareTo 方法由 Integer 類提供，它按預期執行——更大的（更正的）數字獲勝。
優先佇列客戶端
[edit | edit source]client abstract class class!abstract
優先佇列的實現完全是用 Comparable 物件編寫的，但沒有 Comparable 物件！試試建立它吧。
逐字
Comparable comp = new Comparable (); // ERROR
逐字
你會收到一個編譯時訊息，內容類似於“java.lang.Comparable 是一個介面。它不能被例項化。”在 Java 中，抽象類被稱為介面。我之前一直避免使用這個詞，因為它還有其他意思，但現在你必須知道了。
interface
為什麼抽象類不能被例項化？因為抽象類只指定要求（你必須有一個 compareTo 方法）；它不提供實現。
要建立一個 Comparable 物件，你必須建立一個屬於 Comparable 集合的其中一個物件，例如 Integer。然後你可以在任何需要 Comparable 的地方使用該物件。
逐字
PriorityQueue pq = new PriorityQueue ();
Integer item = new Integer (17);
pq.insert (item);
逐字
此程式碼建立一個新的空優先佇列和一個新的 Integer 物件。然後它將 Integer 插入佇列。insert 期望一個 Comparable 作為引數，因此它很樂意接受一個 Integer。如果我們嘗試傳遞一個 Rectangle（不屬於 Comparable），我們會收到一條類似於“方法不相容的型別。需要顯式轉換才能將 java.awt.Rectangle 轉換為 java.lang.Comparable。”的編譯時訊息。
這是編譯器告訴我們，如果我們想進行這種轉換，我們必須顯式地進行轉換。我們可能會嘗試按照它的建議去做。
verbatim Rectangle rect = new Rectangle (); pq.insert ((Comparable) rect); verbatim
但在這種情況下，我們會收到一個執行時錯誤，即 ClassCastException。當 Rectangle 嘗試作為 Comparable 傳遞時，執行時系統會檢查它是否滿足要求，並拒絕它。所以這就是我們按照編譯器建議所得到的。
ClassCastException exception!ClassCastException
要從佇列中取出專案，我們必須反轉該過程。
逐字
while (!pq.empty ())
item = (Integer) pq.remove ();
System.out.println (item);
逐字
此迴圈從佇列中移除所有專案並列印它們。它假設佇列中的專案是 Integer。如果不是，我們會收到一個 ClassCastException。
Golfer 類
[edit | edit source]Golfer class!Golfer abstract class!implementing Comparable
最後，讓我們看看如何建立一個屬於 Comparable 的新類。作為具有“最高”優先順序的非同尋常定義的示例，我們將使用高爾夫球手：
verbatim public class Golfer implements Comparable
String name; int score;
public Golfer (String name, int score)
this.name = name;
this.score = score;
逐字
類定義和建構函式基本相同；不同之處在於我們必須宣告 Golfer 實現 Comparable。在本例中，關鍵字 implements 意味著 Golfer 實現 Comparable 指定的介面。
如果我們嘗試在此時編譯 Golfer.java，我們會收到類似於“類 Golfer 必須宣告為抽象類。它沒有定義介面 java.lang.Comparable 中的 int compareTo(java.lang.Object)。”的訊息。換句話說，要成為 Comparable，Golfer 必須提供一個名為 compareTo 的方法。所以讓我們寫一個吧。
逐字
public int compareTo (Object obj)
Golfer that = (Golfer) obj;
int a = this.score;
int b = that.score;
// for golfers, low is good!
if (a < b) return 1;
if (a > b) return -1;
return 0;
逐字
這裡有兩個地方有點令人驚訝。首先，引數是 Object。這是因為通常情況下，呼叫者不知道要比較的物件是什麼型別。例如，在 PriorityQueue.java 中，當我們呼叫 compareTo 時，我們傳遞一個 Comparable 作為引數。我們不必知道它是一個 Integer 還是一個 Golfer，或者其他什麼東西。
在 compareTo 內部，我們必須將引數從 Object 轉換為 Golfer。像往常一樣，當我們進行這種轉換時存在風險：如果我們轉換為錯誤的型別，我們會得到一個異常。
最後，我們可以建立一些高爾夫球手。
逐字
Golfer tiger = new Golfer ("Tiger Woods", 61);
Golfer phil = new Golfer ("Phil Mickelson", 72);
Golfer hal = new Golfer ("Hal Sutton", 69);
逐字
並將它們放入佇列中。
逐字
pq.insert (tiger);
pq.insert (phil);
pq.insert (hal);
逐字
當我們把它們拉出來的時候。
逐字
while (!pq.empty ())
golfer = (Golfer) pq.remove ();
System.out.println (golfer);
逐字
它們以降序排列（對於高爾夫球手）。
逐字
Tiger Woods 61
Hal Sutton 69
Phil Mickelson 72
逐字
當我們從 Integers 切換到 Golfers 時，我們完全不需要在 PriorityQueue.java 中進行任何更改。因此，我們成功地維護了 PriorityQueue 和使用它的類之間的屏障，允許我們無需修改地重用程式碼。此外，我們能夠讓客戶端程式碼控制 compareTo 的定義，從而使 PriorityQueue 的這種實現更加通用。
queue queueing discipline FIFO priority queue veneer constant time linear time performance hazard linked queue circular buffer abstract class interface
描述
[佇列:] 一組有序的物件，等待某種服務。
[排隊策略:] 決定佇列中哪個成員下一個被移除的規則。
[FIFO:] ``先進先出，一種排隊策略，其中 最先到達的成員最先被移除。
[優先佇列:] 一種排隊策略，其中每個成員都有一個由外部因素決定的優先順序。優先順序最高的成員最先被移除。
[優先佇列:] 一種 ADT，定義了可以在優先佇列上執行的操作。
[裝飾:] 一個類定義，它使用方法定義來實現一個 ADT，這些方法定義是對其他方法的呼叫，有時帶有簡單的轉換。裝飾不執行任何重要工作，但它改進或標準化了客戶端看到的介面。
[效能風險:] 與裝飾相關的風險，即某些方法的實現方式可能效率低下，而客戶端無法察覺。
[常數時間:] 一種操作，其執行時間不依賴於資料結構的大小。
[線性時間:] 一種操作，其執行時間是資料結構大小的線性函式。
[連結串列佇列:] 使用連結串列和對第一個和最後一個節點的引用來實現佇列。
[迴圈緩衝區:] 使用陣列和第一個元素的索引以及下一個可用空間的索引來實現佇列。
[抽象類:] 一組類。抽象類規範列出了類必須滿足的要求才能包含在該組中。
[介面:] Java 中對抽象類的稱呼。不要與該詞語更廣泛的含義混淆。