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

核心提示：这几天一直在搞关于优先级队列的实现,因为要考虑到线程的安全,所以PRiorityQueue就不适用了，一个非常简单的实现方法，java中关于优先级队列的实现，那就是把优先级比较好的插入一个队列，优先级低的插入另一个队列，所以它的吞吐量是很不错的！简单代码如下：packagetest; importjava.util.c

　　这几天一直在搞关于优先级队列的实现,因为要考虑到线程的安全,所以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());
　　　　}
　　}
}