萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

Java 泛型實作鏈結堆疊:深度解析《Java 編程思想》經典範例

原始碼重構與註解

package generics;

/** 泛型鏈結堆疊 — 內部節點類別亦為泛型 */
public class LinkedStack<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>();

    /** 壓入:新節點指向舊頂端,頂端指標前移 */
    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; // 空堆疊回傳 null
    }

    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);
        // 輸出: stun! / on / Phasers (LIFO)

        // 測試 Integer (自動裝箱)
        LinkedStack<Integer> lii = new LinkedStack<>();
        for (int i = 0; i < 10; i++) lii.push(i);
        Integer ii;
        while ((ii = lii.pop()) != null) System.out.println(ii);
        // 輸出: 9 8 7 6 5 4 3 2 1 0
    }
}

設計精華解析

  1. 哨兵節點消除空指針判斷: top 永遠指向一個節點(初始為哨兵),pop() 無需檢查 top == null,只需檢查 top.end()。簡化邏輯、避免 NPE。
  2. 泛型節點 Node<U>: 內部類別另行宣告型別參數 U,雖然實際上 U 總是等於外部 T,但展示了「嵌套泛型類別」的寫法。
  3. 不可變節點結構: push 建立新節點而非修改舊節點,天然支援持久化資料結構(如函數式堆疊)。
  4. 型別擦除下的安全: 編譯期保證 push 只接受 T,pop 回傳 T,執行期無需轉型。

記憶體模型圖解

初始: top → [Sentinel: item=null, next=null]

push("A"): top → [Node: item="A", next] → [Sentinel]
push("B"): top → [Node: item="B", next] → [Node: item="A", next] → [Sentinel]

pop(): 取 "B", top 後移 → [Node: item="A", next] → [Sentinel]
pop(): 取 "A", top 後移 → [Sentinel]
pop(): 取 null (end()==true), top 保持哨兵

擴充功能建議

public boolean isEmpty() { return top.end(); }
public int size() { int c=0; for(Node<T> n=top; !n.end(); n=n.next) c++; return c; }
public T peek() { return top.end() ? null : top.item; }
public void clear() { top = new Node<T>(); }

對比:陣列實作 vs 鏈結實作

特性陣列堆疊鏈結堆疊
記憶體分配連續,需擴容複製分散,按需分配
Push/Pop 時間O(1) 攤銷O(1) 固定
最大容量受陣列長度限制僅受堆記憶體限制
快取局部性優秀較差
持久化/共享困難天然支援 (函數式)

現代 Java 改寫 (Java 16+ Record + Sealed)

// Node 為 sealed 介面,僅允許兩種實現
sealed interface Node<T> permits Node.Data, Node.Sentinel {
    boolean isEmpty();
}

final class Data<T> implements Node<T> {
    final T item; final Node<T> next;
    Data(T item, Node<T> next) { this.item = item; this.next = next; }
    public boolean isEmpty() { return false; }
}

final class Sentinel<T> implements Node<T> {
    public boolean isEmpty() { return true; }
}

public class LinkedStack<T> {
    private Node<T> top = new Sentinel<>();
    public void push(T item) { top = new Data<>(item, top); }
    public T pop() { if (top.isEmpty()) return null; T r = ((Data<T>)top).item; top = ((Data<T>)top).next; return r; }
}

這個經典範例展示了泛型、內部類別、哨兵模式、鏈結結構在 Java 中的優雅結合,是理解資料結構與泛型交互的最佳教材之一。

copyright © 萬盛學電腦網 all rights reserved