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
}
}
top 永遠指向一個節點(初始為哨兵),pop() 無需檢查 top == null,只需檢查 top.end()。簡化邏輯、避免 NPE。Node<U>: 內部類別另行宣告型別參數 U,雖然實際上 U 總是等於外部 T,但展示了「嵌套泛型類別」的寫法。push 建立新節點而非修改舊節點,天然支援持久化資料結構(如函數式堆疊)。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>(); }
| 特性 | 陣列堆疊 | 鏈結堆疊 |
|---|---|---|
| 記憶體分配 | 連續,需擴容複製 | 分散,按需分配 |
| Push/Pop 時間 | O(1) 攤銷 | O(1) 固定 |
| 最大容量 | 受陣列長度限制 | 僅受堆記憶體限制 |
| 快取局部性 | 優秀 | 較差 |
| 持久化/共享 | 困難 | 天然支援 (函數式) |
// 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 中的優雅結合,是理解資料結構與泛型交互的最佳教材之一。