PriorityQueue是Java中的一種優先隊列數據結構,它繼承自AbstractQueue類并實現了Queue接口。它的特點是每次從隊列中取出元素時,都會取出優先級最高的元素。
PriorityQueue內部使用堆(Heap)實現,具體來說是使用二叉小頂堆(Binary Min Heap)實現。在二叉小頂堆中,父節點的值總是小于或等于它的子節點的值。這意味著當我們從PriorityQueue中取出元素時,總是從堆頂取出,這個元素就是當前最小的元素。
PriorityQueue可以存儲任意類型的元素,只要這些元素實現了Comparable接口或者我們提供了比較器(Comparator)來比較元素的優先級。
創建PriorityQueue的示例代碼如下:
PriorityQueue<Integer> pq = new PriorityQueue<>();
在上面的代碼中,我們創建了一個存儲Integer類型的PriorityQueue。
添加元素到PriorityQueue的示例代碼如下:
pq.add(5);
pq.add(3);
pq.add(8);
在上面的代碼中,我們調用了add()方法來向PriorityQueue中添加元素。添加元素后,PriorityQueue會自動調整元素的位置以保持堆的性質。
從PriorityQueue中取出元素的示例代碼如下:
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
在上面的代碼中,我們使用了一個while循環來不斷從PriorityQueue中取出元素并打印。使用poll()方法可以取出并刪除堆頂的元素。
如果我們希望PriorityQueue按照自定義的優先級進行排序,可以使用帶比較器的構造函數來創建PriorityQueue,示例代碼如下:
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
上面的代碼中,我們使用了Collections.reverseOrder()來創建一個逆序的比較器,這樣PriorityQueue就會按照降序排序。
除了基本的添加和取出操作,PriorityQueue還提供了一些其他的方法,如size()方法可以返回PriorityQueue中的元素個數,peek()方法可以返回堆頂的元素而不刪除它。
總的來說,PriorityQueue是Java中非常常用的數據結構,它可以方便地實現優先隊列的功能。