java中關於優先權佇列的實現

這幾天一直在搞關於優先權佇列的實作,因為要考慮到執行緒的安全性,所以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());
}
}