您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 隊列原理與手寫實現：從環形緩衝區到生產者消費者模型

編輯：Java 相關知識

隊列是計算機科學中最基礎的數據結構之一，廣泛應用於任務調度、消息中間件、線程池、流量控制等核心場景。本文從底層原理出發，手寫實現基於數組的環形隊列，並延伸至 Java 集合框架與並發隊列的工程化應用。

隊列核心特性

FIFO（先進先出）：最早入隊的元素最先出隊，類似排隊買票
兩端操作：隊尾入隊、隊頭出隊
邏輯與物理分離：邏輯上連續，物理上可環形復用存儲空間

基於數組的環形隊列手寫實現

使用固定大小數組 + 兩個指針（head/tail）+ 元素計數器，實現 O(1) 入隊出隊。

public class ArrayQueue<E> {
    private final Object[] elements;
    private int head = 0;      // 隊頭索引
    private int tail = 0;      // 隊尾索引（指向下一個插入位置）
    private int size = 0;      // 當前元素數量

    @SuppressWarnings("unchecked")
    public ArrayQueue(int capacity) {
        if (capacity < 1) throw new IllegalArgumentException("Capacity must be >= 1");
        this.elements = new Object[capacity];
    }

    /** 入隊：尾部插入，尾指針環形前進 */
    public boolean offer(E e) {
        if (isFull()) return false; // 或拋出異常
        elements[tail] = e;
        tail = (tail + 1) % elements.length;
        size++;
        return true;
    }

    /** 出隊：頭部取出，頭指針環形前進 */
    @SuppressWarnings("unchecked")
    public E poll() {
        if (isEmpty()) return null; // 或拋出異常
        E e = (E) elements[head];
        elements[head] = null; // 幫助 GC
        head = (head + 1) % elements.length;
        size--;
        return e;
    }

    /** 查看隊頭元素不移除 */
    @SuppressWarnings("unchecked")
    public E peek() {
        return isEmpty() ? null : (E) elements[head];
    }

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

關鍵設計點解析

環形索引計算：(index + 1) % capacity 實現指針循環，避免數據搬移
size 計數器：區分「滿」與「空」狀態（head==tail 時無法判斷），犧牲一個存儲槽位換取邏輯清晰
置 null 輔助 GC：出隊後將槽位置空，防止對象游離引用導致內存洩漏
泛型擦除處理：數組創建使用 Object[]，取出時強制轉型並 @SuppressWarnings

Java 集合框架中的隊列體系

接口層次

Collection
  └── Queue
        ├── Deque (雙端隊列)
        │     ├── ArrayDeque (數組雙端隊列，非線程安全)
        │     └── LinkedList (鏈表實現，亦實現 List)
        ├── PriorityQueue (優先級隊列，堆實現)
        └── BlockingQueue (阻塞隊列接口，並發包核心)
              ├── ArrayBlockingQueue (有界數組隊列)
              ├── LinkedBlockingQueue (可選有界鏈表隊列)
              ├── PriorityBlockingQueue (優先級阻塞隊列)
              ├── DelayQueue (延遲隊列)
              ├── SynchronousQueue (同步移交隊列，容量 0)
              └── LinkedTransferQueue (傳輸隊列)

核心實現對比

隊列	底層結構	有界性	線程安全	順序性	典型場景
ArrayDeque	環形數組	無界(擴容)	❌	FIFO/LIFO	單線程棧/隊列、鏈表替代
PriorityQueue	最小堆	無界	❌	優先級序	任務調度、Dijkstra、Huffman
ArrayBlockingQueue	環形數組+ReentrantLock	有界	✅	FIFO	生產消費、線程池工作隊列
LinkedBlockingQueue	鏈表+雙鎖	可選有界	✅	FIFO	高吞吐生產消費、Executors 默認
ConcurrentLinkedQueue	鏈表+CAS	無界	✅(無鎖)	FIFO	高併發非阻塞場景

阻塞隊列與生產者消費者模型

BlockingQueue 提供阻塞語義：

put(e)：隊列滿時阻塞等待
take()：隊列空時阻塞等待
offer(e, timeout) / poll(timeout)：帶超時控制

經典生產消費者範例

public class ProducerConsumerDemo {
    private static final BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);
    private static final Random random = new Random();

    public static void main(String[] args) {
        // 生產者
        new Thread(() -> {
            try {
                while (true) {
                    int num = random.nextInt(100);
                    queue.put(num);
                    System.out.printf("[生產] %d | 隊列大小: %d%n", num, queue.size());
                    Thread.sleep(random.nextInt(500));
                }
            } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        }, "Producer").start();

        // 消費者
        new Thread(() -> {
            try {
                while (true) {
                    int num = queue.take();
                    System.out.printf("[消費] %d | 隊列大小: %d%n", num, queue.size());
                    Thread.sleep(random.nextInt(800));
                }
            } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        }, "Consumer").start();
    }
}