队列的两种实现方式简要分析
package comZCB0409;import comZCB0408.Student;/** * 自定义队列接口的实现 * @author chubin */public interface NetJavaList {//向队列中加入一个学生对象public void add(Student st);//取得队列中指定位置上的学生对象public Student get(int index);//得到队列的长度public int size();}
? ? 2、定义接口后必须实现其所有的抽象方法，代码如下：
package comZCB0409;import comZCB0408.Student;/** * 实现的简单队列 * @author chubin */public class STList implements NetJavaList{@Override//向队列中加入一个学生对象public void add(Student st) {//1、新建一个数组。长度是原数组的长度+1Student[] destA=new Student[srcA.length+1];//2、将要加入的对象放入新数组的最后一个位置destA[srcA.length]=st;//3、将原数组中的元素复制到新数组中for(int t=0;t<srcA.length;t++){destA[t]=srcA[t];}//新数组重新复制给原数组srcA=destA;}@Override/** * 取得队列中指定位置的元素值 */public Student get(int index) {Student st=srcA[index];return st;}@Override/** * 得到队列的长度，即队列中元素的个数 */public int size() {return srcA.length;}//队列内部初始用来装学生对象的数组，长度为0 private Student[] srcA=new Student[0];}? ? 3、方法也定义好了，那么就让我们来测试一下下吧，代码如下：
package comZCB0409;import comZCB0408.Student;public class ManagerT {/** * @param args */public static void main(String[] args) {String s[] = {"张三","李四","王五","刘浏","蔡明"};//创建队列对象NetJavaList njl=new STList();java.util.Random ran=new java.util.Random();for(int i=0;i<5;i++){Student st=new Student(""+s[ran.nextInt(5)],ran.nextInt(5)+10);//加入队列njl.add(st);}//打印队列printStudent(njl);}/** * 打印队列中每个学生对象的信息 * @param njl */public static void printStudent(NetJavaList sl) {System.out.println(sl.size()+" 个学生信息如下：");System.out.println("队列的长度是："+sl.size());for(int t=0;t<sl.size();t++){System.out.println("t="+t);Student st=sl.get(t); st.ShowInfo();//调用Student类的showInfo方法，输出学生信息}}}?至此，队列的操作就实现了，当然还可以根据自己的需要，定义其他的方法。在这里只是说明队列最基本的实现过程。
? ? ? 好了，既然我们已经认识了数组和队列，那么就让我们在认识一下链表吧：
? ? ? 链表，是一组中的每一个数据有且只有一个直接前驱和直接后继的结构，简单的说，链表就是每个数据后面有一个箭头指向下一个元素，最后一个元素没有箭头的一组数据。链表的实现也分为三步：
? ? ?1、链表中的每一个数据都有数据域和指针域（其实不能称之为指针，因为在java中并没有指针这个概念，指针的概念是c语言的，但为了描述方便，这个概念暂且先用着）：
package comZCB0414;/** * 定义一个节点类 * @author chubin * */public class IntNode {public int data; //节点的数据域public IntNode next;//指向下一个节点的属性/* * 构造数据域为i，指针域为n的节点 */public IntNode(Object i,IntNode n){data = i;next = n;}/* * 构造一个next域为空的节点。用处是什么呢，答案在后面 */public IntNode(Object i){this(i,null);} //调用上面的构造方法，新建的指针域为空的节点数据域为i}? ? ?2、定义好结点类后，便需要定义相关方法，那么需要哪些相关方法呢？我们可以这样想，既然链表带有头指针和尾指针，想来肯定有他的用处，那么是什么用处呢？如果学过c语言就应该对指针有比较清晰的了解，其实，我们可以利用头指针和尾指针方便的进行插入的操作：代码如下：
package comZCB0414;/** * 定义一个链表类实现其主要操作 * @author chubin * */public class IntList {private IntNode head,tail;//定义头指针和尾指针/* * 定义一个空节点，为什么呢O(∩_∩)O哈！答案在后面 */public IntList(){head = tail = null;}/* * 判断节点是否为空，如果没有判断怎么办？ */public boolean isEmpty(){return head == null;}/* * 前插法 */public void addHeadNode(int e1){head = new IntNode(e1,head);//新建一个节点指向头结点System.out.println();if(head==tail){tail=head;} //空链表的时候}/* * 后插法 */public void addTailNode(Object e1){if(!isEmpty()){tail.next = new IntNode(e1);tail = tail.next;}else{head = tail = new IntNode(e1);}} /* *打印链表信息的方法 */public void printAll(){if(isEmpty()){System.out.println("该链表是空表");}IntNode temp;for(temp=head;temp!=null;temp=temp.next){System.out.println(temp.data+"");} System.out.println(); //不止一个节点的时候输出每个节点的信息}}? ? 3、在这里只实现了元素的前插和后插，其他的方法读者可以自己实现，方法实现后，便需要测试一下是否能实现，代码如下：
package comZCB0414;/** * 链表测试类 * @author chubin * */public class TestList {/** * @param args */public static void main(String[] args) {IntList test = new IntList();test.addTailNode(4);test.addTailNode(5);test.printAll();}}?
? ? ?以上我花了比较多篇幅说明三种数据结构的实现方式，主要就是为了用数组实现队列以及链表实现队列的比较。下面说明为什么要用数组实现队列呢，请看代码：
package comZCB0416;/** * 数组实现队列高级版 * @author chubin * 1、定义接口，以及队列操作的抽象方法 * 2、说明各个方法是什么实现操作的 * 3、检测方法的正确性，学会从问题发现问题的源头 */public interface Queue {public void clear(); //将队列置空public void enqueue(Object val); //在队尾插入一个新元素public Object dequeue(); //删除并返回队首元素public boolean isEmpty(); //检测是否为空队列public int size(); //返回队列中元素的个数public Object peek(); //Return the element at the front of this queue;void dequeue(int index); //删除指定位置上的元素}package comZCB0416;public class ArrayQueue implements Queue{private static final int DEFAULT_SIZE = 10;private Object[] array;private int front;public int rear;private int count;//构造器public ArrayQueue(){array = new Object[DEFAULT_SIZE];front = rear = count = 0;}@Override/* * 清空队列 */public void clear() {for(int i=0;i<array.length;i++){array[i] = null;front = rear = count = 0;}// TODO Auto-generated method stub}public void dequeue(int index) {if(count == 0){System.out.println("操作失败！");throw new java.lang.ArrayIndexOutOfBoundsException("");}array[index-1] = array[index];for(int k=count-1;k>index;k--){array[k-1] = array[k];}count--;rear--;System.out.println("执行啦");if(front == array.length)throw new java.lang.ArrayIndexOutOfBoundsException("操作失败！");}@Overridepublic void enqueue(Object val) {if(count == array.length) throw new java.lang.ArrayIndexOutOfBoundsException("不能再添加元素啦");array[rear++] = val;if(rear == array.length) throw new java.lang.ArrayIndexOutOfBoundsException("不能再添加元素啦");count++;}public void printAll(){if(count!=0){int k;for(k=0;k<count;k++){System.out.println(array[k]+"");}System.out.println("队列的长度是: "+count);}}@Overridepublic boolean isEmpty() {return count == 0;}@Overridepublic Object peek() {return null;}@Overridepublic int size() {return count;}@Overridepublic Object dequeue() {return null;}}package comZCB0416;public class TestArrayQueue extends ArrayQueue{public static int front;public static int rear;public static int count ;/** * @param args */public static void main(String[] args) {TestArrayQueue aq = new TestArrayQueue();aq.enqueue(1);aq.enqueue(2);aq.enqueue(3);aq.enqueue(4);aq.enqueue(5);aq.dequeue(3);aq.printAll();}}?在这里实现了往队列插入元素，以及删除任意位置的元素，并用数组打印出来。因为数组是顺序结构，所以在插入或删除元素时往往需要比较多时间，所以代码的效率很高。所以在需要经常更新数据的时候，我们一般需用链表队列，因为链表是非顺序存储结构，每个元素带有一个指针，所以在插入或者删除元素时能够更快的实现。链表实现队列代码如下：
package comZCB0415;/** * 使用链表实现队列 * @author chubin * */class QueueNode { Object data; // 节点存储的数据 QueueNode next; // 指向下个节点的指针 public QueueNode() { this(null, null); } public QueueNode(Object data) { this(data, null); } public QueueNode(Object data, QueueNode next) { this.data = data; this.next = next; } } public class QueueLinked { QueueNode front; // 队首指针 QueueNode rear; // 队尾指针 public QueueLinked() { this.rear = null; this.front = null; } //将一个对象追加到队列的尾部 public void enqueue(Object obj) { //如果队列是空的 if (rear == null && front == null) { rear = new QueueNode(obj); front = rear; } else { QueueNode node = new QueueNode(obj); rear.next = node; rear = rear.next; } } //队首对象出队 //return 出队的对象，队列空时返回null public Object dequeue() { //如果队列空 if (front == null) { return null; } //如果队列中只剩下一个对象 if (front == rear && rear != null) { QueueNode node = front; rear = null; front = null; return node.data; } Object obj = front.data; front = front.next; return obj; } public static void main(String[] args) { QueueLinked q = new QueueLinked(); q.enqueue("张三"); q.enqueue("李斯"); q.enqueue("赵五"); q.enqueue("王一"); for (int i = 0; i < 4; i++) { System.out.println(q.dequeue()); } } }? ? ? 本来队列是可以以任意形式进出的，但为了说明问题，这里的的队列是一般书上的即只能先进先出的形式，从队尾加入元素，从队首删除元素。是为了便于比较。通过以上代码，我们发现数组实现队列删除队列的时候需要从最后一个元素开始查找，试想一下如果数组比较长，则这种查找是显而易见的。现在，我们看链表实现队列，当删除元素的时候front = front.next;使用这么一条语句就搞定了，所以省去了许多时间，提高了代码的效率。但数组实现的队列的好处在于可以通过数组下标快捷的找到某个元素，而要通过链表访问某个数据就得遍历整个链表，比较麻烦。链表在于能够动态的分配空间，自由度大。?
? ?最后，在总结一下队列的实现方式：
? ?1、要有数组或者链表
? ?2、队列的定义
? ?3、用数组或者链表实现队列的插入以及删除方法（这部分最重要）。数组表现在数组下标的移动，链表表现在指针的移动。
? ?4、要有实现类