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堆棧的區別