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

2019-11-17 04:00:41

字体：大中小

来源：转载

供稿：网友

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

import  java.util.concurrent.ConcurrentLinkedQueue ;

public   class  PriorityQueueTest {

     public   static   void  main(String[] args) {
        ConcurrentLinkedQueue <String> highPriority =  new  ConcurrentLinkedQueue <String>();  //高优先级
        ConcurrentLinkedQueue <String> lowPriority =  new  ConcurrentLinkedQueue <String>();   //低优先级

        highPriority.add( "aaa" );
        highPriority.add( "bbb" );
        highPriority.add( "111" );

        lowPriority.add( "ccc" );
        lowPriority.add( "ddd" );
        lowPriority.add( "222" );

         int  i =  0  ,j =  0 , k= 0 ;
         while ( true ){
             while ( true ){
                 if (!highPriority.isEmpty()){
                    System.out.print(highPriority.remove());
                    i++;
                    k++;
                    System.out.println( ", i = " +i+ ", k=" +k);
                     break ;
                }
                 if (!lowPriority.isEmpty()){
                    System.out.print(lowPriority.remove());
                    j++;
                    k++;
                    System.out.println( ", j = " +j+ ", k=" +k);
                     break ;
                }
                 break ;
            }
             try  {
                Thread.sleep( 100 );
            }  catch  (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}




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

import  java.util.PriorityQueue;

public   class  PriorityTest  extends  PriorityQueue<PriorityTest.Test>{
     static   class  Test  implements  Comparable<Test>{
        String packet;
         int  priotity;

         public  Test(String packet,  int  priotity) {
             this .packet = packet;
             this .priotity = priotity;
        }

         public   int  compareTo(Test arg) {
             if (priotity < arg.priotity)
                 return   1 ;
             else   if (priotity > arg.priotity)
                 return  - 1 ;
             else
                 return   0 ;
        }

         public  String toString(){
             return  packet;
        }
    }

     public   void  add(String str,  int  priority){
         super .add( new  Test(str,priority));
    }

     public   static   void  main(String args[]){
        PriorityTest pTest =  new  PriorityTest();
        pTest.add( "aaa" , 3 );  //优先级最高
        pTest.add( "bbb" , 2 );
        pTest.add( "ccc" , 1 );

         while (!pTest.isEmpty()){
            System.out.println(pTest.remove());
        }
    }
}

上一篇：Java枚举工具类ValuedEnum用法

下一篇：JAVA堆栈的区别