当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

队列实现

发表于: 2013-04-20   作者:csb   来源:转载   浏览:
摘要: 1.概念的小小理解       参考解释:队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。        我们当然不能照搬概念,这只会混淆我们的
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;
	}

队列实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号