Circular Queue Data Structure

Circular Queue Data Structure

Circular Queue data structure is a linear data structure in which operation 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.

Operations on Circular Queue

The following are the operations are performed on circular queue:

• Front: Front is used to acheive the front element from the Queue.
• Rear: Rear is used to achieve the rear element from the Queue.
• enQueue(value): enQueue function is used to insert the new value in the Queue. 
• deQueue(): deQueue function deletes an element from the Queue.

Program for circular queue in C++

#include<bits/stdc++.h>
using namespace std;
 
class Queue
{
    // Initialize front and rear
    int rear, front;
 
    // Circular Queue
    int size;
    int *arr;
public:
    Queue(int s)
    {
       front = rear = -1;
       size = s;
       arr = new int[s];
    }
 
    void enQueue(int value);
    int deQueue();
    void displayQueue();
};
 
 
/* Function */
void Queue::enQueue(int value)
{
    if ((front == 0 && rear == size-1) ||
            (rear == (front-1)%(size-1)))
    {
        printf("\nQueue is Full");
        return;
    }
 
    else if (front == -1)     {
        front = rear = 0;
        arr[rear] = value;
    }
 
    else if (rear == size-1 && front != 0)
    {
        rear = 0;
        arr[rear] = value;
    }
 
    else
    {
        rear++;
        arr[rear] = value;
    }
}
 
// Function 
int Queue::deQueue()
{
    if (front == -1)
    {
        printf("\nQueue is Empty");
        return INT_MIN;
    }
 
    int data = arr[front];
    arr[front] = -1;
    if (front == rear)
    {
        front = -1;
        rear = -1;
    }
    else if (front == size-1)
        front = 0;
    else
        front++;
 
    return data;
}
 
// Function to display the elements  of Circular Queue
void Queue::displayQueue()
{
    if (front == -1)
    {
        printf("\nQueue is Empty");
        return;
    }
    printf("\nElements in Circular Queue are: ");
    if (rear >= front)
    {
        for (int i = front; i <= rear; i++)
            printf("%d ",arr[i]);
    }
    else
    {
        for (int i = front; i < size; i++)
            printf("%d ", arr[i]);
 
        for (int i = 0; i <= rear; i++)
            printf("%d ", arr[i]);
    }
}
 
int main()
{
    Queue q(5);
 
    // Inserting
    q.enQueue(14);
    q.enQueue(22);
    q.enQueue(13);
    q.enQueue(-6);
 
    // Display elements 
    q.displayQueue();
 
    // Deleting elements 
    printf("\nDeleted value = %d", q.deQueue());
    printf("\nDeleted value = %d", q.deQueue());
 
    q.displayQueue();
 
    q.enQueue(9);
    q.enQueue(20);
    q.enQueue(5);
 
    q.displayQueue();
 
    q.enQueue(20);
    return 0;
}

Output

Elements in Circular Queue are: 1 2 3 5
Deleted value = 1
Deleted value = 2
Elements in Circular Queue are: 3 5
Elements in Circular Queue are: 3 5 6 7 8 
Queue is Full

Program for circular queue in Java

import java.util.ArrayList;
 
class CircularQueue{
 
private int size, front, rear;
 
// Declaring array list 
private ArrayList<Integer> queue = new ArrayList<Integer>();
 
// Constructor
CircularQueue(int size)
{
    this.size = size;
    this.front = this.rear = -1;
}
 
// Method to insert a new element
public void enQueue(int data)
{
     
    // Condition if queue is full.
    if((front == 0 && rear == size - 1) ||
      (rear == (front - 1) % (size - 1)))
    {
        System.out.print("Queue is Full");
    }
 
    else if(front == -1)
    {
        front = 0;
        rear = 0;
        queue.add(rear, data);
    }
 
    else if(rear == size - 1 && front != 0)
    {
        rear = 0;
        queue.set(rear, data);
    }
 
    else
    {
        rear = (rear + 1);
     
        // Adding a new element 
        if(front <= rear)
        {
            queue.add(rear, data);
        }
     
                else
        {
            queue.set(rear, data);
        }
    }
}
 
// Function to dequeue an element
public int deQueue()
{
    int temp;
 
    if(front == -1)
    {
        System.out.print("Queue is Empty");
         
        return -1;
    }
 
    temp = queue.get(front);
 
    if(front == rear)
    {
        front = -1;
        rear = -1;
    }
 
    else if(front == size - 1)
    {
        front = 0;
    }
    else
    {
        front = front + 1;
    }
     / Returns the dequeued element
    return temp;
}
 
// Method to display the elements 
  public void displayQueue()
{
     
    // Condition for empty queue.
    if(front == -1)
    {
        System.out.print("Queue is Empty");
        return;
    }
 
   
    System.out.print("Elements in the " +
                     "circular queue are: ");
 
    if(rear >= front)
    {
     
        // Loop to print elements 
        for(int i = front; i <= rear; i++)
        {
            System.out.print(queue.get(i));
            System.out.print(" ");
        }
        System.out.println();
    }
 
    else
    {
         
           for(int i = front; i < size; i++)
        {
            System.out.print(queue.get(i));
            System.out.print(" ");
        }
 
           for(int i = 0; i <= rear; i++)
        {
            System.out.print(queue.get(i));
            System.out.print(" ");
        }
        System.out.println();
    }
}
 
public static void main(String[] args)
{
     
    CircularQueue q = new CircularQueue(5);
     
    q.enQueue(14);
    q.enQueue(22);
    q.enQueue(13);
    q.enQueue(-6);
     
    q.displayQueue();
 
    int x = q.deQueue();
 
    // Checking for empty queue.
    if(x != -1)
    {
        System.out.print("Deleted value = ");
        System.out.println(x);
    }
 
    x = q.deQueue();
 
    if(x != -1)
    {
        System.out.print("Deleted value = ");
        System.out.println(x);
    }
 
    q.displayQueue();
     
    q.enQueue(9);
    q.enQueue(20);
    q.enQueue(5);
     
    q.displayQueue();
     
    q.enQueue(20);
}
}

Output

Elements in Circular Queue are: 1 2 3 4 
Deleted value = 1
Deleted value = 2
Elements in Circular Queue are: 3 4 
Elements in Circular Queue are: 3 4 5 6 7
Queue is Full

Time Complexity of Circular Queue

Time complexity of enQueue() is O(1), deQueue() operation is O(1).

Applications of Circular Queue
 

• Memory Management
• Traffic system
• CPU Scheduling

Also read, Queue Data structure