Java 數組模擬優先級隊列數據結構實現

優先級隊列核心概念

優先級隊列是一種特殊隊列，每個元素擁有優先級，優先級高（數值小）的元素先出隊。與普通隊列的 FIFO 不同，它按優先級排序，適用於任務調度、路由選擇、Huffman 編碼等場景。

數組實現思路

• 使用整型數組存儲元素
• 插入時維持數組有序（升序：小值在前 = 高優先級）
• 出隊直接取數組第一個元素
• 為簡化演示，採用固定容量 + 冒泡排序（生產環境建議用堆）

完整代碼實現

package datastruct;

import java.util.Arrays;

/**
 * 基於數組的優先級隊列（教學演示版）
 * 優先級：數值越小優先級越高
 */
public class ArrayPriorityQueue {
    private final int[] elements;
    private int size;
    private final int capacity;

    public ArrayPriorityQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("容量必須大於 0");
        this.capacity = capacity;
        this.elements = new int[capacity];
        this.size = 0;
    }

    /** 入隊 - 保持升序 */
    public void enqueue(int value) {
        if (isFull()) {
            throw new IllegalStateException("隊列已滿，無法入隊");
        }
        // 找到插入位置（從後向前移動大於 value 的元素）
        int i = size - 1;
        while (i >= 0 && elements[i] > value) {
            elements[i + 1] = elements[i];
            i--;
        }
        elements[i + 1] = value;
        size++;
        System.out.println("入隊 " + value + " → " + Arrays.toString(Arrays.copyOf(elements, size)));
    }

    /** 出隊 - 取最小值（索引 0） */
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("隊列為空，無法出隊");
        }
        int min = elements[0];
        // 所有元素前移
        System.arraycopy(elements, 1, elements, 0, size - 1);
        size--;
        elements[size] = 0; // 清理引用
        System.out.println("出隊 " + min + " → " + Arrays.toString(Arrays.copyOf(elements, size)));
        return min;
    }

    /** 查看隊首元素不移除 */
    public int peek() {
        if (isEmpty()) throw new IllegalStateException("隊列為空");
        return elements[0];
    }

    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == capacity; }
    public int size() { return size; }

    public static void main(String[] args) {
        ArrayPriorityQueue pq = new ArrayPriorityQueue(5);
        
        System.out.println("=== 入隊演示 ===");
        pq.enqueue(5);
        pq.enqueue(2);
        pq.enqueue(8);
        pq.enqueue(1);
        pq.enqueue(3);
        
        System.out.println("\n=== 出隊演示（應按 1,2,3,5,8 順序） ===");
        while (!pq.isEmpty()) {
            pq.dequeue();
        }
    }
}

運行結果

=== 入隊演示 ===
入隊 5 → [5]
入隊 2 → [2, 5]
入隊 8 → [2, 5, 8]
入隊 1 → [1, 2, 5, 8]
入隊 3 → [1, 2, 3, 5, 8]

=== 出隊演示 ===
出隊 1 → [2, 3, 5, 8]
出隊 2 → [3, 5, 8]
出隊 3 → [5, 8]
出隊 5 → [8]
出隊 8 → []

複雜度分析與優化方向

生產環境建議

實際開發中直接使用 java.util.PriorityQueue，它基於二叉堆實現，性能優異且線程不安全（多線程用 PriorityBlockingQueue）。

// 正確使用 JDK 內置優先級隊列
PriorityQueue pq = new PriorityQueue<>(); // 默認小頂堆
pq.offer(5);
pq.offer(2);
pq.offer(8);
System.out.println(pq.poll()); // 2
System.out.println(pq.poll()); // 5

通過手寫數組版本理解底層原理，實際項目用成熟庫，這是數據結構學習的正確姿勢。