萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Java 隊列類完整實作:基於 Vector 的執行緒安全泛型佇列

前言

隊列 (Queue) 是先進先出 (FIFO) 的線性資料結構。Java 集合框架雖提供 Queue 介面與 LinkedList、ArrayDeque 等實作,但理解如何從基礎類別 (如 Vector) 手刻一個執行緒安全的隊列,有助於掌握同步機制與資料結構內部運作。本文提供一個基於 Vector 的完整隊列實作,支援六大核心操作,並包含自訂例外處理。

介面設計:六大核心操作

方法功能異常處理
enq(E x)尾端插入元素無
deq()移除並回傳頭端元素空隊列拋出 EmptyQueueException
front()檢視頭端元素 (不移除)空隊列拋出 EmptyQueueException
empty()判斷是否為空回傳 boolean
clear()清空隊列無
search(E x)搜尋元素位置 (0-based),不存在回傳 -1無

完整原始碼 (JDK 1.1.5 相容,可輕鬆升級至泛型)

1. 自訂例外類別

public class EmptyQueueException extends Exception {
    public EmptyQueueException() {
        super("Queue is empty");
    }
    public EmptyQueueException(String msg) {
        super(msg);
    }
}

2. 隊列主類別 (Java 5+ 泛型版)

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?

  • Vector 內建同步 (所有方法皆為 synchronized),直接繼承即獲得執行緒安全。
  • 底層動態陣列支援 addElement、removeElementAt、elementAt、indexOf 等操作,完美對應隊列語意。
  • 程式碼極度精簡,維護成本低。

同步策略

所有修改操作 (enq、deq、clear) 與複合讀取 (front) 均宣告 synchronized,確保原子性。雖 Vector 單一方法已同步,但複合操作 (如 if (!empty()) deq()) 需額外鎖定,本實作將邏輯封裝在同步方法內,避免競態條件。

效能考量

  • 優點:實作簡單、執行緒安全、API 直觀。
  • 缺點:removeElementAt(0) 導致後續元素整體前移,時間複雜度 O(n)。高頻操作場景建議改用 ArrayDeque (環狀陣列) 或 LinkedList (雙向鏈表),兩者皆為 O(1)。
  • 現代替代:Java 5+ 推薦使用 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
    }
}

單元測試要點 (JUnit 5)

@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 進階學習的優秀練習題。

copyright © 萬盛學電腦網 all rights reserved