Queue and PriorityQueue

Queue is a data structure that maintains FIFO (First In First Out) order of elements. It means the element that goes first in a queue, comes out first; and one that goes last, comes last.

Queue Declaration

public interface Queue<E> extends Collection<E>  

PriorityQueue Class

The implementing class of Queue interface is PriorityQueue. This orders its elements based on the priorities. The higher priority element is placed before a lower priority element.

A practical example of a priority queue would be a queue in a hospital. If a critical patient comes in, his/her priority to be seen by the doctor is higher than others. Therefore, he/she would stand in the queue before all others.

How is priority decided?

DefaultpPriority of elements is natural sorting order as per their data type. If we want to override the default priority, then we have to use comparision methods, such as Comparable or Comparator.

Let’s see one example using default priority of String objects which is alphabetical.

package com.javatrainingschool;

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
	
	public static void main(String[] args) {
		
		Queue<String> nameQueue = new PriorityQueue<String>();
		
		nameQueue.add("Rajeev");
		nameQueue.add("Sam");
		nameQueue.add("Joe");
		nameQueue.add("Rameez");
		nameQueue.add("Arjun");
		
		while(nameQueue.size() > 0) {
	    	System.out.println(nameQueue.poll());	
	    }
	}
}

Output :
Arjun
Joe
Rajeev
Rameez
Sam

In the output, we can see that elements have been displayed in the alphabetical order which is natural sorting order of String objects. One more thing to notice here is that we have used poll() method inside while loop. Poll method retrieves the head element of the queue and removes it.

Head element of the queue

Head element of a queue is the first element of the queue that is out first from the queue. There are two methods using which we can retrieve head element of a queue.

Object element();    //retrieves the head element of the queue
Object peek();       //retrieves the head element of the queue

//The only difference between the two methods is that peek() returns null if the queue is empty. Whereas element() throws exception if the queue is empty

Fetch and remove the head element of the queue

There are two metods to fetch and remove head element of a queue.

Object remove();        //retrieves and removes the head element
Object poll();          //retrieves and removes the head element

//The only difference is that poll method return null, whereas remove() throws exception if the queue is empty.

How to retrieve the elements in the order of their priority from priority queue

This is very important. Because if you simply iterate over a priority queue using an iterator or for-each loop, you may not get the priority order in which the queue will out the elements from it. Therefore, we have to use poll method to test the priority order of elements.

Let’s understand this using below example

package com.javatrainingschool;

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
	
	public static void main(String[] args) {
		
		Queue<String> nameQueue = new PriorityQueue<String>();
		
		nameQueue.add("Rajeev");
		nameQueue.add("Sam");
		nameQueue.add("Joe");
		nameQueue.add("Rameez");
		nameQueue.add("Arjun");
		
		for(String name : nameQueue) {
			System.out.println("Name using iterator : " + name);
		}
		System.out.println("-----------------------------------");
		while(nameQueue.size() > 0) {
	    	System.out.println("Name using poll method : " + nameQueue.poll());	
	    }
	}
}

Output:
Name using iterator : Arjun
Name using iterator : Joe
Name using iterator : Rajeev
Name using iterator : Sam
Name using iterator : Rameez
-----------------------------------
Name using poll method : Arjun
Name using poll method : Joe
Name using poll method : Rajeev
Name using poll method : Rameez
Name using poll method : Sam

We can see in the results that Sam is coming before Rameez in iterator method, which is not alphabetical order.

PriorityQueue with custom priority

Now, we will see how we can define our own priority of elements. We can either use Comparable interface or Comparator interface.

In the below example, we will create a Person class that implements Comparable interface. Its sorting logic is that the person who has longest name will be the first element in the queue and the person with smallest name would be the last person in the list.

package com.javatrainingschool;

public class Person implements Comparable<Person>{

	private String name;
	
	@Override
	public int compareTo(Person o) {
	     return -1*(new 
                        Integer(this.getAlphabetCount(this.name)).compareTo(getAlphabetCount(o.name)));
	}
	
	public int getAlphabetCount(String name) {
		char[] noOfChars = name.toCharArray();
		return noOfChars.length;
	}

	public Person(String name) {
		super();
		this.name = name;
	}

	@Override
	public String toString() {
		return "Person [name=" + name + "]";
	}
	
}

package com.javatrainingschool;

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
	
	public static void main(String[] args) {
		
		Queue<Person> nameQueue = new PriorityQueue<Person>();
		
		Person p1 = new Person("Rajeev Kumar");
		Person p2 = new Person("Sam Clive");
		Person p3 = new Person("Joe Root");
		Person p4 = new Person("Rameez Raza");
		Person p5 = new Person("Arjun Singh Rajput");
		
		nameQueue.add(p1);
		nameQueue.add(p2);
		nameQueue.add(p3);
		nameQueue.add(p4);
		nameQueue.add(p5);
		
		while(nameQueue.size() > 0) {
	    	System.out.println(nameQueue.poll());	
	    }
	}
}

Output: 
Person [name=Arjun Singh Rajput]
Person [name=Rajeev Kumar]
Person [name=Rameez Raza]
Person [name=Sam Clive]
Person [name=Joe Root]

In the above example, Arjun Singh Rajput has longest name, and thus it is has the most priority, and thus the first element in the queue.

PriorityQueue priority using Comparator

Priority can also be defines using Comparator. We just have to write a custom comparator and pass the object of it using PriorityQueue constructor.

public class PersonComparator implements Comparator<Person> {

        //code here

}

Create a priority queue using PersonComparator object

PriorityQueue<Person> pQueue = new PriorityQueue<Person>(new PersonComparator());

Enough of the priority queue. The highest priority now is to grab our cup of tea. Cheers!