PriorityQueue and priorityblockingqueue

brief introduction

Generally speaking, queues are FIFO. Of course, we also introduced that deque can be used as a stack. Today, we introduce a PriorityQueue, which can sort objects in natural order or custom order in the queue.

PriorityQueue

Let's first look at the PriorityQueue, which inherits from abstractqueue and is non thread safe.

The capacity of PriorityQueue is unbounded, that is, it has no capacity limit, so you can add elements indefinitely. If you add too many elements, an outofmemoryerror exception will be reported in the end.

Here we teach you a recognition skill. As long as the collection class has capability, most of its underlying implementations are arrays, because only arrays have capacity. Of course, there are exceptions, such as linkedblockingdeque.

As long as there is a comparator in the collection class, the collection must be an ordered collection.

Let's look at PriorityQueue:

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

If the initial capacity and comparator are defined, the underlying implementation of PriorityQueue is array, and it is an ordered collection.

By default, ordered collections are sorted according to natural ordering. If you pass in comparator, they will be sorted according to the method you specify. Let's see two examples of sorting:

@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("{},third);
    }
}

By default, it will be arranged in ascending order. In the second example, if we pass in a comparator in reverse order, it will be arranged in reverse order.

PriorityBlockingQueue

Priorityblockingqueue is a BlockingQueue, so it is thread safe.

Let's consider the question: if the natural ordering or comparator order of two objects is the same, is the order of two objects still fixed?

In this case, the default order cannot be determined, but we can encapsulate the objects in this way, so that the objects can be sorted according to the creation order first in first out FIFO when the sorting order is the same:

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;
    }
}

In the above example, first compare the natural ordering of two entries. If they are consistent, then sort them according to seqnum.

Examples of this article https://github.com/ddean2009/learn-java-collections