Java 雙端循環隊列 (Deque) 陣列實作完整指南

資料結構簡介

雙端循環隊列 允許在隊列頭尾兩端進行插入與刪除操作，結合了隊列 (FIFO) 與堆疊 (LIFO) 的特性。以陣列實作時，利用模運算實現索引循環，達到 O(1) 時間複雜度的雙端操作。

核心欄位設計

private int maxSize;      // 陣列最大容量
private int left;         // 左端指標 (指向頭部元素)
private int right;        // 右端指標 (指向尾部元素)
private int nItems;       // 當前元素數量
private long[] myDeque;   // 底層儲存陣列

建構子初始化

public Deque(int maxSize) {
    this.maxSize = maxSize;
    this.myDeque = new long[maxSize];
    this.nItems = 0;
    this.left = maxSize;   // 關鍵：初始化為 maxSize，首次插入左端時 --left 變為 maxSize-1
    this.right = -1;       // 關鍵：初始化為 -1，首次插入右端時 ++right 變為 0
}

核心操作實作

左側插入

public void insertLeft(long value) {
    if (left == 0) left = maxSize;  // 循環回繞
    myDeque[--left] = value;        // 先遞減再賦值
    nItems++;
}

右側插入

public void insertRight(long value) {
    if (right == maxSize - 1) right = -1;  // 循環回繞
    myDeque[++right] = value;              // 先遞增再賦值
    nItems++;
}

左側移除

public long removeLeft() {
    long temp = myDeque[left++];  // 取值後指標右移
    if (left == maxSize) left = 0; // 循環回繞
    nItems--;
    return temp;
}

右側移除

public long removeRight() {
    long temp = myDeque[right--];  // 取值後指標左移
    if (right == -1) right = maxSize - 1; // 循環回繞
    nItems--;
    return temp;
}

輔助方法

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

完整程式碼

package source;

public class Deque {
    private int maxSize;
    private int left;
    private int right;
    private int nItems;
    private long[] myDeque;

    public Deque(int maxSize) {
        this.maxSize = maxSize;
        this.myDeque = new long[maxSize];
        this.nItems = 0;
        this.left = maxSize;
        this.right = -1;
    }

    public void insertLeft(long value) {
        if (left == 0) left = maxSize;
        myDeque[--left] = value;
        nItems++;
    }

    public void insertRight(long value) {
        if (right == maxSize - 1) right = -1;
        myDeque[++right] = value;
        nItems++;
    }

    public long removeLeft() {
        long temp = myDeque[left++];
        if (left == maxSize) left = 0;
        nItems--;
        return temp;
    }

    public long removeRight() {
        long temp = myDeque[right--];
        if (right == -1) right = maxSize - 1;
        nItems--;
        return temp;
    }

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

應用場景

• 滑動視窗最大值/最小值：單調隊列核心資料結構
• 瀏覽器前進/後退歷史：雙端操作天然契合
• 工作竊取演算法：雙端隊列支援雙端取任務
• 替代 Stack/Queue：JDK ArrayDeque 即是此結構高效實作

注意事項

• 此實作為教學示意，非線程安全，多線程環境請使用 java.util.concurrent.LinkedBlockingDeque 或 ConcurrentLinkedDeque
• 固定容量陣列會有擴容限制，生產環境建議直接使用 JDK ArrayDeque (支援動態擴容)
• 索引循環邏輯是核心難點，實作時務必仔細驗證邊界條件