Java 泛型實戰：實現基於鏈表的棧結構 LinkedStack

設計思路

• 使用泛型類型參數 <T> 實現類型安全的棧。
• 內部私有靜態節點類 Node<U> 持有數據與下一節點引用。
• 引入 哨兵節點 作為棧底標記，end() 方法判斷是否為空（item==null && next==null）。
• push 創建新節點指向原頂點，pop 取值後移動頂點指針。

完整代碼

package generics;

public class LinkedStack<T> {
    private static class Node<U> {
        U item;
        Node<U> next;
        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>(); // 哨兵節點

    public void push(T item) {
        top = new Node<T>(item, top);
    }

    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<>();
        for (String s : "Phasers on stun!".split(" ")) lss.push(s);
        String ss;
        while ((ss = lss.pop()) != null) System.out.println(ss);

        // Integer 測試
        LinkedStack<Integer> lii = new LinkedStack<>();
        for (Integer i = 0; i < 10; i++) lii.push(i);
        Integer end;
        while ((end = lii.pop()) != null) System.out.println(end);
    }
}

運行輸出

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

關鍵點解析

1. 類型參數不能是基本類型：使用 Integer 而非 int。
2. 哨兵節點簡化邊界判斷：無需額外 size 字段，end() 統一處理空棧情況。
3. 泛型擦除下的類型安全：編譯期檢查，運行期通過轉型保證安全。
4. 內部類泛型參數 U 與外部 T 綁定：Node<T> 確保節點數據類型與棧一致。