Java 實作堆疊與佇列：基於 LinkedList 的封裝設計模式

設計理念：介面導向與封裝

Java LinkedList 實作了 List、Deque、Queue 多重介面，功能豐富但過於暴露內部細節。透過封裝模式，僅暴露堆疊 (LIFO) 或佇列 (FIFO) 所需的最小介面集合，既能確保語義正確性，又能隱藏實作細節，提升代碼安全性與可維護性。

堆疊實作：Stack<T>

import java.util.LinkedList;

public class Stack<T> {
    private LinkedList<T> storage = new LinkedList<T>();

    /** 入堆疊 (推入堆疊頂端) */
    public void push(T v) {
        storage.addFirst(v);
    }

    /** 查看堆疊頂端元素 (不移除) */
    public T peek() {
        return storage.getFirst();
    }

    /** 出堆疊 (移除並回傳頂端元素) */
    public T pop() {
        return storage.removeFirst();
    }

    /** 判斷堆疊是否為空 */
    public boolean empty() {
        return storage.isEmpty();
    }

    /** 列印堆疊內容 (除錯用) */
    @Override
    public String toString() {
        return storage.toString();
    }
}

設計亮點

• 語義精確： 僅提供 push/pop/peek/empty 四大核心操作，符合堆疊 LIFO 語義
• 效能最優： addFirst/removeFirst/getFirst 皆為 O(1) 常數時間
• 泛型支援： 型別安全，編譯期檢查
• 委派模式： 內部委派 LinkedList 實作，零額外負擔

佇列實作：MyQueue<T>

import java.util.LinkedList;
import java.util.Queue;

public class MyQueue<T> {
    private Queue<T> storage = new LinkedList<T>();

    /** 插入元素至佇列尾部 */
    public void offer(T v) {
        storage.offer(v);
    }

    /** 檢索但不移除佇列頭部，空佇列回傳 null */
    public T peek() {
        return storage.peek();
    }

    /** 檢索但不移除佇列頭部，空佇列拋出異常 */
    public T element() {
        return storage.element();
    }

    /** 檢索並移除佇列頭部，空佇列回傳 null */
    public T poll() {
        return storage.poll();
    }

    /** 檢索並移除佇列頭部，空佇列拋出異常 */
    public T remove() {
        return storage.remove();
    }

    /** 判斷佇列是否為空 */
    public boolean empty() {
        return storage.isEmpty();
    }

    /** 列印佇列內容 (除錯用) */
    @Override
    public String toString() {
        return storage.toString();
    }
}

設計亮點

• 完整對應 Queue 介面： 封裝 offer/peek/element/poll/remove 五大核心方法，涵蓋「失敗回傳 null」與「失敗拋出異常」兩種語義
• 介面導向宣告： 成員變數宣告為 Queue<T> 而非 LinkedList<T>，降低耦合度，未來可替換為 ArrayDeque、PriorityQueue 等實作
• FIFO 語義保證： 僅暴露佇列操作，禁止任意位置插入/刪除

為什麼不直接使用 java.util.Stack 與 java.util.Queue？

使用範例

堆疊應用：括號匹配驗證

public boolean isValidParentheses(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stack.empty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stack.empty();
}

佇列應用：廣度優先搜尋 (BFS)

public void bfs(TreeNode root) {
    MyQueue<TreeNode> queue = new MyQueue<>();
    queue.offer(root);
    while (!queue.empty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

進階擴展建議

1. 固定容量版本： 加入 maxSize 參數，滿載時 push/offer 拋出異常或阻塞
2. 執行緒安全版本： 內部使用 Collections.synchronizedList 或改用 ConcurrentLinkedQueue/ArrayBlockingQueue
3. 可迭代支援： 實作 Iterable<T> 介面，支援 for-each 遍歷 (堆疊從頂到底、佇列從頭到尾)
4. 序列化支援： 實作 Serializable，確保內部 LinkedList 可序列化

總結

本文展示基於 LinkedList 封裝堆疊與佇列的最佳實踐：

• 堆疊使用 addFirst/removeFirst/getFirst 實現 O(1) LIFO
• 佇列委派 Queue 介面實現 O(1) FIFO，支援雙重語義 (null/異常)
• 皆採用泛型、介面導向、委派模式，符合「組合優於繼承」原則
• 避免使用過時的 Vector、Stack 等類別

這種封裝設計不僅提升代碼可讀性與安全性，更為未來效能優化 (如改用 ArrayDeque) 預留彈性空間。