Java 手寫棧：陣列實作、動態擴容與泛型支援

棧 (Stack) 資料結構

後進先出 (LIFO)。核心操作：

• push(E) — 入棧 O(1) 攤還
• pop() — 出棧 O(1)
• peek() — 查看頂端不移除
• isEmpty()、size()

Java java.util.Stack 繼承 Vector (同步化、效能差)，實務建議用 ArrayDeque 或自行實作。

完整 ArrayStack 實作

import java.util.Arrays;

public class ArrayStack<T> {
    private Object[] elements;
    private int size;
    private static final int DEFAULT_CAPACITY = 16;

    public ArrayStack() { this(DEFAULT_CAPACITY); }
    public ArrayStack(int capacity) {
        if (capacity < 0) throw new IllegalArgumentException("Capacity: " + capacity);
        elements = new Object[capacity];
    }

    // ---- 入棧 ----
    public void push(T item) {
        ensureCapacity(size + 1);
        elements[size++] = item;
    }

    // ---- 出棧 ----
    @SuppressWarnings("unchecked")
    public T pop() {
        if (size == 0) throw new IllegalStateException("Stack empty");
        T item = (T) elements[--size];
        elements[size] = null; // 釋放引用助 GC
        return item;
    }

    // ---- 查看頂端 ----
    @SuppressWarnings("unchecked")
    public T peek() {
        if (size == 0) return null;
        return (T) elements[size - 1];
    }

    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
    public void clear() { Arrays.fill(elements, 0, size, null); size = 0; }

    // ---- 動態擴容 (1.5 倍) ----
    private void ensureCapacity(int minCapacity) {
        if (minCapacity - elements.length > 0) {
            int newCap = elements.length + (elements.length >> 1);
            if (newCap < minCapacity) newCap = minCapacity;
            elements = Arrays.copyOf(elements, newCap);
        }
    }

    // ---- 列印 (除錯用) ----
    public void printStack() {
        System.out.print("[Bottom] ");
        for (int i = 0; i < size; i++) System.out.print(elements[i] + " ");
        System.out.println(" [Top]");
    }

    // ---- 測試 ----
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack<>();
        stack.push("A"); stack.push("B"); stack.push("C");
        stack.printStack(); // [Bottom] A B C [Top]
        System.out.println("Peek: " + stack.peek()); // C
        System.out.println("Pop: " + stack.pop());   // C
        System.out.println("Pop: " + stack.pop());   // B
        stack.push("D");
        stack.printStack(); // [Bottom] A D [Top]
    }
}

關鍵實作細節

1. 泛型擦除 + Object[]：標準集合做法，@SuppressWarnings("unchecked") 只在確定安全處使用。
2. elements[size] = null：pop() 後清空引用，避免「過期引用」導致記憶體洩漏 (Effective Java Item 6)。
3. 擴容 1.5 倍：newCap = old + (old >> 1)，比 2 倍更節省記憶體，JDK ArrayList 同策略。
4. 拋出 IllegalStateException：空棧 pop() 符合集合框架慣例 (ArrayDeque 同)。

效能對照 (百萬次操作)

應用場景

• 🔙 瀏覽器前進/後退、編輯器撤銷/重做
• 🧮 運算式求值 (中綴轉後綴、計算機)
• 🌲 樹/圖 深度優先搜尋 (DFS) 遞迴改迭代
• 🔧 編譯器語法分析、括號匹配

進階：支援迭代器

實作 Iterable<T> 並提供 Iterator<T> (從頂端向下)，即可支援 for (T item : stack) 語法，方便除錯與轉集合。

手寫棧能深入理解 LIFO 邏輯、陣列擴容、記憶體釋放與泛型擦除，是資料結構與集合原理的入門必修課。

1. 上一篇文章： Java 記憶體分配進階：陣列限制、Unsafe 離堆與巨大記憶體實戰
2. 下一篇文章： Debian 7/8 安裝 Oracle Java 8 完整指令教學

Java 相關知識

深入解析 Java HashMap 核心原理與源碼實現

HashMap 整體結構概覽 HashMap 是 Java

Thumbnailator 圖片處理框架全攻略：從入門到實戰

為什麼選擇 Thumbnailator？ Java 原生圖片

Java 套接字程式設計（下）：UDP 與多點傳送

資料報套接字 因使用流套接字每個連接均需花費一定時間，為減少

善用物件導向設計模式替換 Switch-Case 與 If-Else

在日常 Java 開發中，針對狀態或類型進行判斷時，swit