Learn to use Queue in Java Collections Framework


Reading time: 30 minutes | Coding time: 10 minutes

In this article, we will take a look at how to use the Queue class in Java Collections library. This is useful as one can directly use queue without natively implementing it which can significantly boost implementation speed. At the same time, Java's Queue implementation is efficient in terms of performance.

Before going into using Java's Queue, you may want to understand the basics of Queue as a data structure. It is a widely used data structure and it is recommended that you go through the basics:

Understand the basics of Queue data structure in general

Introduction

The Queue interface extends Collection and declares the behavior of a queue, which is often a First-in, First-out list. It is mainly used for holding elements prior to processing.

Properties

  • It is an ordered list of elements
  • Elements can only be removed from the head of the Queue
  • Every Queue implementation must specify its ordering properties.
  • Queues may be bounded i.e. impose a restriction on the number of elements that can be added to the Queue.
  • The LinkedList implementation of the Queue (demonstrated below) allows null values to be inserted in the Queue.
Queue<String> q = new LinkedList<>; //recommended way

Applications

Some important applications of Queue are as follows:

  • It is used for disk scheduling in an Operating System
  • It is used in Breadth First Search of a Graph

Methods

Insertion

Insertion in a queue can only be done at the end of the queue. The following methods can be used -

  1. boolean add(E e) - Inserts the specified element e into the queue if it is possible to do so.
  2. boolean addAll(Collection<? extends E> c) - Adds all of the elements in the specified collection to this collection.
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
q1.add(1); //q1 = [1]
q1.add(2); //q1 = [1, 2]
q1.add(3); //q1 = [1, 2, 3]
q2.addAll(q1); //q2 = [1, 2, 3]

Deletion

The following methods can invariably be used to make deletions -

  1. void clear() - Removes all of the elements from queue
  2. E poll() - Retrieves and removes the head of this queue, or returns null if this queue is empty.
  3. E remove() - Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.
  4. boolean remove(Object o) - Removes a single instance of the specified element from this collection, if it is present
  5. boolean removeAll(Collection<?> c) - Removes all of this collection's elements that are also contained in the specified collection.
  6. boolean retainAll(Collection<?> c) - Retains only the elements in this collection that are contained in the specified collection
System.out.println("First element = " + q1.poll()); //First element = 1
q1.remove(2); //q1 = [3]
q2.removeAll(q1); //q2 = [1, 2]
System.out.println("First element = " + q2.remove()); //First element = 1
q1.clear(); //q1 = []
q2.retainAll(q1); //q2 = []

Traversal

Traversal through the elements of a queue can be done by the following two methods -

  1. Iterator iterator() - Returns an iterator over the elements in this collection. There are no guarantees concerning the order in which the elements are returned (unless this collection is an instance of some class that provides a guarantee)
for(Integer item: q1) {
    System.out.println(item);
}

Iterator<Integer> itr = q1.iterator();
while(itr.hasNext()) {
    System.out.println(itr.next());
}

Other Operations

  1. boolean contains(Object o) - Returns true if the queue contains the specified element.
  2. boolean containsAll(Collection<?> c) - Returns true if this collection contains all of the elements in the specified collection.
if(q1.contains(2)) {
    System.out.println("True");
}

if(!q2.containsAll(q1)) {
    System.out.println("False");
}

Question

Can any element apart from the head be removed from a queue?

Yes
No
Depends on contents
Maybe
boolean remove(Object o) - Removes a single instance of the specified element from this collection, if it is present

Implementation

Shown here is another example of the implementation of the queue. The following additional methods have been demonstrated -

  1. E peek() - Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
  2. E element() - Retrieves, but does not remove, the head of this queue. This method differs from peek only in that it throws an exception if this queue is empty.
  3. int size() - Returns the number of elements in this collection
  4. boolean equals(Object o) - Compares the specified object with the queue for equality.
  5. int hashCode() - Returns the hash code value for this collection.
  6. boolean isEmpty() - Returns true if this collection contains no elements.
  7. Object[] toArray() - Returns an array containing all of the elements in this collection
  8. public String toString() - Returns a string representation of the object.
    import java.util.LinkedList; 
    import java.util.Queue; 
    public class QueueExample 
    { 
      public static void main(String[] args) 
      { 
        Queue<Integer> q = new LinkedList&lt;&gt;(); 
        for (int i = 0; i < 10; i+= 2) 
            q.add(i);
        //q = [0, 2, 4, 6, 8]
        System.out.println("Elements of queue - " + q); 
        System.out.println("First element = " + q.peek()); //First element = 0
        System.out.println("Size of queue = " + q.size()); //Size of queue = 5
        System.out.println("Removed element = " + q.remove()); //Removed element = 0
        System.out.println("Elements of queue - " + q);
        //q = [2, 4, 6, 8]
        q.remove(4); //q = [2, 6, 8]
        System.out.println("First element = " + q.element()); //First element = 2
        int a = q.hashCode();
	    System.out.println(a);    
	    if(!q.isEmpty())
	        System.out.println("Queue is not empty");
        System.out.println(q.toString()); //[2, 6, 8]
        Object[] obj = q.toArray();
        System.out.print("Printing elements from first to last:"); //Display the contents of the array
        for (Object value : obj) {
            System.out.print(value + " ");
      } //Printing elements from first to last: 2 6 8
    }