Queue In JAVA | PriorityQueue In Java

Queue In JAVA | PriorityQueue In Java

Queue is data-structure that follows FIFO (First In First Out) architecture. That’s means element added at first in queue will be retrieved at first.

Let’s understand this using below example. In this example we are adding 22, 13, 3, 22, 10, 23, 54, 22, 1 it will be added in order of the insertion just like ArrayList in order [22, 13, 3, 22, 10, 23, 54, 22, 1] as shown in the below image. But unlike array Queue does not allow random access.

Queue

But here is the catch in way of retrieving the element from the Queue. Whenever an element is retrieved from the queue element which was inserted first will be fetched first in our case 22 is the element that was inserted first and will be fetched whenever retrieved. Queue has its own set of operations to perform add or removal lets have quick look to that operation.

AddResponsible for inserting element in Queue
PollIt retrieves element which was added first in Queue and also removes it from the Queue
PeekIt retrieves element which was added first in Queue but does not remove it from the Queue.
HeadHead signifies the position from where elements will be removed/retrieved from the Queue
RearRear Signifies the position at which elements will be added to the Queue

We have show example of these operations in above image.

Queue in Java

Java has provided a good implementation of Queue data-structure in its own way using priority queue and ArrayDequeue. Java has provided Queue interface as contract between all classes who want to act as a Queue.

Let’s see now where Queue and its implementations stands in Java Collection.

Queue hierarchy in Java Collection
Queue hierarchy in Java Collection

Queue is an interface from java.util package and act as a contract between all classes that want to act as queue or want to provide an implementation of the Queue Data-Structure. Queue has its actual implementation provided by classes as PriorityQueue and ArrayDequeue.We will discuss about these classes in detail below.

Priority Queue in Java

PriorityQueue implements Queue interface and provides implementation for all its methods.

As we discussed earlier in our post that queue acts on FIFO (First in First Out) architecture and elements are added in order of their insertion but their is a catch in PriorityQueue here elements are inserted in natural ordering of its elements or the ordering as is mentioned by comparator provided while creating the PriorityQueue

Lets see this with example.

private static void printQueue() {
		System.out.println("Creating preority queue");
		Queue<String> queue1 = new PriorityQueue<String>();
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
		queue1.add("Rome");
		queue1.add("Japan");
	
        System.out.println("Elements of priority queue1 : "+queue1);
}

Output of above code

Creating priority queue
Adding elements priority queue1
Elements of priority queue1 : [India, Japan, Japan, Rome, Rome]

Here elements are added in queue in their natural ordering i.e String are sorted in ascending order and when inserted in Queue. Thats why we got the output as

[India, Japan, Japan, Rome, Rome]

And also queue does not allow null value. If null is added it will through null-pointer exception

private static void convertQueueToList() {
		System.out.println("Creating priority queue");
		Queue<String> queue1 = new PriorityQueue<String>();
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
		queue1.add("Rome");
		queue1.add(null);
	
        System.out.println("Elements of priority queue1 : "+queue1);
}

Output of above code

Creating priority queue
Adding elements priority queue1
Exception in thread "main" java.lang.NullPointerException
at java.util.PriorityQueue.offer(PriorityQueue.java:336)
at com.techijournal.collection.TEchijournalQueue.convertQueueToList(TEchijournalQueue.java:211)
at com.techijournal.collection.TEchijournalQueue.main(TEchijournalQueue.java:20)

Methods of PriorityQueue in Java

Priority queue provides multiple methods to interact with Queue.

PriorityQueue Constructor

Priority Queue provides multiple constructor let’s discuss them all

PriorityQueue()Creates a Queue with initial capacity as 11 and elements are ordered in its natural ordering of elements
PriorityQueue(Collection<? Extends E> c)Create a queue from given collection c
PriorityQueue(Comparator<? super E> comparator)Create a queue of initial capacity as 11 and order the elements as per provided comparator
PriorityQueue(int initialCapacity)Creates an Queue with initial capacity and elements are ordered in its natural ordering of elements
PriorityQueue(int initialCapacity, Comparator comparator)Create a queue with provided initalCapacity and order the elements as per provided comparator
PriorityQueue(PriorityQueue<? Extends E> priorityQueue)Creates a new priority queue from given priority queue
PriorityQueue(SortedSet<? Extends E> set)Creates a priority queue from given set queue

Code for creating queue using its constructor

private static void createQueue() {
        System.out.println("Creating priority queue");
		Queue<String> queue1 = new PriorityQueue<String>();
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
		queue1.add("US");
		queue1.add("China");
        System.out.println("Elements of priority queue1 : "+queue1);

        
        System.out.println("Creating preority queue using comparator");
		Queue<String> queue2 = new PriorityQueue<String>((o1,o2)-> o2.compareTo(o1));
		System.out.println("Adding elements priority queue2");
		queue2.add("India");
		queue2.add("Rome");
		queue2.add("Japan");
		queue2.add("US");
		queue2.add("China");
        System.out.println("Elements of priority queue2 : "+queue2);
        
        System.out.println("Creating preority queue using initialcapacity of 5");
		Queue<String> queue3 = new PriorityQueue<String>(5);
		System.out.println("Adding elements priority queue3");
		queue3.add("India");
		queue3.add("Rome");
		queue3.add("Japan");
		queue3.add("US");
		queue3.add("China");
        System.out.println("Elements of priority queue3 : "+queue3);
        
        System.out.println("Creating preority queue using constructor PriorityQueue(initalcapacity,comparator)");
		Queue<String> queue4 = new PriorityQueue<String>(5,(o1,o2)-> o2.compareTo(o1));
		System.out.println("Adding elements priority queue3");
		queue4.add("India");
		queue4.add("Rome");
		queue4.add("Japan");
		queue4.add("US");
		queue4.add("China");
        System.out.println("Elements of priority queue4 : "+queue4);
        
        System.out.println("Creating priority queue using constructor PriorityQueue(PriorityQueue<? Extends E> priorityQueue)");
		Queue<String> queue5 = new PriorityQueue<String>(queue1);
        System.out.println("Elements of priority queue5 : "+queue5);
        
        System.out.println("Creating priority queue using constructor PriorityQueue(Collection<? Extends E> c)");
        List<String> list = new ArrayList<>();
        list.add("CAT");
        list.add("DOG");
        list.add("RAT");
        list.add("GOAT");
		Queue<String> queue6 = new PriorityQueue<String>(list);
        System.out.println("Elements of priority queue6 : "+queue6);
        
	}

Output for above code

Creating priority queue
Adding elements priority queue1
Elements of priority queue1 : [China, India, Japan, US, Rome]
Creating preority queue using comparator
Adding elements priority queue2
Elements of priority queue2 : [US, Rome, Japan, India, China]
Creating preority queue using initialcapacity of 5
Adding elements priority queue3
Elements of priority queue3 : [China, India, Japan, US, Rome]
Creating preority queue using constructor PriorityQueue(initalcapacity,comparator)
Adding elements priority queue3
Elements of priority queue4 : [US, Rome, Japan, India, China]
Creating priority queue using constructor PriorityQueue(PriorityQueue priorityQueue)
Elements of priority queue5 : [China, India, Japan, US, Rome]
Creating priority queue using constructor PriorityQueue(Collection c)
Elements of priority queue6 : [CAT, DOG, RAT, GOAT]

Add Elements to PriorityQueue

PriorityQueue provides add() and offer() methods to add elements into the Queue.

boolean add(E e)boolean offer(E e)
This adds element to queue if its capacity allowsThis also adds element to the queue.
Return true in case addition is successReturn true in case addition is success else false
Throws IllegalStateExceptionexception if addition is failure due to lack of sizeDo not throw exception if it fails to add element to queue

Code for adding element to queue

private static void insertElementintoQueue() {
		System.out.println("Creating preority queue");
		Queue<String> queue1 = new PriorityQueue<String>(5);
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
		queue1.add("US");
		queue1.add("China");
        System.out.println("Elements of priority queue1 : "+queue1);
        
        System.out.println("inserting Element into priority queue1 using add()");
        System.out.println("inserting England to queue1 "+ queue1.add("England"));
        System.out.println("Elements of priority queue1 : "+queue1);

        System.out.println("inserting Element into priority queue1 using offer()");
        System.out.println("inserting Russia to queue1 "+ queue1.add("Russia"));
        System.out.println("Elements of priority queue1 : "+queue1);

	}

Output of above code is

Creating preority queue
Adding elements priority queue1
Elements of priority queue1 : [China, India, Japan, US, Rome]
inserting Element into priority queue1 using add()
inserting England to queue1 true
Elements of priority queue1 : [China, India, England, US, Rome, Japan]
inserting Element into priority queue1 using offer()
inserting Russia to queue1 true
Elements of priority queue1 : [China, India, England, US, Rome, Japan, Russia]

Retrieve or Remove Element from Queue in Java

We can use remove() and poll() provided by Queue interface and implemented by PriorityQueue.

E poll()E remove()
This retrieves and removes the element from head of the QueueThis will retrieves and remove the element from head of the Queue
This return null if queue is emptyThis will throw exception if queue is empty

We can also use clear() to empty the Queue.

Code to illustrate removal of element from PriorityQueue

	private static void removeElementFromQueue() {
		System.out.println("Creating preority queue");
		Queue<String> queue1 = new PriorityQueue<String>();
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
		queue1.add("US");
		queue1.add("China");
        System.out.println("Elements of priority queue1 : "+queue1);
        System.out.println("removing top element from priority queue1 using poll()");
        System.out.println("Removed element from queue1 is : "+queue1.poll());

        System.out.println("queue1 elements after removing: "+ queue1);
        
        System.out.println("removing top element from priority queue1 using remove()");
        System.out.println("Removed element from queue1 is : "+queue1.remove());

        System.out.println("queue1 elements after removing: "+ queue1);
        
        System.out.println("removing all elements from priority queue1 using clear()");
        queue1.clear();
        System.out.println("queue1 elements after removing: "+ queue1);
        
        System.out.println("removing top element from empty priority queue1 using poll()");

        System.out.println("removing top element from priority queue1 using poll()");
        System.out.println("Removed element from queue1 is : "+queue1.poll());

        System.out.println("queue1 elements after removing: "+ queue1);
        
        System.out.println("removing top element from empty priority queue1 using remove()");
        try {
        System.out.println("Removed element from queue1 is : "+queue1.remove());
        } catch (NoSuchElementException e){
        	System.out.println("Exception throw while calling remove() on empty queue is :" +e.getMessage());
        }    

	}

Output for above code

Creating preority queue
Adding elements priority queue1
Elements of priority queue1 : [China, India, Japan, US, Rome]
removing top element from priority queue1 using poll()
Removed element from queue1 is : China
queue1 elements after removing: [India, Rome, Japan, US]
removing top element from priority queue1 using remove()
Removed element from queue1 is : India
queue1 elements after removing: [Japan, Rome, US]
removing all elements from priority queue1 using clear()
queue1 elements after removing: []
removing top element from empty priority queue1 using poll()
removing top element from priority queue1 using poll()
Removed element from queue1 is : null
queue1 elements after removing: []
removing top element from empty priority queue1 using remove()
Exception throw while calling remove() on empty queue is :null

Or we can use peek() method of PriorityQueue class to retrieve element from Queue.

Main difference between peek() and remove() or poll() is that peek() just retrieves the element from the queue but it does not remove it from Queue as is done by poll() or remove().

Just check the code below

private static void retriveElementFromQueue() {
		System.out.println("Creating preority queue");
		Queue<String> queue1 = new PriorityQueue<String>(5);
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
	
        System.out.println("Elements of priority queue1 : "+queue1);
        
        System.out.println("Retreving top Element from priority queue1 using peek()");
        System.out.println("Element retrieved from queue1 "+ queue1.peek());
        System.out.println("Elements of priority queue1 : "+queue1);

	}

Output of the above code is

Creating preority queue
Adding elements priority queue1
Elements of priority queue1 : [India, Rome, Japan]
Retreving top Element from priority queue1 using peek()
Element retrieved from queue1 India
Elements of priority queue1 : [India, Rome, Japan]

Search Element in Queue

PriorityQueue or say Queue interface provides with contains() to search elements from the Queue. contains() method is not separately provided by Queue Interface or PriorityQueue Class but it comes from the Collection interface. It returns true if element is found in queue else false

E contains(E object)Return true if element is found else return false

Code for searching the element in Queue.

private static void searchingElementInQueue() {
		System.out.println("Creating preority queue");
		Queue<String> queue1 = new PriorityQueue<String>(5);
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
		queue1.add("England");
		queue1.add("Russia");
	
        System.out.println("Elements of priority queue1 : "+queue1);
        
        System.out.println("Searching Element in priority queue1 using contains()");
        System.out.println("Is Rome present in queue "+queue1.contains("Rome"));
        

	}

Output

Creating preority queue
Adding elements priority queue1
Elements of priority queue1 : [England, India, Japan, Rome, Russia]
Searching Element in priority queue1 using contains()
Is Rome present in queue true

Iterating Over PriorityQueue

PriorityQueue or Queue provides us with iterator() and splitIterator() to perform iteration. Let’s check the code below.

	private static void IteratingOverElementOfQueue() {
		System.out.println("Creating preority queue");
		Queue<String> queue1 = new PriorityQueue<String>(5);
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
		queue1.add("Rome");
		queue1.add("Japan");
	
        System.out.println("Elements of priority queue1 : "+queue1);
        
        System.out.println("Iterating over  Elements of priority queue1 using Iterator()");
        System.out.println("Elements are ");
        Iterator<String> iterator = queue1.iterator();
        while(iterator.hasNext()) {
        System.out.println(iterator.next());
        }
	}

Output for above code is

Creating preority queue
Adding elements priority queue1
Elements of priority queue1 : [India, Japan, Japan, Rome, Rome]
Iterating over Elements of priority queue1 using Iterator()
Elements are
India
Japan
Japan
Rome
Rome

Getting Size of PriorityQueue

PriorityQueue gets size() method from collection interface which provides the size of the queue.

int size()Return size of the Queue
private static void sizefQueue() {
		System.out.println("Creating preority queue");
		Queue<String> queue1 = new PriorityQueue<String>(5);
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
		queue1.add("England");
		queue1.add("Russia");
	
        System.out.println("Elements of priority queue1 : "+queue1);
        
        System.out.println("Qetting size of priority queue1 using size()");
        System.out.println("Size of the queue "+queue1.size());
        

	}

Output for above code is

Creating preority queue
Adding elements priority queue1
Elements of priority queue1 : [England, India, Japan, Rome, Russia]
Qetting size of priority queue1 using size()
Size of the queue 5

Converting Queue to Array

PriorityQueue class provides toArray() which helps to convert queue to Array.

Object toArray()Converts Queue to Array of the Object type.
<T> T[] toArray(T[] a)It returns given Array a with queue elements
private static void convertingQueueToArray() {
		System.out.println("Creating preority queue");
		Queue<String> queue1 = new PriorityQueue<String>(5);
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
		queue1.add("Rome");
		queue1.add("Japan");
	
        System.out.println("Elements of priority queue1 : "+queue1);
        
        System.out.println("Converting queue  to Array using toArray()");
        Object [] array = queue1.toArray();
        
        String [] strArray = new String[10];
        strArray = queue1.toArray(strArray);        

	}
Creating preority queue
Adding elements priority queue1
Elements of priority queue1 : [India, Japan, Japan, Rome, Rome]
Converting queue to Array using toArray()

Converting Queue to List

There is no specific method to convert Queue to List provided by PriorityQueue class. For conerting Queue to List we can use constructor of ArrayList that accepts Collection. As shown below.

private static void convertQueueToList() {
		System.out.println("Creating priority queue");
		Queue<String> queue1 = new PriorityQueue<String>(5);
		System.out.println("Adding elements priority queue1");
		queue1.add("India");
		queue1.add("Rome");
		queue1.add("Japan");
		queue1.add("Rome");
	
        System.out.println("Elements of priority queue1 : "+queue1);
        
        System.out.println("Converting queue  to List using toArray()");
        
        List<String> list = new ArrayList<>(queue1);
        System.out.println("Transformed list from queue is " + list);
	}
	

Output for above code is

Creating priority queue
Adding elements priority queue1
Elements of priority queue1 : [India, Rome, Japan, Rome]
Converting queue to List using toArray()
Transformed list from queue is [India, Rome, Japan, Rome]

Conclusion

In this post, we all learned about how Queue works at a basic level and basic Queue related operations.

AddResponsible for inserting element in Queue
PollIt retrieves element which was added first in Queue and also removes it from the Queue
PeekIt retrieves element which was added first in Queue but does not remove it from the Queue.
HeadHead signifies the position from where elements will be removed/retrieved from the Queue
RearRear Signifies the position at which elements will be added to the Queue

Also we learned about PriorityQueue and its methods with code examples.

Thank’s Note

Thanks for spending your valuable time reading this post. Hope this post taught you something new today. Please share the post if you like it.

Durgesh Kumar

He is the Founder of TechiJournal.com. And have 4+ years of experience as full-stack Java developer. He worked with many reputed product companies and would like to share his experience and knowledge through this blog. He works very hard to provide you with quality content. But as no one is perfect, If you feel that some improvement can be made then feel free to add it in the comment section. We look forward to it.

Leave a Reply