用数组和链表实现队列

*什么是队列？

????? 队列的实质就是以数组和链表为基础，实现对数据的添加，删除，查找，插入等动作

举个例子，一根按动笔，笔芯就代表数组或链表，而整支笔就可以代表一个队列，这支笔可以通过一些方法来控制笔芯的弹出、收回以及写字，这就和队列存在一些方法可以向链表和数组加入、删除、获取数据是一个道理。

下面是我分别用数组和链表实现的简单队列

?

（一）用数组试下的队列

?

1、首先建立数组和链表中存放的对象类

public class student {    //定义学生类private String name;  //定义姓名属性private int number;   //定义学号属性public student(String name,int number){   //带有参数的构造器，参数为name和numberthis.name=name;this.number=number;}}

?

2、创建队列类

import xxy0417.student;/** * 用数组实现队列 * @author 徐馨宇2013.04.19 * */public class list {      //定义队列类private int change;  //定义一个变动值private int count; //定义一个计数数，该数与数组下标值相同private int root;  //定义数组的初始长度student[]st=new student[root]; //创建一个长度为root的数组public list(int root,int change){  //创建带有两个参数的构造器用来实例化数组}public void add(student s){    //定义在队列中加入对象的方法，参数为student类的一个对象if(count+1>=st.length){    //判断如果新加入一个对象，是否使数组越界student[]b=new student[st.length+change]; //如果越界,则新建一个长度增加change个单位的数组来存储数据for(int i=0;i<st.length;i++){ //将原数组中的数据传到新建数组中b[i]=st[i];}b[st.length]=s;   //把新加入的对象放入新建数组中下标为【原数组长度】的位置st=b;           //将新数组中的所有数据赋给原数组}else{                  //如果数组未越界，则把新加入的对象存储在数组中st[count+1]=s;  }count++;                    //新加入一个对象，则计数数增加一}public student get(int index){  //定义获取数组中某个指定元素的值得方法，参数为一个整形的索引数student s=st[index];        //得到数组中下标为index的单元所存的对象return s;                   //返回这个对象}public void delete(int index){   //定义删除数组中某指定元素的方法student[]n=new student[st.length-1];   //创建一个新数组for(int i=0;i<index;i++){     //把原数组中所要删除元素之前的元素赋给新建数组n[i]=st[i];}for(int i=index+1;i<st.length;i++){  //把原数组中所要删除元素之后的元素赋给新建的数组，下标减一n[i-1]=st[i];}st=n;   //把新建数组赋给原数组}public int getSize(){   //定义得到队列中元素个数的方法return st.length;   //返回数组的长度}}

（二）用链表实现的队列

?

1、创建节点类

//定义节点类public class linknode {//定义数据属性   private Object obj;     private linknode child;    //定义指针指向的子节点   private linknode parent;   //定义指针指向的父节点         public linknode(Object obj){ //有参构造器   this.obj=obj;   }      public void setobj(Object obj){     this.obj=obj;   }      public Object getobj(){   return obj;   }      public void setchild(linknode child){   this.child=child;   }      public linknode getchild(){   return child;   }   public void setparent(linknode parent){   this.parent=parent;   }      public linknode getparent(){   return parent;   }}

?2、创建用链表实现的队列类

//创建链表类public class linklist {public static linknode front=null;//第一个节点赋值public  linknode last=null;//最后一个节点赋值/** *  * 函数入口 */public void main(String args[]){    linklist list=new linklist();//创建链表对象    list.add("aa");    list.add("bb");    list.add("cc");    //加入节点    }//定义接入节点的方法public void add(Object obj){linknode node=new linknode(obj);//如果链表为nullif(front==null){front=node;last=front;}else{last.setchild(node);node.setparent(last);last=node;}}//定义插入节点的方法public void insert(Object obj,int index){if(this.getlength()<index||index<0){throw new java.lang.RuntimeException("下标越界："+index+"size:"+this.getlength());}else{linknode newnode=new linknode(obj);//创建一个新节点 linknode node=this.getnode(index);if(index==0){ front=node; }else{linknode fnode=node.getparent();fnode.setchild(newnode);newnode.setparent(fnode);//设置新的用关系newnode.setchild(node);node.setparent(newnode); }}}//定义删除节点的方法public void delete(Object obj,int index){linknode node=this.getnode(index);if(index>this.getlength()){throw new java.lang.RuntimeException("下标越界："+index+"size："+this.getlength());}else{linknode nodef=node.getparent();linknode nodez=node.getchild();if(nodef==null){     front=nodez;}else if(nodez==null){nodef.setchild(null);}else{nodez.setparent(nodef);nodef.setchild(nodez);}}}//定义取出节点的方法public linknode getnode(int index){linknode d=front.getchild();for(int i=0;i<index;i++){d=d.getchild();}return d;}public int getlength(){int count=0;if(front==null){return count;}linknode node=front.getchild();while(node!=null){count++;node=node.getchild();}return count+1; }} 

?时间不够链表的注解没怎么写，明天补上