Java Queue – Queue Methods, Queue Implementation With Examples

In this Tutorial, we will discuss What is a Queue in Java, How to use it, Java Queue Example, Java Queue Methods & Queue Interface Implementation:

A queue is a linear data structure or a collection in Java that stores elements in a FIFO (First In, First Out) order.

The queue collection has two ends i.e. front & rear. The elements are added at the rear and removed from the front.

=> Visit Here To See The Java Training Series For All.

What Is A Java Queue?

A queue data structure is represented as shown below:

As shown in the above diagram, a queue is a structure having two points i.e. start (front) and end (rear). Elements are inserted into the queue at the rear end and removed from the queue at the front.

In Java, Queue is an interface that is a part of java.util package. The queue interface extends the Java Collection interface.

The general definition of the Queue interface is:

public interface Queue<E> extends Collection<E>

As the Queue is an interface, it cannot be instantiated. We need some concrete classes to implement the functionality of the Queue interface. Two classes implement the Queue interface i.e. LinkedList and PriorityQueue.

Following are some of the major characteristics of the Queue data structure:

• Queue follows the FIFO (First In, First Out) order. This means that the element is inserted in the queue at the end and removed from the queue at the beginning.
• The Java queue interface provides all the methods of Collection interface like insertion, deletion, etc.
• LinkedList and PriorityQueue are the classes that implement the Queue interface. ArrayBlockingQueue is yet another class that implements the Queue interface.
• The Queues that are a part of the java.util package can be classified as unbounded queues while those present in java.util.the concurrent package is bounded queues.
• The Deque is a queue that supports insertion and deletion from both the ends.
• The deque is thread-safe.
• BlockingQueues are thread-safe and are used to implement producer-consumer problems.
• BlockingQueues do not allow null elements. A NullPointerException is thrown if any operation related to null values is attempted.

How To Use A Queue In Java?

To use a queue in Java, we must first import the queue interface as follows:

import java.util.queue;

Or

import java.util.*;

Once this is imported, we can create a queue as shown below:

Queue<String> str_queue = new LinkedList<> ();

As Queue is an interface, we use a LinkedList class that implements the Queue interface to create a queue object.

Similarly, we can create a queue with other concrete classes.

Queue<String> str_pqueue = new PriorityQueue<> ();
Queue<Integer> int_queue = new ArrayDeque<> ();

Now that the queue object is created, we can initialize the queue object by providing the values to it through the add method as shown below.

str_queue.add(“one”);
str_queue.add(“two”);
str_queue.add(“three”);

Java Queue Example

import java.util.*;

public class Main {
   public static void main(String[] args) {
	//declare a Queue	
	Queue<String> str_queue = new LinkedList<>();
    //initialize the queue with values
	str_queue.add("one");
	str_queue.add("two");
	str_queue.add("three");
	str_queue.add("four");
	//print the Queue
	System.out.println("The Queue contents:" + str_queue);
    }
}

Output:

The Queue contents:[one, two, three, four]

The above example shows the declaration and initialization of a Queue object. Then, we just print the contents of the queue.

Queue Methods In Java

In this section, we will discuss the methods of API for the queue. Queue interface supports various operations like insert, delete, peek, etc. Some operations raise an exception while some return a specific value when the method succeeds or fails.

Note that there are no specific changes to the Queue collection in Java 8. The below methods are also available in later versions of Java like Java 9, etc.

The below table summarizes all these methods.

Iterating The Queue Elements

We can traverse the queue elements either using the forEach loop or using an iterator. The program given below implements both the approaches to traverse the Queue.

import java.util.*;
public class Main {
   public static void main(String[] args) {
     //declare a Queue	
    Queue LL_queue = new LinkedList();
    //initialize the Queue
    LL_queue.add("Value-0");
    LL_queue.add("Value-1");
    LL_queue.add("Value-2");
    LL_queue.add("Value-3");
    //traverse the Queue using Iterator
    System.out.println("The Queue elements through iterator:");
    Iterator iterator = LL_queue.iterator();
    while(iterator.hasNext()){
        String element = (String) iterator.next();
        System.out.print(element + " ");
    }
    System.out.println("\n\nThe Queue elements using for loop:");
    //use new for loop to traverse the Queue
    for(Object object : LL_queue) {
        String element = (String) object;
        System.out.print(element + " ");
    }
    }
}

Output:

The Queue elements through iterator:
Value-0 Value-1 Value-2 Value-3
The Queue elements using for loop:
Value-0 Value-1 Value-2 Value-3

Java Queue Implementation

The program below demonstrates the methods that we discussed above.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Queue<Integer> q1 = new LinkedList<Integer>();
        //Add elements to the Queue
        q1.add(10);
        q1.add(20);
        q1.add(30);
        q1.add(40);
        q1.add(50);
        System.out.println("Elements in Queue:"+q1);
        //remove () method =>removes first element from the queue
        System.out.println("Element removed from the queue: "+q1.remove());
        //element() => returns head of the queue
        System.out.println("Head of the queue: "+q1.element());
        //poll () => removes and returns the head
        System.out.println("Poll():Returned Head of the queue: "+q1.poll());
        //returns head of the queue
        System.out.println("peek():Head of the queue: "+q1.peek());
        //print the contents of the Queue
        System.out.println("Final Queue:"+q1);
    }
}

Output:

Elements in Queue:[10, 20, 30, 40, 50]
Element removed from the queue: 10
Head of the queue: 20
Poll():Returned Head of the queue: 20
peek():Head of the queue: 30
Final Queue:[30, 40, 50]

Java Queue Array Implementation

Queue implementation is not as straightforward as a stack implementation. First of all, the queue contains two pointers, rear, and front. Also, different operations are done at two different ends.

To implement queue using Arrays, we first declare an array that will hold n number of queue elements.

Then we define the following operations to be performed in this queue.

#1) Enqueue: An operation to insert an element in the queue is Enqueue (function queueEnqueue in the program). For inserting an element at the rear end, we need to first check if the queue is full. If it is full, then we cannot insert the element. If rear < n, then we insert the element in the queue.

#2) Dequeue: The operation to delete an element from the queue is Dequeue (function queueDequeue in the program). First, we check whether the queue is empty. For dequeue operation to work, there has to be at least one element in the queue.

#3) Front: This method returns the front of the queue.

#4) Display: This method traverses the queue and displays the elements of the queue.

The following Java program demonstrates the Array implementation of Queue.

class Queue { 
    private static int front, rear, capacity; 
    private static int queue[]; 
  
    Queue(int size) { 
        front = rear = 0; 
        capacity = size; 
        queue = new int[capacity]; 
    } 
  
    // insert an element into the queue
    static void queueEnqueue(int item)  { 
        // check if the queue is full
        if (capacity == rear) { 
            System.out.printf("\nQueue is full\n"); 
            return; 
        } 
  
        // insert element at the rear 
        else { 
            queue[rear] = item; 
            rear++; 
        } 
        return; 
    } 
  
    //remove an element from the queue
    static void queueDequeue()  { 
        // check if queue is empty 
        if (front == rear) { 
            System.out.printf("\nQueue is empty\n"); 
            return; 
        } 
  
        // shift elements to the right by one place uptil rear 
        else { 
            for (int i = 0; i < rear - 1; i++) { 
                queue[i] = queue[i + 1]; 
            } 
  
      
      // set queue[rear] to 0
            if (rear < capacity) 
                queue[rear] = 0; 
  
            // decrement rear 
            rear--; 
        } 
        return; 
    } 
  
    // print queue elements 
    static void queueDisplay() 
    { 
        int i; 
        if (front == rear) { 
            System.out.printf("Queue is Empty\n"); 
            return; 
        } 
  
        // traverse front to rear and print elements 
        for (i = front; i < rear; i++) { 
            System.out.printf(" %d = ", queue[i]); 
        } 
        return; 
    } 
  
    // print front of queue 
    static void queueFront() 
    { 
        if (front == rear) { 
            System.out.printf("Queue is Empty\n"); 
            return; 
        } 
        System.out.printf("\nFront Element of the queue: %d", queue[front]); 
        return; 
    } 
} 

public class Main {
    public static void main(String[] args) { 
        // Create a queue of capacity 4 
        Queue q = new Queue(4); 
  
        System.out.println("Initial Queue:");
       // print Queue elements 
        q.queueDisplay(); 
  
        // inserting elements in the queue 
        q.queueEnqueue(10); 
        q.queueEnqueue(30); 
        q.queueEnqueue(50); 
        q.queueEnqueue(70); 
  
        // print Queue elements 
        System.out.println("Queue after Enqueue Operation:");
        q.queueDisplay(); 
  
        // print front of the queue 
        q.queueFront(); 
        
        // insert element in the queue 
        q.queueEnqueue(90); 
  
        // print Queue elements 
        q.queueDisplay(); 
  
        q.queueDequeue(); 
        q.queueDequeue(); 
        System.out.printf("\nQueue after two dequeue operations:"); 
  
        // print Queue elements 
        q.queueDisplay(); 
  
        // print front of the queue 
        q.queueFront(); 
    } 
}

Output:

Initial Queue:
Queue is Empty
Queue after Enqueue Operation:
10 = 30 = 50 = 70 =
Front Element of the queue: 10
Queue is full
10 = 30 = 50 = 70 =
Queue after two dequeue operations: 50 = 70 =
Front Element of the queue: 50

Java Queue Linked List Implementation

As we have implemented the Queue data structure using Arrays in the above program, we can also implement the Queue using Linked List.

We will implement the same methods enqueue, dequeue, front, and display in this program. The difference is that we will be using the Linked List data structure instead of Array.

The below program demonstrates the Linked List implementation of Queue in Java.

class LinkedListQueue
{
 private Node front, rear; 
 private int queueSize; // queue size 
 
 //linked list node
 private class Node { 
 int data;
 Node next;
 }
 
 //default constructor - initially front & rear are null; size=0; queue is empty
 public LinkedListQueue()
 {
 front = null;
 rear = null;
 queueSize = 0;
 }


//check if the queue is empty
 public boolean isEmpty()
 {
 return (queueSize == 0);
 }
 
 //Remove item from the front of the queue.
 public int dequeue()
 {
 int data = front.data;
 front = front.next;
 if (isEmpty()) 
 {
 rear = null;
 }
 queueSize--;
 System.out.println("Element " + data+ " removed from the queue");
 return data;
 }
 
 //Add data at the rear of the queue.
 public void enqueue(int data)
 {
 Node oldRear = rear;
 rear = new Node();
 rear.data = data;
 rear.next = null;
 if (isEmpty()) 
 {
 front = rear;
 }
 else  {
 oldRear.next = rear;
 }
 queueSize++;
 System.out.println("Element " + data+ " added to the queue");
 }
 //print front and rear of the queue
 public void print_frontRear() {
     System.out.println("Front of the queue:" + front.data 
     + " Rear of the queue:" + rear.data);
 }
}
class Main{
 public static void main(String a[]){
 
 LinkedListQueue queue = new LinkedListQueue();

 queue.enqueue(6);
 queue.enqueue(3);
 queue.print_frontRear();
 queue.enqueue(12);
 queue.enqueue(24);
 queue.dequeue();
 queue.dequeue();
 queue.enqueue(9);

 queue.print_frontRear();
 }
}

Output:

Element 6 added to the queue
Element 3 added to the queue
Front of the queue:6 Rear of the queue:3
Element 12 added to the queue
Element 24 added to the queue
Element 6 removed from the queue
Element 3 removed from the queue
Element 9 added to the queue
Front of the queue:12 Rear of the queue:9

BlockingQueue In Java

BlockingQueue is an Interface added in Java 1.5 and is a part of the java.util.concurrent package. This interface introduces blocking in case the BlockingQueue is full or empty.

Thus when a thread accesses the queue and tries to insert (enqueue) elements in a queue that is already full is blocked till another thread creates a space in the queue (maybe by dequeue operation or clearing queue).

Similarly, in the case of dequeuing, the operation is blocked if the queue is empty until the element becomes available for the dequeue operation.

The BlockingQueue methods use some form of concurrency control like internal locks and are atomic. The BlockingQueue is a concurrent queue that manages the queue operations concurrently.

The BlockingQueue is shown below:

Note that BlockingQueue does not accept null values. An attempt to insert a null value in the queue results in NullPointerException.

Some of the BlockingQueue implementations provided in Java are LinkedBlockingQueue, PriorityBlockingQueue, ArrayBlockingQueue, and SynchonousQueue. All these implementations are thread-safe.

BlockingQueue Types

BlockingQueues are of two types:

Bounded Queue

In the bounded queue, the capacity of the queue is passed to the constructor of the queue.

The queue declaration is as follows:

BlockingQueue blockingQueue = new LinkedBlockingDeque (5);

Unbounded Queue

In the unbounded queue, we don’t set the capacity of the queue explicitly and it can grow in size. The capacity is set to Integer.MAX_VALUE.

The declaration of the unbounded queue is as follows:

BlockingQueue blockingQueue = new LinkedBlockingDeque ();

The BlockingQueue interface is primarily used for producer-consumer types of problems wherein producer produces the resources and consumer consumes the resources.

Frequently Asked Questions

Q #1) What is a Queue in Java?

Answer: Queue in Java is a linear ordered data structure that follows FIFO (First In, First Out) ordering of elements. This means that the element inserted first in the queue will be the first element to be removed. In Java, the queue is implemented as an interface that inherits the Collection interface.

Q #2) Is a Queue thread-safe Java?

Answer: Not all queues are thread-safe but BlockingQueues in Java are thread-safe.

Q #3) Which is faster – Stack or Queue?

Answer: The stack is faster. In stack, the elements are processed from one end only, hence no shifting is required. But in the queue, the elements need to be shifted and adjusted as there are two different pointers to insert and delete elements.

Q #4) What are the Types of the Queue?

Answer: The queues are of the following types:

• Simple queue
• Circular queue
• Priority queue
• Double-ended queue

Q #5) Why is the Queue used?

Answer: The queue data structure is used for synchronization purposes. The queue is also used for disk and CPU scheduling.

Conclusion

In this tutorial, we have discussed the simple queues along with their details like declarations, initialization implementation, and methods. We also learned about the Array and LinkedList implementation of Queue in Java.

In our upcoming tutorials, we will discuss more types of queues in detail.

=> Check ALL Java Tutorials Here.