快捷導(dǎo)航

Java PriorityQueue數(shù)據(jù)結(jié)構(gòu)接口原理及用法

更新時間：2020年10月21日 09:50:31 作者：cuisuqiang

這篇文章主要介紹了Java PriorityQueue數(shù)據(jù)結(jié)構(gòu)接口原理及用法,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下

PriorityQueue是從JDK1.5開始提供的新的數(shù)據(jù)結(jié)構(gòu)接口，它是一種基于優(yōu)先級堆的極大優(yōu)先級隊列。優(yōu)先級隊列是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素。如果不提供Comparator的話，優(yōu)先隊列中元素默認按自然順序排列，也就是數(shù)字默認是小的在隊列頭，字符串則按字典序排列（參閱 Comparable），也可以根據(jù) Comparator 來指定，這取決于使用哪種構(gòu)造方法。優(yōu)先級隊列不允許 null 元素。依靠自然排序的優(yōu)先級隊列還不允許插入不可比較的對象（這樣做可能導(dǎo)致 ClassCastException）

優(yōu)先級隊列是無界的，但是有一個內(nèi)部容量，控制著用于存儲隊列元素的數(shù)組大小。它通常至少等于隊列的大小。隨著不斷向優(yōu)先級隊列添加元素，其容量會自動增加。無需指定容量增加策略的細節(jié)

簡單應(yīng)用：

package test;
import java.util.PriorityQueue;
public class PriorityQueueTest1 {
 @SuppressWarnings("unchecked")
 public static void main(String[] args) {
 PriorityQueue queue = new PriorityQueue();
 queue.add("AAAAA"); // Add接受的參數(shù)是Obj，PriorityQueue使用integer String等基本的數(shù)據(jù)類型時，默認new時有參數(shù)，如果不寫則是按照默認排序
 queue.add("BBBBB"); 
 queue.add("CCCCC"); 
 queue.add("DDDDD"); 
 
 System.out.println(queue.peek()); // 獲取但不移除此隊列的頭
 System.out.println(queue.poll()); // 獲取并移除此隊列的頭
 System.out.println(queue.poll());
 
 queue.offer("ZZZZZ"); // 將指定的元素插入此優(yōu)先級隊列
 
 System.out.println(queue.poll());
 System.out.println(queue.poll());
 System.out.println(queue.poll());
 
 System.out.println(queue.poll()); // 到這里已經(jīng)沒有元素，打印Null
 }
}

定義比較器：

package test;
import java.util.Comparator;
import java.util.PriorityQueue;
@SuppressWarnings("unchecked")
public class PriorityQueueTest2 {
 private static PriorityQueue queue = new PriorityQueue(10,new Comparators());
 public static void main(String[] args) {
 QueueObject queueObject = new QueueObject();
 queueObject.setId(4);
 queueObject.setObject("AAAAA");
 queue.add(queueObject);
 QueueObject queueObject1 = new QueueObject();
 queueObject1.setId(1);
 queueObject1.setObject("BBBBB");
 queue.add(queueObject1);
 QueueObject queueObject2 = new QueueObject();
 queueObject2.setId(3);
 queueObject2.setObject("CCCCC");
 queue.add(queueObject2);
 
 System.out.println(((QueueObject)queue.poll()).getObject());
 System.out.println(((QueueObject)queue.poll()).getObject());
 System.out.println(((QueueObject)queue.poll()).getObject());
 }
}
class QueueObject {
  private int id;
  private Object object;
  public int getId() {
    return id;
  }
  public void setId(int id) {
    this.id = id;
  }
  public Object getObject() {
    return object;
  }
  public void setObject(Object object) {
    this.object = object;
  }
}
@SuppressWarnings("unchecked")
class Comparators implements Comparator{
  public int compare(Object arg0, Object arg1) {
    int val1 = ((QueueObject)arg0).getId();
    int val2 = ((QueueObject)arg1).getId();
    return val1 < val2 ? 0 : 1;
  }
}

注意事項：

注意1：該隊列是用數(shù)組實現(xiàn)，但是數(shù)組大小可以動態(tài)增加，容量無限。

注意2:此實現(xiàn)不是同步的。不是線程安全的。如果多個線程中的任意線程從結(jié)構(gòu)上修改了列表，則這些線程不應(yīng)同時訪問 PriorityQueue 實例，這時請使用線程安全的PriorityBlockingQueue 類。

注意3:不允許使用 null 元素。

注意4：此實現(xiàn)為插入方法（offer、poll、remove() 和 add 方法）提供 O(log(n)) 時間；

為 remove(Object) 和 contains(Object) 方法提供線性時間；
為檢索方法（peek、element 和 size）提供固定時間。

注意5:方法iterator()中提供的迭代器并不保證以有序的方式遍歷優(yōu)先級隊列中的元素。

至于原因可參考下面關(guān)于PriorityQueue的內(nèi)部實現(xiàn)

如果需要按順序遍歷，請考慮使用 Arrays.sort(pq.toArray())。

注意6：可以在構(gòu)造函數(shù)中指定如何排序。如：