Java Deque

Deque（Double-Ended Queue）是雙端佇列，可以從兩端進行插入和刪除操作，既可以當作佇列使用，也可以當作堆疊使用。

基本介面

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.LinkedList;

// 常用實作
Deque<String> deque1 = new ArrayDeque<>();  // 推薦，效能較好
Deque<String> deque2 = new LinkedList<>();  // 也可以用

主要方法

兩端操作

Deque<String> deque = new ArrayDeque<>();

// 從前端加入
deque.addFirst("B");
deque.addFirst("A");  // [A, B]

// 從後端加入
deque.addLast("C");
deque.addLast("D");   // [A, B, C, D]

// 從前端移除
String first = deque.removeFirst();  // "A", 剩餘 [B, C, D]

// 從後端移除
String last = deque.removeLast();    // "D", 剩餘 [B, C]

// 查看（不移除）
String peekFirst = deque.peekFirst();  // "B"
String peekLast = deque.peekLast();    // "C"

當作佇列使用 (FIFO)

Deque<String> queue = new ArrayDeque<>();

// 加入（從後端）
queue.offer("A");
queue.offer("B");
queue.offer("C");  // [A, B, C]

// 移除（從前端）
String first = queue.poll();  // "A"

// 查看
String peek = queue.peek();   // "B"

當作堆疊使用 (LIFO)

Deque<String> stack = new ArrayDeque<>();

// 推入
stack.push("A");
stack.push("B");
stack.push("C");  // [C, B, A]（C 在頂端）

// 彈出
String top = stack.pop();  // "C"

// 查看頂端
String peek = stack.peek();  // "B"

建議：使用 Deque 而非 Stack 類別，因為 Stack 繼承自 Vector，有同步開銷

遍歷

Deque<String> deque = new ArrayDeque<>(Arrays.asList("A", "B", "C"));

// for-each（從前到後）
for (String s : deque) {
    System.out.print(s + " ");  // A B C
}

// Iterator（從前到後）
Iterator<String> it = deque.iterator();
while (it.hasNext()) {
    System.out.print(it.next() + " ");  // A B C
}

// descendingIterator（從後到前）
Iterator<String> descIt = deque.descendingIterator();
while (descIt.hasNext()) {
    System.out.print(descIt.next() + " ");  // C B A
}

ArrayDeque vs LinkedList

// ArrayDeque 不允許 null
Deque<String> arrayDeque = new ArrayDeque<>();
// arrayDeque.add(null);  // NullPointerException

// LinkedList 允許 null
Deque<String> linkedList = new LinkedList<>();
linkedList.add(null);  // OK

實際範例

瀏覽器歷史紀錄

public class BrowserHistory {
    private Deque<String> backStack = new ArrayDeque<>();
    private Deque<String> forwardStack = new ArrayDeque<>();
    private String currentPage;

    public void visit(String url) {
        if (currentPage != null) {
            backStack.push(currentPage);
        }
        currentPage = url;
        forwardStack.clear();  // 清除前進紀錄
        System.out.println("訪問：" + url);
    }

    public void back() {
        if (!backStack.isEmpty()) {
            forwardStack.push(currentPage);
            currentPage = backStack.pop();
            System.out.println("返回：" + currentPage);
        }
    }

    public void forward() {
        if (!forwardStack.isEmpty()) {
            backStack.push(currentPage);
            currentPage = forwardStack.pop();
            System.out.println("前進：" + currentPage);
        }
    }

    public String getCurrentPage() {
        return currentPage;
    }
}

// 使用
BrowserHistory history = new BrowserHistory();
history.visit("google.com");
history.visit("github.com");
history.visit("stackoverflow.com");
history.back();     // 返回：github.com
history.back();     // 返回：google.com
history.forward();  // 前進：github.com

滑動視窗最大值

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0) return new int[0];

    int[] result = new int[nums.length - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();  // 存放索引

    for (int i = 0; i < nums.length; i++) {
        // 移除超出視窗範圍的元素
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        // 移除比當前元素小的元素
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        deque.offerLast(i);

        // 視窗形成後記錄最大值
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }

    return result;
}

回文檢查

public boolean isPalindrome(String s) {
    Deque<Character> deque = new ArrayDeque<>();

    // 只保留字母和數字
    for (char c : s.toLowerCase().toCharArray()) {
        if (Character.isLetterOrDigit(c)) {
            deque.addLast(c);
        }
    }

    // 從兩端比較
    while (deque.size() > 1) {
        if (!deque.pollFirst().equals(deque.pollLast())) {
            return false;
        }
    }

    return true;
}

任務排程

public class TaskScheduler {
    private Deque<Runnable> highPriority = new ArrayDeque<>();
    private Deque<Runnable> normalPriority = new ArrayDeque<>();

    public void addHighPriority(Runnable task) {
        highPriority.addFirst(task);  // 高優先級從前端加入
    }

    public void addNormalPriority(Runnable task) {
        normalPriority.addLast(task);  // 一般任務從後端加入
    }

    public void processNext() {
        Runnable task = null;

        if (!highPriority.isEmpty()) {
            task = highPriority.pollFirst();
        } else if (!normalPriority.isEmpty()) {
            task = normalPriority.pollFirst();
        }

        if (task != null) {
            task.run();
        }
    }
}

重點整理

• Deque 是雙端佇列，可從兩端操作
• ArrayDeque 效能通常優於 LinkedList
• ArrayDeque 不允許 null 值
• 可當作 Queue（FIFO）或 Stack（LIFO）使用
• 建議使用 Deque 取代 Stack 類別
• 常用於需要兩端操作的場景：歷史紀錄、滑動視窗等