Java 编程思想 泛型 末端哨兵例子解读

    java的泛型给编程带来了很大的灵活性，它非常重要的一点就是类型实现了参数化，下面就来解读书中一个例子，一个堆栈类，书中的第357页，java代码如下：

    

package com.cn.java;

/**
 * 
 * <p>
 * 堆栈
 * <p>
 * 
 * @author Lqy
 * 
 */
public class LinkedStack<T> {
        //堆栈中的节点
	class Node<U> {
		
		private U item;// 节点的值
		private Node<U> next;// 前一个节点

		Node() {
			item = null;
			next = null;
		}

		Node(U item, Node<U> next) {
			this.item = item;
			this.next = next;
		}

		/**
		 * 用于判断堆栈是否为空，也就是是否遇到了末端哨兵(end sentinel)
		 * 
		 * @return
		 */
		boolean end() {
			return item == null && next == null;
		}
	}

	/**
	 * 末端哨兵(end sentinel)
	 */
	private Node<T> top = new Node<T>();

	/**
	 * 入栈
	 * 
	 * @param t
	 */
	public void push(T item) {
                //当有新值插入的时候，改变top的指向，改变top指向之前先将top往下压。
		top = new Node<T>(item, top);
	}

	/**
	 * 出栈
	 * 
	 * @return
	 */
	public T pop() {
                //出栈的时候，每次都取栈顶的值
		T result = top.item;
                //判断是否遇到了末端哨兵
		if (!top.end()) {
			top = top.next;
		}
		return result;
	}

	public static void main(String[] args) {
		LinkedStack<String> stack = new LinkedStack<String>();
		stack.push("test1");
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
	}
}

 

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

    当堆栈为空的时候，这个末端哨兵就为空了，当往堆栈里面添加数据的时候，末端哨兵被压入底部。