Queues and Priority Queues

In a priority queue, the element with the highest priority is removed first. A queue is a first-in, first-out data structure. Elements are appended to the end of the queue and are removed from the beginning of the queue. In a priority queue, elements are assigned priorities. When accessing elements, the element with the highest priority is removed first. This section introduces queues and priority queues in the Java API.

The Queue Interface

The Queue interface extends java.util.Collection with additional insertion, extraction, and inspection operations, as shown in Figure below.

The offer method is used to add an element to the queue. This method is similar to the add method in the Collection interface, but the offer method is preferred for queues. The poll and remove methods are similar, except that poll() returns null if the queue is empty, whereas remove() throws an exception. The peek and element methods are similar, except that peek() returns null if the queue is empty, whereas element() throws an exception.

Deque and LinkedList

The LinkedList class implements the Deque interface, which extends the Queue interface, as shown in Figure below. Therefore, you can use LinkedList to create a queue. LinkedList is ideal for queue operations because it is efficient for inserting and removing elements from both ends of a list.

Deque supports element insertion and removal at both ends. The name deque is short for “double-ended queue” and is usually pronounced “deck.” The Deque interface extends Queue with additional methods for inserting and removing elements from both ends of the queue. The methods addFirst(e), removeFirst(), addLast(e), removeLast(), getFirst(), and getLast() are defined in the Deque interface.

The code below shows an example of using a queue to store strings. Line 6 creates a queue using LinkedList. Four strings are added to the queue in lines 7–10. The size() method defined in the Collection interface returns the number of elements in the queue (line 12). The remove() method retrieves and removes the element at the head of the queue (line 13).

The PriorityQueue class implements a priority queue, as shown in Figure below. By default, the priority queue orders its elements according to their natural ordering using Comparable. The element with the least value is assigned the highest priority and thus is removed from the queue first. If there are several elements with the same highest priority, the tie is broken arbitrarily. You can also specify an ordering using Comparator in the constructor PriorityQueue(initialCapacity, comparator).

The code below shows an example of using a priority queue to store strings. Line 7 creates a priority queue for strings using its no-arg constructor. This priority queue orders the strings using their natural order, so the strings are removed from the queue in increasing order. Lines 18 create a priority queue using the comparator obtained from Collections.reverseOrder(), which orders the elements in reverse order, so the strings are removed from the queue in decreasing order.