栈的链表实现

Introduction

java中链表的实现，除了不需要释放没用的结点之外，与C的实现相同。

Detail

用嵌套类来声明结点。

• 需要表明next（下一结点）和item（该节点的值）。在需要使用该类的时候，标记为private

private class Node{
	Item item;
	Node next;
}

构造链表

• 根据递归的定义，只要一个Node类型就能表示整条链表因为节点就是一个对象，我们就用new来创建它，Node first = new Node();。 然后，再定义Node里面的值，first.item = "to" first.next = second

• 而Stack类的实例变量就是创建Node的引用，然后再从实例中创建它

public class Stack<Item>{
	private Node first; //实例变量创建引用，没有用new新建对象
	private int N;

增加删除表头结点

• 因我们是用链表实现栈，栈是除了最上面的元素first，其它都不要动。所以我们不需要遍历链表就能实现push()和pop()的方法
  

表尾删除节点

• 如果要遍历链表那么效率太低了， 所以采用一种方法：再创建个已知节点Node last = new Node();
  

增加删除指定节点

• 唯一方法就是遍历链表，如果要减少时间的复杂度，即采用双向链表。

Test

public class Stack<Item>{
	private Node first; //实例变量创建引用，没有用new新建对象
	private int N;

	private class Node{
		Item item;
		Node next;
	}
	
	public boolean isEmpty() {
		return first == null;
	}
	
	public int size() {
		return this.N;
	}
	
	public void push(Item item)
	{
		Node oldfirst = first;
		first = new Node();
		first.next = oldfirst;
		first.item = item;
		N++;
	}
	
	public Item pop() {
		Item item = first.item;
		first = first.next;
		N--;
		return item;
	}
}

test

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Stack<String> s = new Stack<String>();
		while(!StdIn.isEmpty())
		{
			String item = StdIn.readString();
			if(!item.equals("-"))
				s.push(item);
			else if(!s.isEmpty())
				StdOut.print(s.pop() + " ");
		}
		StdOut.println("(" + s.size() + " left on stack)");
	}

}