Java中的PriorityQueue

什么是Java中的PriorityQueue？

隊列遵循先進先出（First-In-First-Out）算法，而PriorityQueue的隊列元素則根據(jù)優(yōu)先級進行處理（按自然順序或根據(jù)創(chuàng)建時提供的自定義比較器排序）。PriorityQueue基于優(yōu)先級堆。我們無法創(chuàng)建不可比較對象的PriorityQueue。向PriorityQueue插入null將拋出NullPointerException，因為Java中的PriorityQueue不允許null元素。PriorityQueue是無界隊列。此隊列的頭是相對于指定排序的最小元素。如果多個元素的值相同，則頭是這些元素中的一個——平局將任意打破。隊列檢索操作poll、remove、peek和element訪問隊列頭部的元素。PriorityQueue從AbstractQueue、AbstractCollection、Collection和Object類繼承方法。在PriorityQueue中插入元素（offer()）和刪除元素（poll()）的時間復(fù)雜度均為O(log n)，其中n是隊列中的元素數(shù)量。默認(rèn)的PriorityQueue使用最小堆實現(xiàn)，這意味著堆中的頂部元素是最小的。如果我們想實現(xiàn)最大堆，則需要使用自定義比較器。在內(nèi)部，Java中的PriorityQueue使用數(shù)組存儲元素。如果初始容量（在JDK 17中默認(rèn)是11）不足以容納所有添加到隊列中的元素，則該數(shù)組會自動增大。雖然在創(chuàng)建PriorityQueue時不必指定初始容量，但如果您知道將要添加的元素數(shù)量，設(shè)置初始容量是有益的。這有助于防止隊列頻繁調(diào)整大小，從而避免浪費CPU資源。

您能提供一個PriorityQueue有用的示例場景嗎？

PriorityQueue可以用于操作系統(tǒng)中的任務(wù)調(diào)度等場景，在這些場景中，具有更高優(yōu)先級的任務(wù)需要在較低優(yōu)先級的任務(wù)之前執(zhí)行。

PriorityQueue構(gòu)造函數(shù)

• PriorityQueue()：創(chuàng)建一個具有默認(rèn)初始容量（11）的PriorityQueue，該隊列根據(jù)自然順序?qū)ζ湓剡M行排序。
• PriorityQueue(Collection c)：創(chuàng)建一個包含指定集合中元素的PriorityQueue。
• PriorityQueue(int initialCapacity)：創(chuàng)建一個具有指定初始容量的PriorityQueue，該隊列根據(jù)自然順序?qū)ζ湓剡M行排序。
• PriorityQueue(int initialCapacity, Comparator comparator)：創(chuàng)建一個具有指定初始容量的PriorityQueue，該隊列根據(jù)指定比較器對其元素進行排序。
• PriorityQueue(PriorityQueue c)：創(chuàng)建一個包含另一個優(yōu)先隊列中元素的PriorityQueue。
• PriorityQueue(SortedSet c)：創(chuàng)建一個包含指定排序集中的元素的PriorityQueue。

PriorityQueue操作

• boolean add(E element)：將指定元素插入此優(yōu)先隊列。
• boolean offer(E e)：用于將特定元素插入優(yōu)先隊列。
• public peek()：檢索但不移除此隊列的頭部，若隊列為空則返回null。
• public poll()：檢索并移除此隊列的頭部，若隊列為空則返回null。
• public remove()：從此隊列中移除指定元素的單個實例（如果存在）。當(dāng)我們從優(yōu)先隊列中移除元素時，首先移除的是按照指定順序的最小元素。
• Iterator iterator()：返回此隊列中元素的迭代器。
• boolean contains(Object o)：若此隊列包含指定元素則返回true。
• void clear()：用于移除優(yōu)先隊列的所有內(nèi)容。
• int size()：返回集合中存在的元素數(shù)量。
• toArray()：用于返回一個包含此隊列中所有元素的數(shù)組。
• Comparator comparator()：用于返回可以用于排序隊列元素的比較器。

offer和add方法的區(qū)別是什么？

offer()和add()是兩種將數(shù)據(jù)插入PriorityQueue的方法。在隊列中，add用于將指定元素插入隊列。成功時返回true，否則拋出異常。offer()也用于將指定元素插入隊列，但成功時返回true，否則返回false。在PriorityQueue的情況下，add方法的行為與offer()相同。如果查看實現(xiàn)，PriorityQueue的add方法內(nèi)部調(diào)用了offer。

PriorityQueue示例

import java.util.Iterator;
import java.util.PriorityQueue;
public class PriorityQueueDemo {
public static void main(String[] args) {
		
		PriorityQueue<String> pQueue = new PriorityQueue<>();
		pQueue.add("Sebastian");
		pQueue.add("Boguslaw");
		pQueue.add("Kazimierz ");
		pQueue.add("Bozena");
		System.out.println("Size of pQueue:" + pQueue.size()); // 4
		Object[] arr = pQueue.toArray();
		System.out.println("Coverting pQueue into Array: ");
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i].toString() + ", ");// Boguslaw, Bozena, Kazimierz , Sebastian,
		System.out.println();
		Iterator<String> pqItr = pQueue.iterator();
		while (pqItr.hasNext())
			System.out.print(pqItr.next() + ", ");// Boguslaw, Bozena, Kazimierz, Sebastian,
		System.out.println();
		pQueue.remove("Bozena");
		System.out.println("Printing pQueue after removing Bozena");
		pqItr = pQueue.iterator();
		while (pqItr.hasNext())
			System.out.print(pqItr.next() + ", ");// Boguslaw, Kazimierz , Sebastian,
		boolean isPresent = pQueue.contains("Bozena");
		System.out.println("pQueue contains Bozena or not? " + isPresent); // false
		
		isPresent = pQueue.contains("Sebastian");
		System.out.println("pQueue contains Sebastian or not? " + isPresent); // true
		System.out.println("Head of pQueue from peek:" + pQueue.peek());// Boguslaw
		System.out.println("Head of pQueue from poll:" + pQueue.poll());// Boguslaw
		pqItr = pQueue.iterator();
		while (pqItr.hasNext())
			System.out.print(pqItr.next() + ", ");// Kazimierz , Sebastian,
		System.out.println();
		pQueue.clear();
		System.out.println("Size of pQueue after calling clear:" + pQueue.size()); // 0
	}	
}

若你想提升Java技能，可關(guān)注我們的Java培訓(xùn)課程。