《Java 編程思想》泛型實戰：鏈式堆疊 LinkedStack 完整解析

《Thinking in Java》中 LinkedStack<T> 是理解泛型、內部類、哨兵節點、鏈表結構的經典範例。本文逐行解析原始碼，並補充泛型擦除、型別參數約束、實際應用場景。

完整原始碼（含註解）

package generics;

public class LinkedStack<T> {
    // 靜態內部節點類，U 獨立於外部 T，體現泛型獨立性
    private static class Node<U> {
        U item;
        Node<U> next;

        // 哨兵節點構造子：item=null, next=null
        Node() { item = null; next = null; }

        // 正常節點構造子
        Node(U item, Node<U> next) {
            this.item = item;
            this.next = next;
        }

        // 判斷是否為哨兵（端點）
        boolean end() { return item == null && next == null; }
    }

    // 頂端指針，初始指向哨兵節點
    private Node<T> top = new Node<T>();

    // 壓入：新節點指向舊 top，top 前移
    public void push(T item) {
        top = new Node<T>(item, top);
    }

    // 彈出：取 top.item，top 後移；哨兵返回 null
    public T pop() {
        T result = top.item;
        if (!top.end())
            top = top.next;
        return result;
    }

    // 測試主程式
    public static void main(String[] args) {
        // String 測試
        LinkedStack<String> lss = new LinkedStack<String>();
        for (String s : "Phasers on stun!".split(" "))
            lss.push(s);
        String ss;
        while ((ss = lss.pop()) != null)
            System.out.println(ss); // 輸出：stun! on Phasers

        // Integer 測試（自動裝箱）
        LinkedStack<Integer> lii = new LinkedStack<Integer>();
        for (Integer i = 0; i < 10; i++)
            lii.push(i);
        Integer end;
        while ((end = lii.pop()) != null)
            System.out.println(end); // 輸出：9 8 ... 0
    }
}

核心設計精解

1. 哨兵節點模式

• top = new Node<T>() 建立空節點作為鏈表尾端標記
• end() 同時檢查 item==null && next==null，避免誤判資料節點
• 優點：pop() 無需額外 null 判斷，統一邏輯

2. 泛型參數 T vs U

• 外部類 LinkedStack<T> 定義資料型別
• 內部類 Node<U> 獨立宣告 U，編譯期各自擦除為 Object
• 實際執行時 Node 內部欄位仍保持 T 型別（靠橋接方法）

3. push / pop O(1) 操作

push: top = new Node(item, top);  // 單一指針更新
pop:  result = top.item; top = top.next; // 單一指針更新

無陣列擴容、無資料搬移，適合高頻堆疊操作。

4. 型別參數限制：不可為基本型別

LinkedStack<int> error;     // 編譯錯誤
LinkedStack<Integer> ok;   // 正確：使用包裝類

輸出結果驗證

stun!
on
Phasers
9
8
7
6
5
4
3
2
1
0

先進後出（LIFO）特性完美呈現。

擴展應用：加入 peek()、size()、Iterable

public T peek() { return top.end() ? null : top.item; }

public int size() {
    int count = 0;
    for (Node<T> n = top; !n.end(); n = n.next) count++;
    return count;
}

// 實作 Iterable 支援 for-each
public Iterator<T> iterator() {
    return new Iterator<T>() {
        Node<T> current = top;
        public boolean hasNext() { return !current.end(); }
        public T next() { T val = current.item; current = current.next; return val; }
    };
}

總結

• 哨兵節點簡化邊界條件處理
• 靜態內部類 + 獨立泛型參數體現封裝與型別安全
• 鏈表結構實現真正的動態容量、O(1) 核心操作
• 此模式廣泛應用於 java.util.LinkedList、ConcurrentLinkedQueue 等 JDK 原始碼