Java 實作佇列資料結構：基於 Vector 的完整範例

佇列資料結構核心特性

佇列是「先進先出」（FIFO, First-In-First-Out）的線性資料結構，僅允許在隊尾插入、隊首刪除。核心操作包含：入隊、出隊、取隊首元素、判斷空佇列、清空佇列、搜尋元素位置。Java 內建 java.util.Vector 具備動態陣列特性且執行緒安全，極適合作為佇列底層儲存。

完整佇列類別實作

import java.util.Vector;

public class Queue extends Vector {
    public Queue() {
        super();
    }
    
    // 入隊：在尾端加入元素
    public synchronized void enq(Object x) {
        super.addElement(x);
    }
    
    // 出隊：移除並回傳隊首元素
    public synchronized Object deq() {
        if (this.empty()) {
            throw new EmptyQueueException();
        }
        Object x = super.elementAt(0);
        super.removeElementAt(0);
        return x;
    }
    
    // 取隊首元素但不移除
    public synchronized Object front() {
        if (this.empty()) {
            throw new EmptyQueueException();
        }
        return super.elementAt(0);
    }
    
    // 判斷是否為空
    public boolean empty() {
        return super.isEmpty();
    }
    
    // 清空佇列
    public synchronized void clear() {
        super.removeAllElements();
    }
    
    // 搜尋元素位置（從隊首算起），不存在回傳 -1
    public int search(Object x) {
        return super.indexOf(x);
    }
}

// 自訂例外：空佇列操作
class EmptyQueueException extends RuntimeException {
    public EmptyQueueException() {
        super("Queue is empty");
    }
}

關鍵設計說明

• 繼承 Vector：直接獲得動態擴容、執行緒安全、豐富集合操作
• synchronized 關鍵字：雖然 Vector 方法已同步，但複合操作（如檢查空後再取元素）需額外同步確保原子性
• 自訂例外：EmptyQueueException 繼承 RuntimeException，呼叫端可選擇捕獲或拋出
• 搜尋語意：search() 回傳距隊首的索引，符合佇列邏輯視角

使用範例

public class QueueDemo {
    public static void main(String[] args) {
        Queue q = new Queue();
        
        // 入隊
        q.enq("任務A");
        q.enq("任務B");
        q.enq("任務C");
        System.out.println("佇列大小: " + q.size()); // 3
        
        // 檢視隊首
        System.out.println("下一個任務: " + q.front()); // 任務A
        
        // 出隊處理
        while (!q.empty()) {
            System.out.println("執行: " + q.deq());
        }
        // 輸出: 執行: 任務A -> 執行: 任務B -> 執行: 任務C
    }
}

現代化替代方案

Java 5+ 推薦使用 java.util.Queue 介面與實作類別：

• LinkedList：非執行緒安全，單執行緒高效能
• ArrayDeque：雙端佇列，效能優於 LinkedList
• ConcurrentLinkedQueue：無鎖執行緒安全，高併發適用
• BlockingQueue 介面（ArrayBlockingQueue, LinkedBlockingQueue）：支援阻塞式 put/take，生產者-消費者模式首選

效能考量

本範例基於 Vector 實作，removeElementAt(0) 需搬移所有後續元素，時間複雜度 O(n)。高頻出隊場景建議改用 ArrayDeque（O(1) 兩端操作）或環形緩衝區實作。