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. 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.

PriorityQueue class was introduced in Java 1.5 and it’s part of Java Collections Framework.

PriorityQueue is an unbounded queue based on a priority heap and the elements of the priority queue are ordered by default in natural order. We can provide a Comparator for ordering at the time of instantiation of priority queue.

Java Priority Queue doesn’t allow null values and we can’t create PriorityQueue of Objects that are non-comparable. We use java Comparable and Comparator for sorting Objects and Priority Queue use them for priority processing of it’s elements.

The head of the priority queue is the least element based on the natural ordering or comparator based ordering, if there are multiple objects with same ordering, then it can poll any one of them randomly. When we poll the queue, it returns the head object from the queue.

Java Priority Queue size is unbounded but we can specify the initial capacity at the time of it’s creation. When we add elements to the priority queue, it’s capacity grows automatically.

PriorityQueue is not thread safe, so java provides PriorityBlockingQueue class that implements the BlockingQueue interface to use in java multithreading environment.

Java Priority Queue implementation provides O(log(n)) time for enqueing and dequeing method.

Let’s see an example of java PriorityQueue for natural ordering as well as with Comparator.

We have our custom class Customer that doesn’t provide any type of ordering, so when we will try to use it with PriorityQueue we should provide a comparator object for that.

package com.journaldev.collections;

public class Customer {
  
  private int id;
  private String name;
  
  public Customer(int i, String n){
    this.id=i;
    this.name=n;
  }

  public int getId() {
    return id;
  }

  public String getName() {
    return name;
  }
  
}

We will use java random number generation to generate random customer objects. For natural ordering, I will use Integer that is also a java wrapper class.

Here is our final test code that shows how to use priority queue in java.

package com.journaldev.collections;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

public class PriorityQueueExample {

  public static void main(String[] args) {
    
    //natural ordering example of priority queue
    Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7);
    Random rand = new Random();
    for(int i=0;i<7;i++){
      integerPriorityQueue.add(new Integer(rand.nextInt(100)));
    }
    for(int i=0;i<7;i++){
      Integer in = integerPriorityQueue.poll();
      System.out.println("Processing Integer:"+in);
    }
    
    //PriorityQueue example with Comparator
    Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator);
    addDataToQueue(customerPriorityQueue);
    
    pollDataFromQueue(customerPriorityQueue);
    
  }
  
  //Comparator anonymous class implementation
  public static Comparator<Customer> idComparator = new Comparator<Customer>(){
    
    @Override
    public int compare(Customer c1, Customer c2) {
            return (int) (c1.getId() - c2.getId());
        }
  };

  //utility method to add random data to Queue
  private static void addDataToQueue(Queue<Customer> customerPriorityQueue) {
    Random rand = new Random();
    for(int i=0; i<7; i++){
      int id = rand.nextInt(100);
      customerPriorityQueue.add(new Customer(id, "Pankaj "+id));
    }
  }
  
  //utility method to poll data from queue
  private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) {
    while(true){
      Customer cust = customerPriorityQueue.poll();
      if(cust == null) break;
      System.out.println("Processing Customer with ID="+cust.getId());
    }
  }

}

Notice that I am using java anonymous class for implementing Comparator interface and creating our id based comparator.

When I run above java priority queue example test program, it generates the following output.

Processing Integer:9
Processing Integer:16
Processing Integer:18
Processing Integer:25
Processing Integer:33
Processing Integer:75
Processing Integer:77
Processing Customer with ID=6
Processing Customer with ID=20
Processing Customer with ID=24
Processing Customer with ID=28
Processing Customer with ID=29
Processing Customer with ID=82
Processing Customer with ID=96

From output it’s clear that least element was at head and got polled first. If we won’t provide comparator while creating customerPriorityQueue, it will throw ClassCastException at runtime.

Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable
  at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633)
  at java.util.PriorityQueue.siftUp(PriorityQueue.java:629)
  at java.util.PriorityQueue.offer(PriorityQueue.java:329)
  at java.util.PriorityQueue.add(PriorityQueue.java:306)
  at com.journaldev.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45)
  at com.journaldev.collections.PriorityQueueExample.main(PriorityQueueExample.java:25)