队列实现

1.概念的小小理解
      参考解释：队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
       我们当然不能照搬概念，这只会混淆我们的视听。我的理解队列就是一个简单的拥有一个长串（这就是所谓的一种数据结构）的事物，长串里面可是各种各样的对象（数据类型），好像我们排队打水的时候那一长串的人一样，这一长串就是队列，队列的实体就是我们人（就是队列中存放的对象）。再举一个例子，小时候顽皮在地上玩泥巴经常看见的小蚂蚁搬食物，那长长的蚂蚁队伍也是一个队列，蚂蚁就是队列的实体对象。我既然聊到的队列的概念，那就肯定就会思考说明概念有什么作用，没有实际操作的东西永远的都没有价值，所以，我不会花这么大的气力说一些没有作用的东西。首先我们引进队列是因为它有一个可爱的优点，那就是队列没有长度的限制，不想数组那样机械，在使用之前就必须申请空间大小。所以我们用的时候考虑到应该能够给队列添加元素，那就有add()方法，同时要能够知道队列的大小，那就是size()方法，同时我们如果要取到队列中的某一元素的话那就应该有get()方法，以及要插入某一位置，删除某一位置的元素，就必须要有各种方法，自己视需要而写。综述一下，队列是一个不限定长度的数据结构，中间可以是任意类型的元素，引进的作用是方便操作


2.数组的队列实现
以学生数组为代表
     

 public class STList {
	//实例化一个学生对象数组
	private Student[] scrA=new Student[0];
	
	public void add(Student st) {
		Student[] destA=new Student[scrA.length+1];
		destA[scrA.length]=st;
		for(int t=0;t<scrA.length;t++){
			destA[t]=scrA[t];
		}
		scrA=destA;
	}

	public Student get(int index) {
		Student st=scrA[index];
		return st;
	}

	public int size() {
		return scrA.length;
	}
      //.....更多的方法
}

3.链表的队列实现

public class MyNode {
	public Object obj;
	public MyNode next;
	
	public MyNode(Object obj){
		this.obj=obj;
	}
	
	public void setObject(Object obj){
		this.obj=obj;
	}
	
	public Object getObject(){
		return obj;
	}
	
	public void setNext(MyNode next){
		this.next=next;
	}
	
	public MyNode getNext(){
		return next;
	}
}

public class TestMyQueue {

	/**队列的测试类
	 * @param args
	 */
	public MyNode root=null;
	public static void main(String[] args) {
		TestMyQueue tm=new TestMyQueue();
		tm.add("aa");
		tm.add("bb");
		tm.add("cc");
		for(int i=0;i<tm.length();i++){
			System.out.println(tm.getIndexobj(i));
		}
		tm.insertIndexobj(1,"dd");
		for(int i=0;i<tm.length();i++){
			
			System.out.println(tm.getIndexobj(i));
		}
		Object obj=tm.removeIndexobj(3);
		System.out.println(obj);
		for(int i=0;i<tm.length();i++){
			
			System.out.println(tm.getIndexobj(i));
		}
	}
	
	public void add(Object obj){
		MyNode node=new MyNode(obj);
		if(root==null){
			root=node;
		}else{
			MyNode tem=root;
			
			while(tem!=null && tem.next !=null){
				tem=tem.next;
			}
			tem.next=node;
		}
	}
	
	public int length(){
		int i=0;
		MyNode tem=root;
		while(tem!=null){
			tem=tem.next;
			i++;
		}
		return i;
	}
	
	public void insertIndexobj(int index,Object obj){
		MyNode node=new MyNode(obj);
		MyNode tem=root;
		MyNode node1=root;
		int j=this.length();
		if(index>j){
			System.out.println("请输入长度小于队列长度的数");
		}else{
			int k=0;
			while(k!=index){
				node1=tem;
				tem=tem.next;
				k++;
			}
			node1.next=node;
			node.next=tem;
		}
	}
	
	public Object getIndexobj(int index){
		int i=0;
		int len=this.length();
		MyNode tem=root;
		if(index>len){
			System.out.println("越界！！");
		}else {
		while(i!=index){
			tem=tem.next;
			i++;
		}
		}
		Object obj=tem.getObject();
		return obj;
	}
	
	public Object removeIndexobj(int index){
		int i=0;
		int len=this.length();
		MyNode tem=root;
		MyNode tem1=root;
		
		if(index>len){
			System.out.println("越界！！");
		}else {
		while(i!=index){
			tem1=tem;
			tem=tem.next;
			i++;
		}
		tem1.next=tem.next;
		}
		Object obj=tem.getObject();
		return obj;
	}
}

4.通用队列实现以及队列的优化
<1>通用队列的实现

public class MyList<E> {
	//实例化一个String数组
	private Object[] sa=new Object[0];
	
	//add方法
	public void add(E node){
		Object[] ms=new  Object[sa.length+1];
		for(int i=0;i<sa.length;i++){
			ms[i]=sa[i];
		}
		ms[sa.length]=node;
		sa=ms;
	} 
	
	//get方法
	public  E get(int index){
		E node=<E>sa[index];
		return node;
	}
	
	//返回长度
	public int size(){
		return sa.length;
	}
//......其他的方法
}

<2>队列的优化
在加入元素时，每加一个就会把原来的数组重新复制到新的数组，时间效率很低

public void add(E node){
		Object[] ms=new  Object[sa.length+1];
		for(int i=0;i<sa.length;i++){
			ms[i]=sa[i];
		}
		ms[sa.length]=node;
		sa=ms;
	} 

//改进

Object[] ms=new  Object[sa.length+1000];//增加更长的长度，效率明显提高

打一个比方：我每天都有一个习惯就是早晨会喝一杯牛奶，但是我的做法是每天早晨都要跑一趟超市去买，花的时间太多，如果我一次买一箱的话，花的时间就会少太多



      5.队列实现重绘
   

 public void paint(Graphics g){
		super.paint(g);
		int count=50;
		//画棋盘
		for(int j=0;j<11;j++){
			g.drawLine(200,200+j*50,700,200+j*50);
		}
		for(int k=0;k<11;k++){
			g.drawLine(200+k*50,200,200+k*50,700);
		}
		int size=pointlist.size();
		for(int i=0;i<size;i++){
			Point po=pointlist.get(i);
			g.fillOval(po.x,po.y,30,30);
		}
	}

在鼠标监听器里面要有返回的队列

public PointList getPointList(){
		return pointlist;
	}