Java 實現棧資料結構：鏈表、陣列、LinkedList 三種方式完整對比

棧 是「後進先出」(LIFO) 的線性表，僅允許在棧頂進行插入與刪除。本文展示三種經典實現：單向鏈表、動態陣列、委託 LinkedList，附完整代碼、複雜度分析、擴容策略、泛型支援與生產級建議。

核心介面定義

public interface Stack {
    int size();
    boolean isEmpty();
    void push(E element);
    E pop();
    E peek();
}

實現一：單向鏈表 — 經典教科書風格

特點

• **push/pop/peek 皆 O(1)**，無擴容開銷。
• 記憶體分散，節點額外 16-24 字節開銷 (引用 + 物件頭)。
• 適合**未知大小、頻繁增刪、記憶體不連續**場景。

完整代碼

public class LinkedStack implements Stack {
    private static class Node {
        E element;
        Node next;
        Node(E e, Node n) { element = e; next = n; }
    }
    private Node top = null;
    private int size = 0;

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

    @Override public void push(E element) {
        top = new Node<>(element, top); // 新節點指向舊 top，再更新 top
        size++;
    }

    @Override public E pop() {
        if (isEmpty()) throw new EmptyStackException();
        E result = top.element;
        top = top.next; // 移除頂節點
        size--;
        return result;
    }

    @Override public E peek() {
        if (isEmpty()) throw new EmptyStackException();
        return top.element;
    }
}

實現二：動態陣列 — 高效能、緊湊記憶體

特點

• **記憶體連續**，CPU 緩存友好，遍歷/批量操作極快。
• **擴容機制**：滿時擴 2 倍 (或 1.5 倍)，均攤 O(1)。
• **push/pop/peek 皆 O(1) 均攤**。
• 適合**大小可預估、高頻訪問、對 GC 壓力敏感**場景。

完整代碼

public class ArrayStack implements Stack {
    private static final int DEFAULT_CAPACITY = 16;
    private Object[] elements;
    private int top = 0; // 指向下一個可寫入位置，同時也是 size

    public ArrayStack() { this(DEFAULT_CAPACITY); }
    public ArrayStack(int capacity) { elements = new Object[capacity]; }

    @Override public int size() { return top; }
    @Override public boolean isEmpty() { return top == 0; }

    @Override public void push(E element) {
        ensureCapacity(top + 1);
        elements[top++] = element;
    }

    @SuppressWarnings("unchecked")
    @Override public E pop() {
        if (isEmpty()) throw new EmptyStackException();
        E result = (E) elements[--top];
        elements[top] = null; // 釋放引用，助 GC
        return result;
    }

    @SuppressWarnings("unchecked")
    @Override public E peek() {
        if (isEmpty()) throw new EmptyStackException();
        return (E) elements[top - 1];
    }

    private void ensureCapacity(int minCapacity) {
        if (minCapacity <= elements.length) return;
        int newCap = Math.max(elements.length * 2, minCapacity);
        elements = Arrays.copyOf(elements, newCap);
    }
}

實現三：委託 java.util.LinkedList — 生產級最簡

特點

• **零造輪子**，直接複用 JDK 經過充分測試的雙向鏈表。
• addFirst/removeFirst/getFirst 皆 O(1)。
• **泛型完美支援**，無需手寫 @SuppressWarnings。
• 適合**業務代碼、快速原型、非極致效能敏感**場景。

完整代碼

public class DelegatedStack implements Stack {
    private final Deque deque = new LinkedList<>(); // Deque 介面語義更精確

    @Override public int size() { return deque.size(); }
    @Override public boolean isEmpty() { return deque.isEmpty(); }
    @Override public void push(E element) { deque.addFirst(element); }
    @Override public E pop() { return deque.removeFirst(); }
    @Override public E peek() { return deque.getFirst(); }
}

三種實現深度對比

| 維度 | LinkedStack (單向鏈表) | ArrayStack (動態陣列) | DelegatedStack (LinkedList) | |------|------------------------|----------------------|----------------------------| | push 時間 | O(1) | O(1) 均攤 | O(1) | | pop 時間 | O(1) | O(1) | O(1) | | peek 時間 | O(1) | O(1) | O(1) | | 記憶體/元素 | ~24-32 bytes (Node + 引用) | **8 bytes (引用) + 陣列開銷** | ~32 bytes (雙向節點) | | 擴容開銷 | 無 | 複製陣列 (偶發峰值) | 無 (節點級分配) | | 緩存友好度 | 差 | **極佳** | 差 | | GC 壓力 | 高 (大量短命 Node) | 低 (陣列復用) | 中 | | 代碼量 | 中 | 中 | **極少** | | 線程安全 | 否 | 否 | 否 (可包裝 Collections.synchronizedDeque) |

生產級增強建議

1. 線程安全版：new ArrayStack<>() + ReentrantLock，或用 ConcurrentLinkedDeque 實現無鎖棧。
2. 容量上限：ArrayStack 加 maxCapacity 參數，防止惡意/錯誤導致 OOM。
3. 序列化支援：實現 Serializable，ArrayStack 需標記 elements 為 transient 並自定義 writeObject/readObject。
4. 迭代器：實現 Iterable，從棧頂到棧底遍歷 (不修改結構)。
5. 效能基準測試：用 JMH 對比三種實現在「高併發推入/彈出」、「大批量建構」場景下的吞吐與延遲。

總結：如何選擇？

• 面試/教學/嵌入式/無依賴環境 → 手寫 ArrayStack (緊湊、快、展示擴容邏輯) 或 LinkedStack (純粹 LIFO、無擴容)。
• 一般業務開發、微服務、中台系統 → 直接用 DelegatedStack (LinkedList/ArrayDeque)，**ArrayDeque 更優** (陣列雙端隊列，無節點開銷、緩存友好、非線程安全但單執行緒最快)。
• 高併發無鎖棧 → ConcurrentLinkedDeque 或 自己寫 Treiber Stack (CAS 無鎖演算法)。

// 現代 Java 最推薦的棧實現 (單執行緒)
Deque stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
stack.pop(); // "b"
stack.peek(); // "a"

ArrayDeque 以環狀陣列實現雙端隊列，**無容量上限 (自動擴容)、無節點物件、O(1) 雙端操作**，完美替代 Stack (舊類、繼承 Vector、同步開銷大) 與 LinkedList。