Java Queue and Priority Queue

Java Collection framework provides several interfaces – List, Set, Queue, Dequeue and classes – ArrayList, LinkedList, PriorityQueue, HashSet, SortedSet and TreeSet. Each of these is fundamentally a collection and therefore grouped under the common parent interface collection, although each has separate characteristics and therefore requires different implementation. Among these, Queue and PriorityQueue are discussed in the article.

Java Queue interface extends Collection interface to mimic Queue Data Structure in which elements (objects) are added to the end of the list and removed from the top – First In First Out (FIFO) structure. Priority Queue is essentially a queue in behaviour, although this behaviour is controlled by attaching some priority to ordering the object element. We may order the objects entering the queue by some criteria, such as ordering student objects by their grades and employee objects by their salary etc.

The following methods are defined by Queue:

Method Description Exception
element() Returns the element object E at the head of the queue and does not remove it. If the queue is empty, it throws NoSuchElementException
offer(E obj) Adds element object E to the queue. Returns true if obj was added and false otherwise. May fail in case the queue size is exceeded due to capacity restriction
peek() Returns the element object E at the head of the queue and does not remove it. It returns null if the queue is empty.
poll() Returns the element at the head of the queue and removes it. It returns null if the queue is empty.
remove() Returns the element at the head of the queue and removes it. If the queue is empty, it throws NoSuchElementException

In addition to the above, all methods defined by the Collection interface are also available in the Queue interface as Collection is the super interface of Queue. Some of the commonly used methods are:

Method Description Exception
add(E obj) Adds element object E to the queue. Returns true if it can add. If it is unable to add due to capacity restriction, it throws IllegalStateException
contains(E obj) Checks if the collection contains the object. Returns if the specified object is present in the queue. If the object obj is incompatible with the collection, it throws ClassCastException
isEmpty() Checks if the queue does not contain any element. Returns true if empty.
remove(E obj ) Remove the element from the queue and returns true. If the object obj is incompatible with the collection, it throws ClassCastException
size() Returns the number of elements in the collection

Points to note:

  • Elements can be removed only from the head of the queue.
  • An element in the queue cannot be null.
  • Since a queue is an interface, a concrete class implemented using a collection interface is required for creating a queue object. The most common among them are the  LinkedList, Dequeue, and PriorityQueue. 
  • Both poll() and remove() obtain and remove elements at the head of the queue. The difference is that poll( ) returns null if the queue is empty, but remove( ) throws an exception.
  • Both element( ) and peek( ) obtain but do not remove the element at the head of the queue. The difference is that peek( ) returns null if the queue is empty, but element( ) throws an exception.
  • Bothe add() and offer( ) add an element to the queue and return true if successful. But if they are unable to add due to capacity restriction, offer( ) returns false but add() throws an exception.

Exceptions:

  • A ClassCastException is thrown if an object passed as a parameter to a method call is incompatible with the collection elements
  • A NullPointerException is thrown if an attempt is made to store a null object
  • An IllegalArgumentException is thrown if an invalid argument is used.
  • An IllegalStateException is thrown if an attempt is made to add an element to a capacity restricted queue that is full.
  • A NoSuchElementException is thrown if an attempt is made to remove an element from an empty queue.

Following code example shows how to work with a queue collection. The queue uses LinkedList to create its object.

			

public class QueueTest {
    public static void main(String args[])
    {
        // Queue object is instantiated using the LinkedList class
        // Order of the elements of the queue is the order in which they entered the queue
        Queue<String> queue = new LinkedList<>();
        queue.add("Rajiv");
        queue.add("Amit");
        queue.add("Swapan");
        queue.add("Kumar");
        
        //  Display the contents of the queue and its size.
        System.out.println("Elements of queue: " + queue+" & its size: "+queue.size());
        //  Peek returns the head of the queue but does not remove
        System.out.println("Head of the queue: " + queue.peek());
        System.out.println("Head of the queue: " + queue.element());
        System.out.println("Size of the queue: " + queue.size());

        //  Poll returns the head of the queue and removes it, so does remove
        //  Difference is in their behaviour if the queue is empty
        System.out.println("Head of the queue: " + queue.poll());
        System.out.println("Head of the queue: " + queue.poll());
        System.out.println("Head of the queue: " + queue.remove());
        System.out.println("Head of the queue: " + queue.poll());

        System.out.println("Size of the queue: " + queue.size());
        System.out.println("Is queue empty: "+queue.isEmpty());
        
        System.out.println("Head of the queue: " + queue.offer("Tapan"));
        System.out.println("Head of the queue: " + queue.offer("Gautam"));
        System.out.println("Head of the queue: " + queue.peek());
        
        Iterator iterator = queue.iterator();
             while (iterator.hasNext()) {System.out.print(iterator.next() + " ");}
        System.out.println();
        
    }
}


				

Output:

Elements of the queue: [Rajiv, Amit, Swapan, Kumar] & its size: 4 Head of the queue: Rajiv Head of the queue: Rajiv Size of the queue: 4 Head of the queue: Rajiv Head of the queue: Amit Head of the queue: Swapan Head of the queue: Kumar Size of the queue: 0 Is queue empty: true Head of the queue: true Head of the queue: true Head of the queue: Tapan Tapan Gautam

Following output is obtained if we replace the queue object creation statement #1 in the main() function with the statement

			

Queue<String> queue = new PriorityQueue<>();

				

Output:

Elements of the queue: [Amit, Kumar, Swapan, Rajiv] & its size: 4 Head of the queue: Amit Head of the queue: Amit Size of the queue: 4 Head of the queue: Amit Head of the queue: Kumar Head of the queue: Rajiv Head of the queue: Swapan Size of the queue: 0 Is queue empty: true Head of the queue: true Head of the queue: true Head of the queue: Gautam Gautam Tapan

Note that the order of the queue is now changed. The queue of strings is ordered in the lexicographical order of the strings, not in the order they were added to the queue. This is because we have now used PriorityQueue for implementation, which uses its natural lexicographic order for arranging the queue. Let us have a look at another example of PriorityQueue of Integer objects. The output shows that the numbers appear in the queue in ascending sequence, although they were added in random order.

			

// Priority Queue Example
import java.util.PriorityQueue;

public class PriorityQueueTest {
    public static void main(String args[])
    {
        //  Create a Priority Queue of Integers and add some numbers randomly to it
        //  The numbers will be added to the queue in ascending sequence – the smallest on top 
        PriorityQueue<Integer> marks = new PriorityQueue();
        marks.add(79);
        marks.add(70);
        marks.add(30);
        marks.add(96);
        marks.add(50);
        //  remove the numbers one by one from the queue and see the number sequence
        while (!marks.isEmpty()) {
            System.out.println("The number removed from the Head of the queue = "+marks.remove());
        }
}


				

Output:

The number removed from the Head of the queue = 30 The number removed from the Head of the queue = 50 The number removed from the Head of the queue = 70 The number removed from the Head of the queue = 79 The number removed from the Head of the queue = 96

Priority Queue

PriorityQueue is a concrete class; it implements a Queue interface to support priority-based queues. Although by definition, the queue follows FIFO, in some cases, we need to attach priority to the elements of the queue for its ordering and operation. This is why the priority queue comes into existence. It can be instantiated with two parameters – a capacity which defines its initial capacity and a Comparator object which defines its ordering pattern. PriorityQueue defines the six constructors. They are

  1. PriorityQueue( ) // initial capacity is 11
  2. PriorityQueue(int capacity) // initial capacity defined
  3. PriorityQueue(int capacity, Comparator comp) // specified initial capacity and a comparator
  4. PriorityQueue(Collection c) // Initialized from the elements of the Collection
  5. PriorityQueue(PriorityQueue c) // Initialized from the elements of another PriorityQueue
  6. PriorityQueue(SortedSet c) // Initialized from the elements of a SortedSet

As elements are added to the queue, it grows automatically, irrespective of the defined initial capacity. If no comparator is specified when a PriorityQueue is constructed, then the default comparator for the type of data stored in the queue is used. The default comparator orders the queue in ascending order. Thus, the head of the queue is the smallest value.   However, by providing a custom comparator, you can specify a different ordering scheme. The following example shows the use of a custom comparator to order a queue in descending order of the strings.

			

import java.util.PriorityQueue;

public class PriorityQueueTest {
    public static void main(String args[])
    {
        Comparator<String> comparator = new MyComparator();
        PriorityQueue<String> p_queue = new PriorityQueue(10, comparator);

        p_queue.add("Basudev");
        p_queue.add("Amit");
        p_queue.add("Debashis");
        p_queue.add("Chandan");
        
        //  Display the contents of the queue and its size.
        System.out.println("Elements of queue: " + p_queue+" & its size: "+p_queue.size());

        //  Poll returns the head of the queue: and removes it, so does remove
        //  Difference is in their behaviour if the queue: is empty
        System.out.println("Head of the queue: " + p_queue.poll());
        p_queue.add("Pulak");
        p_queue.add("Kanjan");
        System.out.println("Head of the queue: " + p_queue.poll());
        System.out.println("Head of the queue: " + p_queue.remove());
        System.out.println("Head of the queue: " + p_queue.poll());
    }
}
class MyComparator implements Comparator<String> {
    public int compare(String x, String y) {
        if (x.compareTo(y) < 0)
            return 1;
        else    
            return -1;
    }
}


				

Output:

Elements of queue: [Debashis, Chandan, Basudev, Amit] & its size: 4 Head of the queue: Debashis Head of the queue: Pulak Head of the queue: Kanjan Head of the queue: Chandan

We can use an iterator to iterate through a PriorityQueue collection, but the order of that iteration is undefined.