Is PriorityQueue a FIFO Queue?

Question

PriorityQueue implements Queue, but is PriorityQueue a FIFO data structure like Queue?

Mahalia

it is priority based, not order based – Tejeda

Answer 1

From the Queue interface:

Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering

So PriorityQueue is an exception and it becomes a FIFO queue only if the comparator sorts in that order.

Uttica

Answer 2

No, it is not. As per Javadoc

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used

AND

The head of this queue is the least element with respect to the specified ordering

Surge

+1 notionally the ordering could be FIFO, but it is usually used for something more interesting. – Yeaton

Answer 3

PriorityQueue does not care about FIFO / LIFO. it handles priority. in case of several objects with same priority - you can't count on any of FIFO LIFO behavior.

Stonyhearted

Answer 4

A priority queue is a data structure which keeps elements in a consistent internal order - in the Java implementation this ordering is specified at construction time. The head of the queue, and the order of the other elements is determined by the ordering criteria you specify.

For example, say you have a PriorityQueue containing students, and the ordering you set is ascending age - the head of the queue will contain the youngest student and the tail will be the oldest. As you add to the PriorityQueue, student will be inserted in the correct position according to their age, as that is the ordering you specified, the order of their insertion is irrelevant.

Wharf

Answer 5

Queues in Java does not necessarily follow FIFO (First-In First Out) principle. Refer here: https://docs.oracle.com/javase/9/docs/api/java/util/Queue.html

Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering.

PriorityQueue does not follow FIFO principle which must be the reason for your problem

Chesson

Answer 6

It hinges on the Comparator you use.

For instance, say you're using a Priority Queue to manage an Event Queue of events scheduled to be called in the future, whether in wall-clock future or in a notional batch-mode future. The highest priority is basically the earliest time, and you'd use a comparator such as:

first.time < second.time

If the Comparator simply compares the time of two events, they will be dequeued in an undefined order and most likely not FIFO.

However, you can maintain a count of your Enqueue operations; store that in the priority queue elements; and make your comparison use the queue operation as a tie-breaker. Example:

first.time < second.time || ( first.time == second.time && first.count < second.count )

Then you will get FIFO behavior. If the counter is 32 bit, you can do 1000 enqueues/sec for 1000 hours before it wraps around. If the counter is 64-bit, you can do a billion enqueues/sec for 500+ years before it wraps. Even when the counter wraps, you can simply renumber all existing Priority Queue elements: deque them all into a vector; sort the vector; overwrite each vector element's counter with its vector element number; and reinsert to the priority queue. That vector size becomes your new counter.

Allele