隊列 (Queue) 是先進先出 (FIFO) 的線性資料結構。Java 集合框架雖提供 Queue 介面與 LinkedList、ArrayDeque 等實作,但理解如何從基礎類別 (如 Vector) 手刻一個執行緒安全的隊列,有助於掌握同步機制與資料結構內部運作。本文提供一個基於 Vector 的完整隊列實作,支援六大核心操作,並包含自訂例外處理。
| 方法 | 功能 | 異常處理 |
|---|---|---|
enq(E x) | 尾端插入元素 | 無 |
deq() | 移除並回傳頭端元素 | 空隊列拋出 EmptyQueueException |
front() | 檢視頭端元素 (不移除) | 空隊列拋出 EmptyQueueException |
empty() | 判斷是否為空 | 回傳 boolean |
clear() | 清空隊列 | 無 |
search(E x) | 搜尋元素位置 (0-based),不存在回傳 -1 | 無 |
public class EmptyQueueException extends Exception {
public EmptyQueueException() {
super("Queue is empty");
}
public EmptyQueueException(String msg) {
super(msg);
}
}
import java.util.Vector;
public class Queue<E> extends Vector<E> {
/** 尾端插入元素 */
public synchronized void enq(E x) {
super.addElement(x);
}
/** 移除並回傳頭端元素 */
public synchronized E deq() throws EmptyQueueException {
if (this.empty()) {
throw new EmptyQueueException("Cannot deq from empty queue");
}
E x = super.elementAt(0);
super.removeElementAt(0);
return x;
}
/** 檢視頭端元素 */
public synchronized E front() throws EmptyQueueException {
if (this.empty()) {
throw new EmptyQueueException("Cannot front empty queue");
}
return super.elementAt(0);
}
/** 判斷是否為空 */
public boolean empty() {
return super.isEmpty();
}
/** 清空隊列 */
public synchronized void clear() {
super.removeAllElements();
}
/** 搜尋元素索引 */
public int search(E x) {
return super.indexOf(x);
}
}
Vector 內建同步 (所有方法皆為 synchronized),直接繼承即獲得執行緒安全。addElement、removeElementAt、elementAt、indexOf 等操作,完美對應隊列語意。所有修改操作 (enq、deq、clear) 與複合讀取 (front) 均宣告 synchronized,確保原子性。雖 Vector 單一方法已同步,但複合操作 (如 if (!empty()) deq()) 需額外鎖定,本實作將邏輯封裝在同步方法內,避免競態條件。
removeElementAt(0) 導致後續元素整體前移,時間複雜度 O(n)。高頻操作場景建議改用 ArrayDeque (環狀陣列) 或 LinkedList (雙向鏈表),兩者皆為 O(1)。java.util.concurrent.ArrayBlockingQueue (有界) 或 LinkedBlockingQueue (無界),提供更豐富的阻塞操作 (put/take) 與更佳效能。public class QueueDemo {
public static void main(String[] args) {
Queue<String> q = new Queue<>();
q.enq("Task-1");
q.enq("Task-2");
q.enq("Task-3");
System.out.println("Front: " + q.front()); // Task-1
System.out.println("Search Task-2: " + q.search("Task-2")); // 1
while (!q.empty()) {
System.out.println("Processing: " + q.deq());
}
// 輸出:
// Processing: Task-1
// Processing: Task-2
// Processing: Task-3
}
}
@Test void testDeqEmptyThrows() {
Queue<Integer> q = new Queue<>();
assertThrows(EmptyQueueException.class, q::deq);
}
@Test void testFifoOrder() {
Queue<Integer> q = new Queue<>();
q.enq(1); q.enq(2); q.enq(3);
assertEquals(1, q.deq());
assertEquals(2, q.deq());
assertEquals(3, q.deq());
assertTrue(q.empty());
}
本文展示了如何以 Vector 為基底,在 30 行程式碼內完成一個功能完整、執行緒安全的隊列類別。雖然生產環境建議直接使用 JCF 或 java.util.concurrent 提供的高效能實作,但親手實作過程能深化對同步機制、資料結構遷移、例外設計的理解,是 Java 進階學習的優秀練習題。