Circular Queue

In a normal Queue Data Structure, we can insert elements until queue becomes full. But once if queue becomes full, we can not insert the next element until all the elements are deleted from the queue. For example consider the queue below…

After inserting all the elements into the queue.

Now consider the following situation after deleting three elements from the queue…

This situation also says that Queue is Full and we can not insert the new element because, ‘rear‘ is still at last position. In above situation, even though we have empty positions in the queue we can not make use of them to insert new element. This is the major problem in normal queue data structure. To overcome this problem we use circular queue data structure.

What is Circular Queue?

A Circular Queue can be defined as follows…

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.

Graphical representation of a circular queue is as follows…

import java.util.*;
public class CircularQueue
{
    static Scanner sc = new Scanner(System.in);
    int cq[], size, front, rear;
    CircularQueue(int size)
    {
        this.size = size;   //Storing the size in the instance variable
        cq = new int[size]; //Allocating memory
        front = rear = -1;  //initial condition for an empty queue
    }

    void push()
    {
        if((rear+1)%size==front)    //Checking if queue is full
        {
            System.out.println("Queue is full.");
            return;
        }
        int x;
        System.out.println("Enter the value to insert: ");
        x = sc.nextInt();
        if(front == -1) //If queue is initially empty
            front = 0;
        rear = (rear+1)%size;
        cq[rear] = x;
    }

    void pop()
    {
        if(front==-1)       //If the queue is empty
        {
            System.out.println("Queue is empty");
            return;
        }
        if(front==rear) //When there is only one value in the queue
        {
            System.out.println("The deleted value is: "+cq[front]);
            front = rear = -1;
            return;
        }
        System.out.println("The deleted value is: "+cq[front]);
        front = (front+1)%size;
    }

    void display()
    {
        if(front == -1)
        {
            System.out.println("Queue is empty");
            return;
        }
        int i = front;
        System.out.println("The values in the queue are: ");
        while(i!=rear)
        {
            System.out.println(cq[i]);
            i = (i+1)%size;
        }
        System.out.println(cq[rear]); 
        /*As the last value will not be printed in the above loop*/
        
    }

    public static void main()
    {
        int ch, s;
        System.out.print("Enter the size of the queue: ");
        s = sc.nextInt();   //Input Queue Size
        CircularQueue obj = new CircularQueue(s);//creating object
        do  //Running do while loop
        {
            System.out.println("MENU");
            System.out.println("1. Enter a value in the queue. ");
            System.out.println("2. Delete a value from the queue. ");
            System.out.println("3. Display the values in the queue. ");
            System.out.println("4. Exit. ");
            System.out.print("Enter your choice: ");
            ch = sc.nextInt();
            switch(ch)
            {
                case 1:
                obj.push();
                break;
                case 2:
                obj.pop();
                break;
                case 3:
                obj.display();
                break;
                case 4:
                System.out.println("Exitting the program. Thank you.");
                break;
                default:
                System.out.println("Wrong Input.");
            }//end of switch
        }while(ch!=4);
    }
}