用数组和链表实现队列

数组与链表

数组实现

数组实现的思路即通过新建一个长度+1的数组，将原数组的所有元素转移到新数组中，并对新数组的额最后一个单元进行添加，即可实现队列。

public class MQueue {
	private Student[] ms=new Student[0];//Student为新建立的类
	public void add(Student m){
		Student[] msd=new Student[ms.length+1];
		for(int i=0;i<ms.length;i++){
			msd[i]=ms[i];//原数组的所有元素转移到新数组
		}
		msd[ms.length]=m;//对新数组的额最后一个单元进行添加
		ms=msd;//这样实现了对数组长度的增加
	}

缺点在于，每一次添加都必须复制一遍之前所用到的数组，效率低下。

链表实现队列

首先，链表的实现思路并不复杂，即让所定义的类，用类似循环的方式不断指代。例如下面的例子

public class MyLinkNode {
	 Object data;
	public  MyLinkNode next;

	public MyLinkNode createLink(){
		String s1="数据";
		MyLinkNode r1=new MyLinkNode();
		r1.data=s1;
		String s2="数据2";
		MyLinkNode r2=new MyLinkNode();
		r2.data=s2;
		r1.next=r2;//r1.next指代了r2
		String s3="数据3";
		MyLinkNode r3=new MyLinkNode();
		r3.data=s3;
		r2.next=r3;//r2.next指代了r3
		return r1;
		
	}
}

这样就实现了链表的形式

那如何用链表实现队列呢？还要能够取到队列任意位置的值？
大家肯定能想到的是，按照上面的例子，只要使r1.next.next=r3，r1.next.next.next=r4。。。。等等，这样的结果实现就可以了。

当然这种写法是错误的，因此我们可以借助一个中间量。

public class LinkQueue {
		private MyLinkNode root;//第一个量
		private MyLinkNode last;//中间量
		private int count;
		public void add(Object o){
			if(root==null){
				root=new MyLinkNode();
				root.data=o;
				last=root;//中间量last
			}
			else{
				MyLinkNode next=new MyLinkNode();
				next.data=o;
				last.next=next;
				last=next;//中间量last
			}
		}
		public Object get(int index){
			int count=0;
			MyLinkNode tempNode=new MyLinkNode();
			tempNode=root;
			while(count!=index){
				tempNode=tempNode.next;
				count++;
				
			}
			return tempNode.data;
		}
}

很显然，我们就是用last表示了root.next.next,从而实现了root.next,next.next的效果
写完主函数运行的时候，
运行结果也表示上面的代码是可行的
显然链表实现队列没有了复制这一环节
因此
链表相比数组的优点在于，删除或插入一个节点时，不用复制，只修改指向