《Java 編程思想》裡的泛型章節有個相當經典的範例——用內部鏈式結構實作一個堆疊(LinkedStack)。作者寫得極好,值得反覆咀嚼與收藏。
在動手看程式碼前,先掌握幾個理解重點:
第一,類型參數不能是基本型別,因此像 T、U 這類泛型參數其實指向的是同一種「物件」概念;第二,每次放入新資料時,它就成為新的 top,並把原本的 top 往下壓一層,透過指標(next)串起整個鏈條;第三,那個「末端哨兵」正是預設構造函數所建立、能讓 end() 回傳 true 的節點,用來標示堆疊底部。
//: generics/LinkedStack.java
// A stack implemented with an internal linked structure.
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>(); // End sentinel
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) {
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);
//----- 放入整數測試
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);
//----- integer test end!
}
}
/* Output:
stun!
on
Phasers
*/
這個範例之所以精彩,在於它用一個泛型化的內部節點類別 Node,加上一個作為「底部哨兵」的初始節點,優雅地實作了後進先出(LIFO)的堆疊行為。push 時把新節點接在目前 top 之前,pop 時則回傳並下移 top,同時用 end() 判斷是否已觸及哨兵,避免空堆疊取值出錯。由於使用了泛型 <T>,同一份程式碼既能處理 String,也能處理 Integer,展現了泛型帶來的高度重用性。