CodeGym /課程 /JAVA 25 SELF /Queue、Deque、Stack：佇列與堆疊的操作

Queue、Deque、Stack：佇列與堆疊的操作

JAVA 25 SELF

等級 27 , 課堂 2

開放

1. Queue 介面：經典佇列（FIFO）

在程式設計與日常生活中，常有不只需要儲存元素，還要控制處理順序的情境。想像超市排隊：越靠前的人會先被服務。這就是 FIFO 原則——「先進先出」。而櫥櫃中的盤子則遵循 LIFO 原則——「後進先出」。在 Java 中，這些原則對應到集合結構：佇列 Queue、雙端佇列 Deque 與堆疊 Stack。

適用場景：

按到達順序處理任務（任務佇列、文件列印、事件處理）。
實作動作回復（undo/redo）——堆疊。
表達式剖析、樹與圖的遍歷（廣度/深度優先）等。

什麼是佇列？

佇列（Queue）是一種遵循 FIFO 原則的集合。元素從尾端加入，從頭端取出。就像在商店排隊：先到者先服務。

Queue 介面的核心方法

方法	說明	回傳
`offer(e)`	在尾端新增元素（不拋出例外）	true/false
`add(e)`	在尾端新增元素（會拋出例外）	true/Exception
`poll()`	刪除並回傳第一個元素	元素/null
`remove()`	刪除並回傳第一個元素	元素/Exception
`peek()`	回傳第一個元素但不刪除	元素/null
`element()`	回傳第一個元素但不刪除	元素/Exception

你會注意到行為相似的方法成對出現。差異在於「溫和程度」：offer、poll、peek 在失敗時回傳特殊值（通常是 null 或 false），不會拋出例外；而 add、remove、element 在邊界情況（例如空佇列、偶爾是容量限制）時會拋出例外。

範例：任務佇列

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> tasks = new LinkedList<>();
        tasks.offer("刷牙");
        tasks.offer("做體操");
        tasks.offer("喝咖啡");

        while (!tasks.isEmpty()) {
            String task = tasks.poll(); // 從佇列頭端取出任務
            System.out.println("正在執行：" + task);
        }
    }
}

輸出：

正在執行：刷牙
正在執行：做體操
正在執行：喝咖啡

為什麼常用 LinkedList？

介面是合約，而實作有多種。常見選擇是 LinkedList，因為它能快速在兩端新增/刪除。不過，極佳的替代方案是 ArrayDeque。也有專用結構：PriorityQueue（優先佇列），下文會介紹。

2. Deque 介面：雙端佇列

Deque（Double Ended Queue，發音近似「deck」）是一種可從兩端（開頭與末尾）新增與刪除元素的佇列。就像有兩個車門的公車：可以從任一側上車/下車。

Deque = 萬用選手：既可當一般佇列（FIFO），也能當堆疊（LIFO），或兩者的混合。

Deque 介面的核心方法

方法	說明	使用範例
`addFirst(e)`	加入到開頭	`ochered.addFirst("A")`
`addLast(e)`	加入到末尾	`ochered.addLast("B")`
`removeFirst()`	從開頭刪除並回傳	`ochered.removeFirst()`
`removeLast()`	從末尾刪除並回傳	`ochered.removeLast()`
`peekFirst()`	查看開頭（不刪除）	`ochered.peekFirst()`
`peekLast()`	查看末尾（不刪除）	`ochered.peekLast()`
`offerFirst(e)`	加入到開頭（不拋出例外）	`ochered.offerFirst("C")`
`offerLast(e)`	加入到末尾（不拋出例外）	`ochered.offerLast("D")`

範例：把 Deque 當佇列與堆疊

import java.util.*;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // 作為佇列（FIFO）
        deque.offerLast("A");
        deque.offerLast("B");
        deque.offerLast("C");
        System.out.println("佇列（FIFO）：");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }

        // 作為堆疊（LIFO）
        deque.offerLast("1");
        deque.offerLast("2");
        deque.offerLast("3");
        System.out.println("堆疊（LIFO）：");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollLast());
        }
    }
}

輸出：

佇列（FIFO）：
A
B
C
堆疊（LIFO）：
3
2
1

為什麼選擇 ArrayDeque？

ArrayDeque 是以陣列實作的快速且精簡的 Deque。作為堆疊與佇列時通常比舊的 Stack 更快更可靠，且沒有固定大小（僅受記憶體限制）。

3. Stack：堆疊——後進先出（LIFO）

堆疊是一種遵循 LIFO 原則的集合：取出的是最後放上去的頂端元素。它在程式設計中對於動作歷史（undo）、遞迴結構（樹/圖）遍歷、運算式求值等都很有用。

Stack 類（以及為何不建議使用）

Java 有一個 Stack 類，它繼承自已過時的 Vector。現今不建議在新專案中使用它，更推薦 Deque/ArrayDeque。

堆疊的方法（以 Deque 提供）

方法	說明
`push(e)`	把元素推入堆疊頂端
`pop()`	彈出並回傳頂端元素
`peek()`	查看頂端元素

注意：在 Deque 中，這些操作分別對應 addFirst/removeFirst/peekFirst，但也提供「堆疊風格」的方法名稱 push/pop/peek 以利相容。

範例：用 ArrayDeque 實作堆疊

import java.util.*;

public class StackDemo {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("第一");
        stack.push("第二");
        stack.push("第三");

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

輸出：

第三
第二
第一

為什麼不用 Stack？

Stack 已同步化（較慢），且繼承過時的 Vector。
ArrayDeque 通常更快且更精簡，且不會阻塞執行緒。
在新程式碼中看到 Stack——通常可以改用 ArrayDeque。

4. 何時該用哪一種

結構	原則	使用場景	實作範例
Queue	FIFO	任務佇列、事件處理、列印、客戶排隊	`LinkedList, ArrayDeque, PriorityQueue`
Stack	LIFO	Undo/redo、遞迴、剖析器、樹遍歷	`ArrayDeque`
Deque	FIFO/LIFO	緩衝區、迴文、雙端佇列、通用任務	`ArrayDeque, LinkedList`

生活中的例子：

銀行排隊——Queue。
編輯器的動作歷史——Stack。
兩端上下車的公車佇列——Deque。

5. 程式範例：用小型應用實作佇列與堆疊

範例 1：文件列印佇列

import java.util.*;

public class PrintQueueApp {
    public static void main(String[] args) {
        Queue<String> printQueue = new ArrayDeque<>();
        printQueue.offer("Document1.pdf");
        printQueue.offer("Document2.docx");
        printQueue.offer("Document3.xls");

        while (!printQueue.isEmpty()) {
            String doc = printQueue.poll();
            System.out.println("正在列印：" + doc);
        }
    }
}

範例 2：動作復原堆疊（undo）

import java.util.*;

public class UndoStackApp {
    public static void main(String[] args) {
        Deque<String> undoStack = new ArrayDeque<>();
        undoStack.push("插入文字");
        undoStack.push("變更顏色");
        undoStack.push("刪除圖片");

        System.out.println("最後一個動作：" + undoStack.peek()); // 刪除圖片

        while (!undoStack.isEmpty()) {
            System.out.println("復原：" + undoStack.pop());
        }
    }
}

範例 3：雙端佇列

import java.util.*;

public class DequeApp {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("A");
        deque.addLast("B");
        deque.addFirst("C");
        deque.addLast("D");

        System.out.println("從頭端取出： " + deque.removeFirst()); // C
        System.out.println("從尾端取出： " + deque.removeLast());   // D
        System.out.println("剩下： " + deque); // [A, B]
    }
}

6. 實作細節與注意事項

ArrayDeque 是多數情境下最快且最通用的佇列/堆疊實作。
LinkedList 也實作了 Deque；有時有用，但在短佇列上通常比 ArrayDeque 慢。
PriorityQueue 是優先佇列：順序由優先權決定（自然順序或透過 Comparator），不是一般的 FIFO 佇列。
Stack 已過時且同步化；在新專案中更建議使用 ArrayDeque。
Deque 的好處是可同時操作結構的開頭與末尾，一個抽象就能涵蓋佇列與堆疊的情境。

7. 操作佇列與堆疊時的常見錯誤

錯誤 1：用 Stack 取代 Deque。
許多新手看到 Stack 這個類名就直接使用。在現代專案中，請改用 ArrayDeque（或 LinkedList）並搭配 push/pop 方法。

錯誤 2：違反資料結構的運作原則。
嘗試用索引存取佇列/堆疊元素，例如 queue.get(0) 或 stack.get(0)。這樣不行——請使用適合佇列與堆疊的方法（peek、poll、pop 等）。

錯誤 3：未檢查就使用 remove()/element()/add()。
remove、element、add 在結構為空/容量受限時可能拋出例外。更安全的是使用「溫和」的 offer、poll、peek，它們會回傳特殊值。

錯誤 4：在 ArrayDeque 中使用 null 元素。
ArrayDeque 不允許 null。嘗試加入 null 會導致 NullPointerException。

錯誤 5：把 PriorityQueue 當成一般佇列。
在 PriorityQueue 中，順序由優先權決定（自然順序或透過 Comparator）。若需要嚴格的 FIFO，請使用 ArrayDeque 或 LinkedList。

錯誤 6：在 for-each 遍歷時修改佇列/堆疊。
在 for-each 期間刪除集合元素可能導致 ConcurrentModificationException。需要刪除時，請使用迭代器，或如範例所示在迴圈中用 poll/pop。

先前先前課堂

下一個下一堂課

留言

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION