海阔天空

I'm on my way!
随笔 - 17, 文章 - 69, 评论 - 21, 引用 - 0
数据加载中……

java中关于优先级队列的实现

        这几天一直在搞关于优先级队列的实现,因为要考虑到线程的安全,所以PriorityQueue就不适用了。一个非常简单的实现方 法，那就是把优先级比较好的插入一个队列，优先级低的插入另一个队列，取数的时候先在优先级高的队列上取数。这有个缺点就是如果优先级别越多的话，队列就 越多。
        因为要线程安全，队列采用ConcurrentLinkedQueue这个线程安全的，而api文档上说ConcurrentLinkedQueue采用了有效的“无等待 (wait-free)”算法，所以它的吞吐量是很不错的！
    简单代码如下：
  1. package test;

  3. import java.util.concurrent.ConcurrentLinkedQueue;

  5. public class PriorityQueueTest {

  7.     public static void main(String[] args) {
  8.         ConcurrentLinkedQueue<String> highPriority = new ConcurrentLinkedQueue<String>(); //高优先级
  9.         ConcurrentLinkedQueue<String> lowPriority = new ConcurrentLinkedQueue<String>();  //低优先级
  10.         
  11.         highPriority.add("aaa");
  12.         highPriority.add("bbb");
  13.         highPriority.add("111");
  14.         
  15.         lowPriority.add("ccc");
  16.         lowPriority.add("ddd");
  17.         lowPriority.add("222");
  18.         
  19.         int i = 0 ,j = 0, k=0;
  20.         while(true){
  21.             while(true){
  22.                 if(!highPriority.isEmpty()){
  23.                     System.out.print(highPriority.remove());
  24.                     i++;
  25.                     k++;
  26.                     System.out.println(", i = "+i+", k="+k);
  27.                     break;
  28.                 }
  29.                 if(!lowPriority.isEmpty()){
  30.                     System.out.print(lowPriority.remove());
  31.                     j++;
  32.                     k++;
  33.                     System.out.println(", j = "+j+", k="+k);
  34.                     break;
  35.                 }
  36.                 break;
  37.             }
  38.             try {
  39.                 Thread.sleep(100);
  40.             } catch (InterruptedException e) {
  41.                 e.printStackTrace();
  42.             }
  43.         }
  44.     }
  45. }

   
 
        
      还有一种是，通过继承PriorityQueue并实现Comparable接口，然后自已重写过compareTo方法就能实现很强大的优先级队列了，不过缺点是线程不安全的！
      代码如下：
  1. package test;

  3. import java.util.PriorityQueue;

  5. public class PriorityTest extends PriorityQueue<PriorityTest.Test>{
  6.     static class Test implements Comparable<Test>{
  7.         String packet;
  8.         int priotity;
  9.         
  10.         public Test(String packet, int priotity) {
  11.             this.packet = packet;
  12.             this.priotity = priotity;
  13.         }
  14.         
  15.         public int compareTo(Test arg) { 
  16.             if(priotity < arg.priotity)
  17.                 return 1;
  18.             else if(priotity > arg.priotity)
  19.                 return -1;
  20.             else
  21.                 return 0;
  22.         } 
  23.         
  24.         public String toString(){
  25.             return packet; 
  26.         }
  27.     }
  28.     
  29.     public void add(String str, int priority){
  30.         super.add(new Test(str,priority));
  31.     }
  32.     
  33.     public static void main(String args[]){
  34.         PriorityTest pTest = new PriorityTest();
  35.         pTest.add("aaa",3);  //优先级最高
  36.         pTest.add("bbb",2);
  37.         pTest.add("ccc",1);
  38.         
  39.         while(!pTest.isEmpty()){
  40.             System.out.println(pTest.remove());
  41.         }
  42.     }
  43. }










摘自：http://blog.csdn.net/liuzhengkang/archive/2009/01/05/3714047.aspx

posted on 2009-08-15 17:25 石头@ 阅读(5512) 评论(1)  编辑  收藏 所属分类: DS & Alg

评论

# re: java中关于优先级队列的实现  回复  更多评论   

如果要线程安全的优先级队列不是有PriorityBlockingQueue么？不知道你用的哪个版本，不过jdk1.6里是有的
2012-07-19 20:51 | 游刃

只有注册用户登录后才能发表评论。
网站导航:
博客园   IT新闻   Chat2DB   C++博客   博问