数据结构--栈的java实现

    栈是只在线性表的一端进行添加和删除动作的特殊线性表。它的主要特点是“先进后出”，主要操作是出栈，入栈，清空，判断是否为空。
    栈的实现方式分为顺序栈和链栈。顺序表用固定长度的数组来实现。链表用变长的单链表实现。栈的一个属性是顶点。入栈时，将入栈数据赋值给顶点，顶点上移。出栈时，顶点下移，将顶点的数值输出。下面分别实现顺序栈和链栈。
    首先定义接口：

 public interface Stack{
    public void clear();
    public boolean isEmpty();
    public int getLength();
    public void pull(Object temp);
    public Object poll();
    public void print();
}

    顺序栈的实现：
    顺序栈的长度为N。

 public class StackDemo1 implements Stack{
    private int top;
    private Object[] arr;
   
    public StackDemo1(){
            top=0;
            arr= new Object[N]; 
    }
    public  void clear(){
            top =0;
    }
    public boolean isEmpty(){
            return top==0;
    }
    public int getLength(){
            int length =0;
            if(!isEmpty()){
                  length = top-1;
            }
            return length;
    }
    public void pull(Object temp){
           if(top!=arr.length){
                   arr[top]= temp;
                   top++;
           }
          else{
                  throw new Exceotion("栈已满");
           }
   }
   public Object poll(){
           Object p=null;
           if(!isEmpty()){
                    top--;
                    p=arr[top];
           }
           else{
                    throw new Exception("栈已空")}
           }
           return p;
  }

    链栈实现：

public class Vertex{
    private int number;
    private Vertex next;

    public Vertex(){
    }
    public Vertex(int num){
             this.number=num;
    }
    public Vertex(Vertex next){
             this.next=next;
    }
    public Vertex(int num,Vertex next){
             this.next=next;
             this.number=num;
    }
    
    public int getNum(){
             return number;
    }
    public void setNext(Vertex p){
             this.next=p;
    }
    public Vertex getNext(){
             return this.next;
    }
    }
  

   public class StackDemo2 {
   private Vertex top;

   public StackDemo2(){
             top = null;
   }
   public void clear(){
             top = null;
   }
   public boolean isEmpty(){
             return  top==null;
   }
   public int getLength(){
             int length=0;
             if(top!=null){
                     Vertex p=top;
                     while(p!=null){
                      p=p.getNext();
                      length++;
              }
             return length;
  }
   public void pull(Vertex p){
              if(isEmpty()){
                       top = p;
              }
              else{
                       p.setNxt(top);
                       top=p;
              }
  }
  public Vertex poll(){
             Vertex p=null;
             if(!isEmpty(){
                       p=top;
                       top=top.getNext();

 }
}
  

    栈的应用非常广泛，操作系统中的堆栈，系统中断时就需要将正在处理的程序相关信息入栈，中断程序处理完时，需要将中断前的程序信息出栈。

评论

1 楼 飘零羽 2012-06-15  

语言叙述还是太简单了，缺少过渡性的描述，描述太简单