如何理解PriorityQueue和PriorityBlockingQueue

發(fā)布時(shí)間：2021-11-17 11:06:03 來源：億速云閱讀：156 作者：柒染欄目：大數(shù)據(jù)

如何理解PriorityQueue和PriorityBlockingQueue，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

簡介

Queue一般來說都是FIFO的，當(dāng)然之前我們也介紹過Deque可以做為棧來使用。今天我們介紹一種PriorityQueue，可以按照對(duì)象的自然順序或者自定義順序在Queue中進(jìn)行排序。

PriorityQueue

先看PriorityQueue，這個(gè)Queue繼承自AbstractQueue，是非線程安全的。

PriorityQueue的容量是unbounded的，也就是說它沒有容量大小的限制，所以你可以無限添加元素，如果添加的太多，最后會(huì)報(bào)OutOfMemoryError異常。

這里教大家一個(gè)識(shí)別的技能，只要集合類中帶有CAPACITY的，其底層實(shí)現(xiàn)大部分都是數(shù)組，因?yàn)橹挥袛?shù)組才有capacity，當(dāng)然也有例外，比如LinkedBlockingDeque。

只要集合類中帶有comparator的，那么這個(gè)集合一定是個(gè)有序集合。

我們看下PriorityQueue：

private static final int DEFAULT_INITIAL_CAPACITY = 11;
private final Comparator<? super E> comparator;

定義了初始Capacity和comparator，那么PriorityQueue的底層實(shí)現(xiàn)就是Array，并且它是一個(gè)有序集合。

有序集合默認(rèn)情況下是按照natural ordering來排序的，如果你傳入了 Comparator,則會(huì)按照你指定的方式進(jìn)行排序，我們看兩個(gè)排序的例子：

@Slf4j

public class PriorityQueueUsage {

@Test
public void usePriorityQueue(){
PriorityQueue<Integer> integerQueue = new PriorityQueue<>();

integerQueue.add(1);
integerQueue.add(3);
integerQueue.add(2);

int first = integerQueue.poll();
int second = integerQueue.poll();
int third = integerQueue.poll();

log.info("{},{},{}",first,second,third);
}

@Test
public void usePriorityQueueWithComparator(){
PriorityQueue<Integer> integerQueue = new PriorityQueue<>((a,b)-> b-a);
integerQueue.add(1);
integerQueue.add(3);
integerQueue.add(2);

int first = integerQueue.poll();
int second = integerQueue.poll();
int third = integerQueue.poll();

log.info("{},{},{}",first,second,third);
}}

默認(rèn)情況下會(huì)按照升序排列，第二個(gè)例子中我們傳入了一個(gè)逆序的Comparator，則會(huì)按照逆序排列。

PriorityBlockingQueue

PriorityBlockingQueue是一個(gè)BlockingQueue，所以它是線程安全的。

我們考慮這樣一個(gè)問題，如果兩個(gè)對(duì)象的natural ordering或者Comparator的順序是一樣的話，兩個(gè)對(duì)象的順序還是固定的嗎？

出現(xiàn)這種情況，默認(rèn)順序是不能確定的，但是我們可以這樣封裝對(duì)象，讓對(duì)象可以在排序順序一致的情況下，再按照創(chuàng)建順序先進(jìn)先出FIFO的二次排序：

public class FIFOEntry<E extends Comparable<? super E>>
implements Comparable<FIFOEntry<E>> {
static final AtomicLong seq = new AtomicLong(0);
final long seqNum;
final E entry;
public FIFOEntry(E entry) {
seqNum = seq.getAndIncrement();
this.entry = entry;
}
public E getEntry() { return entry; }
public int compareTo(FIFOEntry<E> other) {
int res = entry.compareTo(other.entry);
if (res == 0 && other.entry != this.entry)
res = (seqNum < other.seqNum ? -1 : 1);
return res;
}}

上面的例子中，先比較兩個(gè)Entry的natural ordering，如果一致的話，再按照seqNum進(jìn)行排序。

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝您對(duì)億速云的支持。

向AI問一下細(xì)節(jié)

如何理解PriorityQueue和PriorityBlockingQueue

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽