DIV CSS 佈局教程網

用 Java 泛型實現一個鏈式堆棧
編輯:關於JavaScript     

《Java 編程思想》中有一個用泛型實現鏈式堆棧的經典例子,寫得非常精妙,值得收藏借鑑。本文對它做個梳理。

理解要點

1、類型參數不能是基本類型,代碼中的 T 和 U 本質上是同一類型的參數。

2、每次壓入新數據,新節點都成為新的 top,原來的 top 被往下壓一級,通過指針(next)建立鏈接。

3、末端的哨兵節點,就是默認構造器創建出的、能讓 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);
  }
}
/* Output:
stun!
on
Phasers
*/

這個例子的巧妙之處在於:用一個靜態內部類 Node 表示節點,用一個哨兵節點作為棧底,push 時頭插、pop 時頭刪,全程沒有使用數組,靠指針即可完成後進先出。配合泛型,同一份代碼能服務於任意引用類型,是理解泛型與鏈式結構的絕佳範例。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved