Circular Queue Implementation in Java | CodeUsingJava








Circular Queue Implementation in Java

In this tutorial, we will learn about Circular Queues and their implementation.

Introduction

A Circular Queue is a linear data structure based on the First In First Out (FIFO) principle, wherein the last element is joined to the first element to create a circle. Also known as Ring Buffer, Circular Queues were introduced to overcome a queue's limitation of not being able to utilize the vacant spaces left in the beginning once the rear reaches its end position.

Why Use Circular Queues Over Regular Queues

When working with a normal queue, elements can be inserted into the queue till it becomes full. Once that limit is reached, no further additions can take place even if there is a vacancy in the front of the queue. To utilize that vacancy in a regular queue, we would have to shift all elements ahead to insert an additional element in the rear. This situation can be averted by using a Circular Queue where we can insert FIFO data until the queue reaches its maximum capacity. This is explained below.
  • Here we have a regular queue with one element which will act as both the Front and Rear.
    Regular Queue Example
  • Let us fill up the queue with random elements to utilise its maximum space. The front and rear elements are as shown.
    Regular Queue Filled
  • Once we delete an element from the front end, it can be seen that the newly created vacancy is not accessible easily because new elements can only be added from the rear end.
    Regular Queue Deletion
  • To fill up the front vacancy, we need to shift all elements ahead and then add the new element from the rear. This is where Circular Queues prove to be useful.
    Regular Queue Shifting

Circular Queue Operations

  1. Front: obtain the front element of the Circular Queue.
  2. Rear: obtain the rear element of the Circular Queue.
  3. enQueue(item): insert a new value in the Circular Queue. The insertion is always done at the rear.
  4. deQueue(): delete an element from the Circular Queue. The deletion is always done from the front.
Consider a Circular Queue as shown below. The front and rear have been marked and there is excess space in the end that we will fill up.
Circular Queue Example
The integer '4' is added to the rear by performing enQueue(4).
Circular Queue enQueue 1
The integer '5' is added to the rear by performing enQueue(5).
Circular Queue enQueue 2
We will now perform the deQueue() operation. Here, the deletion happens from the front end.
Circular Queue deQueue
To insert a new element in a Circular Queue, we will not be needing to shift the elements as we did with the regular queue. We simply need to change the pointer's position and the new element will be added from the rear end as shown.
Circular Queue enQueue 3

Circular Queue Implementation

// Java program for Operations on Circular Queue
import java.util.ArrayList;

class Circular_Queue{

private int size, front, rear; //Variable declaration


private ArrayList<Integer> circular_queue = new ArrayList<Integer>(); //Declaring Integer array list

Circular_Queue(int queue_size) //Constructor
{
	this.size = queue_size;
	this.front = this.rear = -1;
}

public void enQueue(int queue_data) //Insertion Function
{
	if((front == 0 && rear == size - 1) ||
	(rear == (front - 1) % (size - 1))) // Condition if queue is full
	{
		System.out.print("Queue Full!");
	}

	else if(front == -1) // Condition for empty queue.
	{
		front = 0;
		rear = 0;
		circular_queue.add(rear, queue_data);
	}
	else if(rear == size - 1 && front != 0)
	{
		rear = 0;
		circular_queue.set(rear, queue_data);
	}
	else
	{
		rear = (rear + 1);
		// Adding a new element if
		if(front <= rear)
		{
			circular_queue.add(rear, queue_data);
		}
		// Else updating old value
		else
		{
			circular_queue.set(rear, queue_data);
		}
	}
}

public int deQueue() //Dequeue Function
{
	int temp;

	if(front == -1) //Checking for empty queue
	{
		System.out.print("Queue Empty!");
		return -1;
	}

	temp = circular_queue.get(front);

	if(front == rear) // For only one element
	{
		front = -1;
		rear = -1;
	}

	else if(front == size - 1)
	{
		front = 0;
	}
	else
	{
		front = front + 1;
	}
	return temp; // Returns dequeued element
}


public void displayQueue() // Display the elements of queue
{
	if(front == -1) // Check for empty queue
	{
		System.out.print("Queue is Empty");
		return;
	}
	System.out.print("Elements in the " +
					"circular queue are: ");

	if(rear >= front) //if rear has not crossed the size limit 
	{
		for(int i = front; i <= rear; i++) //print elements using loop
		{
			System.out.print(circular_queue.get(i));
			System.out.print(" ");
		}
		System.out.println();
	}

	else
	{
		for(int i = front; i < size; i++)
		{
			System.out.print(circular_queue.get(i));
			System.out.print(" ");
		}
		for(int i = 0; i <= rear; i++) // Loop for printing elements from 0th index till rear position
		{
			System.out.print(circular_queue.get(i));
			System.out.print(" ");
		}
		System.out.println();
	}
}

// Driver code
public static void main(String[] args)
{
	Circular_Queue queue = new Circular_Queue(5); // Initialising new object of CircularQueue class.
	
	queue.enQueue(1);
	queue.enQueue(2);
	queue.enQueue(3);
	queue.enQueue(4);
	
	queue.displayQueue();

	int x = queue.deQueue();

	if(x != -1) // Check for empty queue
	{
		System.out.print("Deleted value = ");
		System.out.println(x);
	}
	x = queue.deQueue();
        
	if(x != -1) // Check for empty queue
	{
		System.out.print("Deleted value = ");
		System.out.println(x);
	}

	queue.displayQueue();
	
	queue.enQueue(5);
	queue.enQueue(6);
	queue.enQueue(7);
	
	queue.displayQueue();
	
	queue.enQueue(8);
}
}


If we now run the application we get the output as follows-
Circular Queue Output