堆栈小程序

//import java.util.Stack;

class testStack{

public static void main(String args[]){
  Stack stack=new Stack();  
  //注意：如果引用util包中的Stack,使用下面的格式
  //jdk1.5, 1.6中改变的形式。
  //Stack<Node> stack=new Stack<Node>();
  System.out.println(stack.empty());

  IntList list=new IntList();
  list.addFirst(3);
  list.addFirst(2);
  list.addFirst(1);
  //list.printList(); 
  //我认为这是这是一种破坏性输出;
  //它破坏了链表的结构。
  //经过这个输出,链表变为(3,null);
  System.out.print("链表长度为：");
  list.printLength();

  //stack.push(list.head);
  for(Node node=list.head;node!=null;node=node.next){
    stack.push(node);
	//System.out.println(stack.empty());
  }  

  while(!stack.empty()){ //stack不为空的话
    //堆栈倒序输出一个链表
    Node nd=(Node)stack.pop();
	System.out.print(nd+" ");
  }  
}
}


class IntList{
  int length;
  Node head;

  public IntList(){
    length=0;
    head=null;
  }

  public void addFirst(int i){
    Node newNode=new Node(i,head);
	head=newNode;
	length++;
  }

  public void printLength(){
    System.out.println(length);
  }

  public void printList(){
	  System.out.print("(");
	  while(head!=null){
		//注意null的概念,看head对象的时空为空
		//而不是看它的next
		System.out.print(head);
	    if(head.next==null){
		  break;
		}else{
		  System.out.print(",");
		  head=head.next;
		}
	  }
	  System.out.println(")");
  }
}


class Node{
  int cargo;
  Node next;

  public Node(){
    cargo=0;
    next=null;
  }

  public Node(int cargo,Node next){
    this.cargo=cargo;
    this.next=next;
  }

  public String toString(){
    return cargo+"";
  }
}

/*
必须是对象类型才可以添加到堆栈中(String,Node等);
向堆栈压入一个对象，自动转为Object类型

Java有两种类 一基础类：int,double等  二对象类 ：Sring等
基础类对应了相应的内置对象类型  如
Interger(int)    Double(double)    Character(char)

方法(实例变量)前有private表示仅仅在此类中可调用
在任何外部类中都无法使用
*/

//用数组实现Stack的push,pop 《探秘java》中的
class Stack
{
	Object[] array;
	int index;

	public Stack(){
	  this.array=new Object[128];
	  this.index=0;
	}

	public boolean empty(){
	  return index==0;
	}

	public Object pop(){
	  index--;
	  return array[index];
	}

	public void push(Object item){
	  if(full())  resize();
      //at this point we can prove that index<array.length
	  array[index]=item;
	  index++;
	}

	private boolean full(){
	  return index==array.length;
	}

	private void resize(){
	  Object[] newArray=new Object[array.length*2];
	  //we assume that the old array if full
	  for(int i=0;i<array.length;i++){
	    newArray[i]=array[i];
	  }
	  array=newArray;
	}
}