Java利用泛型实现堆栈

       Java传统的下的堆栈是用LinkedList实现的,LinkedList本身已经具备了创建堆栈所必需的方法,而Stack可以通过两个泛型的类Stack<T>和LinkedList<T>的组合来创建。现在我不使用LinkedList,使用泛型来实现自己的内部链式存储机制。

public class LinkedStack<T>{

     private static class Node<U>{

         U item;

         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){

          LinkedStack<String> lss = new LinkedStack<String>();

          for(String s : "Phasers or stun!".split(" "))

             lss.push(s);

          String s;

          while((s = lss.pop() != null))

               System.out.println(s);

      }

}

/*Output

stun!

on

Phasers

*/

       内部类Node也是一个泛型,它拥有自己的类型参数。这里使用了一个末端哨兵来判断堆栈何时为空。这个末端哨兵是在构造LinkedList时创建的。然后,每调用一次push()方法,就会创建一个Node<T>对象,并将其链接到前一个Node<T>对象。当你调用pop()方法时,总是返回top.item,然后丢弃当前top所指的Node<T>,并将top转移到下一个Node<T>,除非已经碰到了末端哨兵,这时候就不再移动top了。如果已经到了末端,客户端程序还继续调用pop()方法,它只能得到null ,说明堆栈已经空了。

原文地址:https://www.cnblogs.com/wwhai/p/10241513.html