Queue Implementation in Java

This article covers queue implementation in Java. A queue is a linear data structure that follows the FIFO (First–In, First–Out) principle. That means the object inserted first will be the first one out, followed by the object inserted next.

The queue supports the following core operations:

Enqueue: Inserts an item at the rear of the queue.
Dequeue: Removes the object from the front of the queue and returns it, thereby decrementing queue size by one.
Peek: Returns the object at the front of the queue without removing it.
IsEmpty: Tests if the queue is empty or not.
Size: Returns the total number of elements present in the queue.

Practice this problem

Queue Implementation using an array:

100

101

102

103

104

105

106

107

108

109

110

111

112

// A class to represent a queue

class Queue

{

private int[] arr; // array to store queue elements

private int front; // front points to the front element in the queue

private int rear; // rear points to the last element in the queue

private int capacity; // maximum capacity of the queue

private int count; // current size of the queue

// Constructor to initialize a queue

Queue(int size)

{

arr = new int[size];

capacity = size;

front = 0;

rear = -1;

count = 0;

}

// Utility function to dequeue the front element

public int dequeue()

{

// check for queue underflow

if (isEmpty())

{

System.out.println("Underflow\nProgram Terminated");

System.exit(-1);

}

int x = arr[front];

System.out.println("Removing " + x);

front = (front + 1) % capacity;

count--;

return x;

}

// Utility function to add an item to the queue

public void enqueue(int item)

{

// check for queue overflow

if (isFull())

{

System.out.println("Overflow\nProgram Terminated");

System.exit(-1);

}

System.out.println("Inserting " + item);

rear = (rear + 1) % capacity;

arr[rear] = item;

count++;

}

// Utility function to return the front element of the queue

public int peek()

{

if (isEmpty())

{

System.out.println("Underflow\nProgram Terminated");

System.exit(-1);

}

return arr[front];

}

// Utility function to return the size of the queue

public int size() {

return count;

}

// Utility function to check if the queue is empty or not

public boolean isEmpty() {

return (size() == 0);

}

// Utility function to check if the queue is full or not

public boolean isFull() {

return (size() == capacity);

}

class Main

{

public static void main (String[] args)

{

// create a queue of capacity 5

Queue q = new Queue(5);

q.enqueue(1);

q.enqueue(2);

q.enqueue(3);

System.out.println("The front element is " + q.peek());

q.dequeue();

System.out.println("The front element is " + q.peek());

System.out.println("The queue size is " + q.size());

q.dequeue();

if (q.isEmpty()) {

System.out.println("The queue is empty");

}

else {

System.out.println("The queue is not empty");

}

Download Run Code

Output:

Inserting 1
Inserting 2
Inserting 3
The front element is 1
Removing 1
The front element is 2
The queue size is 2
Removing 2
Removing 3
The queue is empty

The time complexity of enqueue(), dequeue(), peek(), isEmpty() and size() functions is constant, i.e., O(1).

Using Queue Interface:

Java’s library also contains Queue interface that specifies queue operations. Following is an example of the Queue interface using the LinkedList class:

import java.util.LinkedList;

import java.util.Queue;

class Main

{

public static void main(String[] args)

{

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

queue.add("A"); // Insert `A` into the queue

queue.add("B"); // Insert `B` into the queue

queue.add("C"); // Insert `C` into the queue

queue.add("D"); // Insert `D` into the queue

// Prints the front of the queue (`A`)

System.out.println("The front element is " + queue.peek());

queue.remove(); // removing the front element (`A`)

queue.remove(); // removing the front element (`B`)

// Prints the front of the queue (`C`)

System.out.println("The front element is " + queue.peek());

// Returns the total number of elements present in the queue

System.out.println("The queue size is " + queue.size());

// check if the queue is empty

if (queue.isEmpty()) {

System.out.println("The queue is empty");

}

else {

System.out.println("The queue is not empty");

}

Download Run Code

Output:

The front element is A
The front element is C
The queue size is 2
The queue is not empty

Also See:

Circular Queue implementation in C

Queue Implementation in C++

Queue Implementation in Python

Queue Implementation using a Linked List – C, Java, and Python