优先队列

                            优先队列

前言：java中有很多的队列类，其中有一些叫做优先队列，优先队列的优点之一就是能够实现自动排序，排序的方式是可以指定的。PriorityQueue是一个最常用的优先队列类，如果你想按照某种特定的方法进行排序，可以在创建对象的时候，转入一个比较器对象（comparator）。

关于优先队列，因为平时用的比较少，所以还不是很清楚，看了一下源代码，发现自己似乎懂，但又不是很懂。懂了是因为它不就是多了排序的功能而已，不懂是因为它是怎么具体实现的。在这种情况下，我跟倾向于不懂，因为它不就是多了排序功能的队列吗！我自己也能写一个，于是乎我自己也开始写了一个优先队列类，环顾身边和我一起些优先队列的童鞋，他们都喜欢用数组来实现，但我偏不用数组，我选择了用链表来实现。

示例代码如下：

/**
 * 这是一个节点连类
 *  它既可以指向上一个节点，也可以指向下一个节点
 */
public class LinkNode{
   private int obj;//节点里保存的元素
   private LinkNode next;//这是指向链表的下一个节点
   private LinkNode back;//指向链表的上一个节点
   public LinkNode(int obj)
   {
	   this.obj=obj;
   }
   //设置指向下一个节点的方法
   public void setNext(LinkNode next){
	   this.next=next;
   }
   //设置指向上一个节点的方法
   public void setBack(LinkNode back)
   {
	   this.back=back;
   }
   //修改节点内容的方法
   public void setObj(int obj)
   {
	   this.obj=obj;
   }
   //获得下一个节点的方法
   public LinkNode getNext()
   {
	   return next;
   }
   //获得上一个节点的方法
   public LinkNode getBack(){
	   return back;
   }
   //获得节点内容的方法
   public int getObj()
   {
	   return obj;
   }
   
}

  节点类的代码很简单，下面是优先队列的代码，下面的代码中为什么要创建头结点和尾节点，能不能省略，具体说来我也不知道，我只知道用它们才能实现我想要的功能，当然这个队列还可以优化。

/**
 * 这是一个自定义的优先队列类 
 * 没往里面加一个数据，就可以自动排序
 *该优先队列的排序方式是按从大到小的顺序进行排列
 */
public class YouxianQueue {
	private LinkNode root;//头结点 
	private LinkNode back;//尾节点
	private int size=0;//一个保存队列元素个数的属性
	public YouxianQueue(){
		root=new LinkNode(0);//初始化头结点
		back=new LinkNode(0);//初始化尾节点
		root.setNext(back);//让头结点和尾节点相互指向
		back.setBack(root);//
	}
	//王队列里面添加元素的方法
	public void add(int i){
		LinkNode link=root;//一个中间变量
		for(int k=0;k<size+1;k++){
			link=link.getNext();//获得下一个节点
			if(i>link.getObj()||link.getNext()==null){//如果要插入的元素大于这个节点里的元素，就插入
				LinkNode temp=new LinkNode(i);//创建一个新节点
				LinkNode back=link.getBack();//获得上一个节点
				back.setNext(temp);//上一个节点指向新节点
				temp.setBack(back);//新节点指向上一个节点
				temp.setNext(link);//新节点指向下一个节点
				link.setBack(temp);//上一个节点指向新节点
				break;//跳出循环
			}
		  }
		
		size++;
	}
	/**
	 * 类似于根据指定的下标获取对应的元素
	 * @param w 指定的节点位置
	 * @return 节点里面的元素
	 */
	public int get(int w){
	    if(w<0||w>size){//如果查找的下标不合法
	    	throw new NullPointerException();
	    }else{
	    	LinkNode link=root.getNext();//获得头节点下一个节点
	    	for(int k=0;k<w;k++){
	    		link=link.getNext();//指向对应位置的节点
	    	}
	       return link.getObj(); //返回节点的内容
	    }
	}
	/**
	 * 类似于根据下标移除指定的元素
	 * @param w 节点的位置
	 * @return  返回被移除的元素
	 */
	public int remove(int w){
		 if(w<0||w>size){//如果查找的下标不合法
		    	throw new NullPointerException();
		    }else{
		    	LinkNode link=root.getNext();//获得头节点下一个节点
		    	for(int k=0;k<w;k++){
		    		link=link.getNext();//指向对应位置的节点
		    	}
		    	LinkNode next=link.getNext();//获得当前节点的上一个节点和下一个节点
		    	LinkNode back=link.getBack();
		    	next.setBack(back);//让这两个节点相互指向
		    	back.setNext(next);
		       return link.getObj(); //返回节点的内容
		    }
	}
	/**
	 * 按从小到大的顺序获得对应位置节点的元素
	 * @param w 节点的位置
	 * return 节点里面的元素
	 */
	public int get_Min(int w){
		  if(w<0||w>size){//如果查找的下标不合法
		    	throw new NullPointerException();
		    }else{
		    	LinkNode link=back.getBack();//获得尾节点的上一个节点
		    	for(int k=0;k<w;k++){
		    		link=link.getBack();//指向对应位置的节点
		    	}
		       return link.getObj(); //返回节点的内容
		    }
	}
	//获得队列的长度，即元素的个数
	public int size(){
		return size;
	}
}

 测试类

public class Test {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Test test=new Test();//创建一个对象
		test.testQueue();

	}
	//测试自定义优先队列的方法
	public void testQueue(){
		java.util.Random ran =new java.util.Random();
		YouxianQueue queue=new YouxianQueue();
		//给队列随机赋100个值
		for(int i=0;i<10;i++){
			int temp=ran.nextInt(2000);//获得一个随机数
			queue.add(temp);//把它加到队列里面
		}
		//按从大到小输出队列里面的元素
		for(int j=0;j<queue.size();j++){
			int temp=queue.get(j);
			System.out.println(temp);
		}
		//按从小到大输出队列里面的元素
		for(int j=0;j<queue.size();j++){
			int temp=queue.get_Min(j);
			System.out.println(temp);
		}
	}
}

 

这个队列很大的缺陷就是不支持泛型，当然把它改成支持泛型也比较简单，经过进一步的思考之后，我发现用数组来实现的队列和用链表实现的队列相比。用数组来实现的链表比较适合存储大量的数据的情况，而是用链表实现的队列跟有利实现频繁修改数据的情况。像上面使用链表来实现的时候，查找和比较里面元素的时候特别麻烦，都得从头到尾的去遍历链表，不想用数组，可以用二分法来进行查找，但是他插入数据就会变得很简单，链表需要像数组那样要开辟连续的空间，这样很灵活。