Circular Queue in Data Structure

Introduction

In data structures, queues play an essential role in managing data in a sequential manner. However, standard queues come with limitations, particularly in terms of fixed size and inefficiency in utilizing available space. This is where the concept of a circular queue steps in, offering a more efficient and flexible way to handle queue operations.

A circular queue, also known as a ring buffer or cyclic buffer, is a linear data structure that connects the end of the queue back to the beginning, forming a circle.

In this blog, we will discuss the topic of circular queues their representation, different operations we can perform on them, and their implementation.

Representation of a Circular Queue

Let’s take a look at the example = [ 0, 1, 2, 3, 4, 5, 6, 7 ] where the size of the circular queue is 8.

The image below depicts an abstract circular queue. Initially, when a circular queue is created, it is empty, and the front and rear pointers are initialized to -1.

Suppose, initially first four elements are inserted into the circular queue. So, our Front pointer is on the 1st element and the Rear pointer is on the 4th element.

When the insertion of the elements starts, the Front pointer points to position 0, and the rear pointer points to the last inserted element’s position.

When the circular queue is completely filled, the front pointer points to the 0th index of the inserted element, and the rear pointer points to the last index of the inserted element. The main point of highlight is that the front pointer and the rear pointers are connected. Due to this property of the circular queue, it is also known as a “Ring Buffer.”

Circular Queue Implementation and Operations

Circular Queue implementation and operations involve creating the circular queue in our memory and performing various operations. To do so, we can use global variables, structures, or constructors.

In this article, all the circular queue implementation and operations are done in C++ language using struct and no global variables.

User Defined Data Type for Circular Queue

Here we declare a structure named circular_queue with three data members: arr (int type array to contain queue elements), front and rear (int type variables to store the front and rear positions). As soon as the default constructor is called, some memory is allocated to our circular queue in the physical memory.

// Struct to define the circular queue
struct circular_queue{
    
    // Array to store the elements of the queue
    int arr[MAX_SIZE];
    
    // Pointers for front and rear end
    int front,rear;
}

Operations of Circular Queue

Different types of operations that can be performed on our circular queue are:

front(): The front() operation returns the front element of the circular queue without removing it. This operation helps in accessing the first element for inspection or processing purposes, ensuring that the queue’s state remains unchanged.
rear(): The rear() operation provides the last element in the circular queue without removing it. This is useful for checking the most recently added element, allowing you to inspect the end of the queue while maintaining its integrity.
enQueue(value): The enQueue(value) operation adds a new element to the end of the circular queue. If the queue is not full, it places the element at the rear and updates the rear pointer, ensuring the circular nature is maintained.
deQueue(): The deQueue() operation removes the front element from the circular queue. It updates the front pointer to the next element in the sequence, effectively removing the element and maintaining the circular structure for subsequent operations.

EnQueue Operation

Inserting in the queue in the rear end is called enQueue.

Algorithm:

Check if the circular queue is full or not.
If full, then show an error message.
If not full, then insert the element at the end.
Change the pointer values.

DeQueue Operation

Deleting from the Queue from the front end is called deque.

Algorithm:

Check if the circular queue is empty or not.
If empty, then show an error message.
If not empty, then remove the first element.
Change the pointer values.

Display Operation

Showing the current elements of the circular queue.

Algorithm:

Check if the queue is empty or not.
If empty, then show the appropriate message.
If not empty, then print all the elements in the range front -> rear.

Dry Run

Initially, the insertion of elements in the circular queue takes place in the order

10, 20, 30, 40, and 50.

Circular queue(empty):

Insertion of 1st element with value 10:

Insertion of 2nd element with value 20:

Insertion of 3rd element with value 30:

Insertion of 4th element with value 40:

Insertion of 5th element with value 50:

Here, our circular queue is completely full as our front pointer is 0 and our rear pointer is 4 i.e. they are corresponding neighbours if we see in the figure above so no more insertions can be done. If our front pointer is 0 and last pointer is at max size -1 or if we our front pointer is equal to the rear pointer +1 that means they have reached adjacent to each other and, hence our circular queue is full.

Insertion of an element with the value 60:

‘Queue overflow’ message is displayed as our queue is already full.

Display of circular queue:

The elements in order are 10, 20, 30,40, and 50.

Deletion of an element from the circular queue:

As we know, the deletion takes place from the front end so let’s see how our circular queue will look after deletion.

Next Deletion:

Next Deletion:

Next Deletion:

Next Deletion:

Next Deletion:

As we can observe, our circular queue is now empty as our rear and front pointers have value equal to -1 so deletion from the queue is not possible. Hence, an error message is displayed as the output.

Display of Circular queue:

As the queue is empty, there will be no elements that can be displayed so an messgae ‘queue is empty’ is displayed as the output to the user.

C++ Implementation of Operations

1. Initialization of Circular Queue

In this function, we initialize the circular queue by assigning the front and rear pointers to -1.

// Function to initialize the circular queue
void initialiseQueue(circular_queue *cq){

	// Setting the front and rear pointers to -1
	cq->front = -1;
	cq->rear = -1;
}

2. enQueue in Circular Queue

In this function, we pass the circular queue and the element to be added into the circular queue as arguments. This block contains various checks to ensure that the element is correctly inserted as long as there is space in the circular queue. If the circular queue is full, then an error message is displayed. Else, the element is added, and a message is displayed.

// Function to insert elements to the circular queue
void enQueue(circular_queue *cq, int value){
	
	if((cq->front == 0 && cq->rear == MAX_SIZE-1) || (cq->front == cq->rear+1)){
		// Queue is already full
		cout<<("\n Queue Overflow \n\n");
		return;
	}
	
	// Queue is empty
	if(cq->front == -1){
		cq->front = 0;
		cq->rear = 0;
	}
	
	// Queue contains some elements
	else{
	    // Reached the end of the circular queue
		if(cq->rear == MAX_SIZE-1)
			cq->rear = 0;
		else
		    // incrementing rear pointer by 1 otherwise
			cq->rear += 1;
	}
	
	cq->arr [cq->rear] = value;
	cout<<(" Element with value ");
	cout<<value;
	
	// Successful addition of the element
	cout<<(" is successfully added to the Circular Queue\n");
}

3. deQueue in Circular Queue

This function is used for deleting the elements from the circular queue. During deletion, the first element is deleted, then the second, and so on. To do so, we pass the circular queue as an argument. We first check if the circular queue is empty or not. If it is empty, then an error message is displayed. Else, the first element is deleted.

// Function to delete the elements from the circular queue
void deQueue(circular_queue *cq){
	// Queue is Empty 
	if(cq->front == -1){
		cout<<("\n Queue is Empty/Deletion is not possible \n");
		return;
	}
	
	// Element deleted from the front end of the circular queue
	cout<<(" Element with value ");
	cout<<cq->arr[cq->front];
	cout<<(" deleted from Circular Queue\n");
	
	// If Queue contained only 1 element before deletion
	if(cq->front == cq->rear){
		cq->front = -1;
		cq->rear = -1;
	}
	
	// Queue contains greater than one element
	else{
		if(cq->front == MAX_SIZE-1)
			cq->front = 0;
		else
			cq->front = cq->front+1;
	}
}

4. Displaying the Circular Queue

As the name suggests, this function prints the circular queue from the front to the rear and also checks if the circular queue is empty or not. To do so, we pass the circular queue as an argument. If the queue is empty, then an appropriate error message is displayed. Else, we print the whole circular queue.

// Function to display the elements of the circular queue
void display_queue(circular_queue *cq){
	int curr_front = cq->front, curr_rear = cq->rear;
	
	// Circular queue is empty
	if(cq->front == -1){
		cout<<("\n Queue is Empty \n");
		return;
	}
	
	cout<<("\n The Circular Queue elements are :\n");
	cout<<" ";
	
	// If front <= rear simply iterate over the arr
	if(curr_front <= curr_rear){
		while(curr_front <= curr_rear){
			cout<<(cq->arr[curr_front]);
			cout<<" ";
			curr_front++;
		}
	}
	/*
	    If front >= rear we have to go first 
	    from front to last element(MAX_SIZE-1)
	    then from 0 to rear end
	*/
	else{
	    // Iterating from front to last element(MAX_SIZE-1)
		while(curr_front <= MAX_SIZE-1){
			cout<<(cq->arr[curr_front]);
			cout<<" ";
			curr_front++;
		}
		
		curr_front = 0;
		
		// Iterating from 0 to rear end
		while(curr_front <= curr_rear){
			cout<<(cq->arr[curr_front]);
			cout<<" ";
			curr_front++;
		}
	}
	
	cout<<"\n";
}

Implementation

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_SIZE=5;

// Struct to define the circular queue
struct circular_queue{
    
    // Array to store the elements of the queue
    int arr[MAX_SIZE];

    // Pointers for front and rear end
    int front,rear;
};

// Function to initialise the circular queue
void initialise_queue(circular_queue *cq){
    
    // Setting the front and rear pointers to -1
	cq->front = -1;
	cq->rear = -1;	
}

// Function to insert elements to the circular queue
void enQueue(circular_queue *cq, int value){
	
	
	if((cq->front == 0 && cq->rear == MAX_SIZE-1) || (cq->front == cq->rear+1)){
		// Queue is already full
		cout<<("\n Queue Overflow \n\n");
		return;
	}
	
	// Queue is empty
	if(cq->front == -1){
		cq->front = 0;
		cq->rear = 0;
	}
	// Queue contains some elements
	else{
	    // Reached the end of the circular queue
		if(cq->rear == MAX_SIZE-1)
			cq->rear = 0;
		else
		    // incrementing rear pointer by 1 otherwise
			cq->rear += 1;
	}
	
	cq->arr [cq->rear] = value;
	cout<<(" Element with value ");
	cout<<value;
	
	// Successful addition of the element
	cout<<(" is successfully added to the Circular Queue\n");
}

// Function to delete the elements from the circular queue
void deQueue(circular_queue *cq){
	// Queue is Empty 
	if(cq->front == -1){
		cout<<("\n Queue is Empty/Deletion is not possible \n");
		return;
	}
	
	// Element deleted from the front end of the circular queue
	cout<<(" Element with value ");
	cout<<cq->arr[cq->front];
	cout<<(" deleted from Circular Queue\n");
	
	// If Queue contained only 1 element before deletion
	if(cq->front == cq->rear){
		cq->front = -1;
		cq->rear = -1;
	}
	
	// Queue contains greater than one element
	else{
		if(cq->front == MAX_SIZE-1)
			cq->front = 0;
		else
			cq->front = cq->front+1;
	}
}

// Function to display the elements of the circular queue
void display_queue(circular_queue *cq){
	int curr_front = cq->front, curr_rear = cq->rear;
	
	// Circular queue is empty
	if(cq->front == -1){
		cout<<("\n Queue is Empty \n");
		return;
	}
	
	cout<<("\n The Circular Queue elements are :\n");
	cout<<" ";
	// If front <= rear simply iterate over the arr
	if(curr_front <= curr_rear){
		while(curr_front <= curr_rear){
			cout<<(cq->arr[curr_front]);
			cout<<" ";
			curr_front++;
		}
	}
	/*
	    If front >= rear we have to go first 
	    from front to last element(MAX_SIZE-1)
	    then from 0 to rear end
	*/
	else{
	    // Iterating from front to last element(MAX_SIZE-1)
		while(curr_front <= MAX_SIZE-1){
			cout<<(cq->arr[curr_front]);
			cout<<" ";
			curr_front++;
		}
		
		curr_front = 0;
		
		// Iterating from 0 to rear end
		while(curr_front <= curr_rear){
			cout<<(cq->arr[curr_front]);
			cout<<" ";
			curr_front++;
		}
	}
	
	cout<<"\n";
}

// Driver code for main function
int main(){
	// Making a circular queue
	circular_queue q;
	
	// Initialization of the circular queue
	initialise_queue(&q);
	
	// Pushing elements in order 10->20->30->40->50
	enQueue(&q, 10);
	enQueue(&q, 20);
	enQueue(&q, 30);
	enQueue(&q, 40);
	enQueue(&q, 50);
	
	// Displaying the elements of the circular queue
	display_queue(&q);
	
	// Pushing some element
	enQueue(&q, 60);
	
	// Deleting elements from the circular queue
	deQueue(&q);	
	deQueue(&q);
	deQueue(&q);
	deQueue(&q);
	deQueue(&q);
	deQueue(&q);
	
	display_queue(&q);
	
	return 0;	
}

Java

import java.util.*;

public class CircularQueue {
    private static final int MAX_SIZE = 5;
    private int[] arr = new int[MAX_SIZE];
    private int front = -1, rear = -1;

    public void initialiseQueue() {
        front = -1;
        rear = -1;
    }

    public void enQueue(int value) {
        if ((front == 0 && rear == MAX_SIZE - 1) || (front == rear + 1)) {
            System.out.println("\n Queue Overflow \n\n");
            return;
        }
        if (front == -1) {
            front = 0;
            rear = 0;
        } else if (rear == MAX_SIZE - 1) {
            rear = 0;
        } else {
            rear += 1;
        }
        arr[rear] = value;
        System.out.println(" Element with value " + value + " is successfully added to the Circular Queue");
    }

    public void deQueue() {
        if (front == -1) {
            System.out.println("\n Queue is Empty/Deletion is not possible \n");
            return;
        }
        System.out.println(" Element with value " + arr[front] + " deleted from Circular Queue");
        if (front == rear) {
            front = -1;
            rear = -1;
        } else if (front == MAX_SIZE - 1) {
            front = 0;
        } else {
            front = front + 1;
        }
    }

    public void displayQueue() {
        if (front == -1) {
            System.out.println("\n Queue is Empty \n");
            return;
        }
        System.out.println("\n The Circular Queue elements are :");
        if (front <= rear) {
            for (int i = front; i <= rear; i++) {
                System.out.print(arr[i] + " ");
            }
        } else {
            for (int i = front; i < MAX_SIZE; i++) {
                System.out.print(arr[i] + " ");
            }
            for (int i = 0; i <= rear; i++) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CircularQueue q = new CircularQueue();
        q.initialiseQueue();
        q.enQueue(10);
        q.enQueue(20);
        q.enQueue(30);
        q.enQueue(40);
        q.enQueue(50);
        q.displayQueue();
        q.enQueue(60);
        q.deQueue();
        q.deQueue();
        q.deQueue();
        q.deQueue();
        q.deQueue();
        q.deQueue();
        q.displayQueue();
    }
}

Python

class CircularQueue:
    MAX_SIZE = 5

    def __init__(self):
        self.arr = [0] * self.MAX_SIZE
        self.front = self.rear = -1

    def enqueue(self, value):
        if (self.front == 0 and self.rear == self.MAX_SIZE - 1) or (self.front == self.rear + 1):
            print("Queue Overflow")
            return
        if self.front == -1:
            self.front = self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.MAX_SIZE
        self.arr[self.rear] = value
        print(f"Element with value {value} is successfully added to the Circular Queue")

    def dequeue(self):
        if self.front == -1:
            print("Queue is Empty/Deletion is not possible")
            return
        print(f"Element with value {self.arr[self.front]} deleted from Circular Queue")
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.MAX_SIZE

    def display(self):
        if self.front == -1:
            print("Queue is Empty")
            return
        print("The Circular Queue elements are:")
        i = self.front
        while True:
            print(self.arr[i], end=" ")
            if i == self.rear:
                break
            i = (i + 1) % self.MAX_SIZE
        print()

# Driver code
cq = CircularQueue()
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.enqueue(50)
cq.display()
cq.enqueue(60)
cq.dequeue()
cq.dequeue()
cq.dequeue()
cq.dequeue()
cq.dequeue()
cq.dequeue()
cq.display()

Javascript

class CircularQueue {
    constructor(size) {
        this.MAX_SIZE = size;
        this.arr = new Array(size).fill(0);
        this.front = this.rear = -1;
    }

    enqueue(value) {
        if ((this.front === 0 && this.rear === this.MAX_SIZE - 1) || (this.front === this.rear + 1)) {
            console.log("Queue Overflow");
            return;
        }
        if (this.front === -1) {
            this.front = this.rear = 0;
        } else {
            this.rear = (this.rear + 1) % this.MAX_SIZE;
        }
        this.arr[this.rear] = value;
        console.log(`Element with value ${value} is successfully added to the Circular Queue`);
    }

    dequeue() {
        if (this.front === -1) {
            console.log("Queue is Empty/Deletion is not possible");
            return;
        }
        console.log(`Element with value ${this.arr[this.front]} deleted from Circular Queue`);
        if (this.front === this.rear) {
            this.front = this.rear = -1;
        } else {
            this.front = (this.front + 1) % this.MAX_SIZE;
        }
    }

    display() {
        if (this.front === -1) {
            console.log("Queue is Empty");
            return;
        }
        console.log("The Circular Queue elements are:");
        let i = this.front;
        while (true) {
            process.stdout.write(this.arr[i] + " ");
            if (i === this.rear) break;
            i = (i + 1) % this.MAX_SIZE;
        }
        console.log();
    }
}

// Driver code
const cq = new CircularQueue(5);
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
cq.enqueue(40);
cq.enqueue(50);
cq.display();
cq.enqueue(60);
cq.dequeue();
cq.dequeue();
cq.dequeue();
cq.dequeue();
cq.dequeue();
cq.dequeue();
cq.display();

C#

using System;

class CircularQueue {
    private const int MAX_SIZE = 5;
    private int[] arr;
    private int front, rear;

    public CircularQueue() {
        arr = new int[MAX_SIZE];
        front = rear = -1;
    }

    public void Enqueue(int value) {
        if ((front == 0 && rear == MAX_SIZE - 1) || (front == rear + 1)) {
            Console.WriteLine("Queue Overflow");
            return;
        }
        if (front == -1) {
            front = rear = 0;
        } else {
            rear = (rear + 1) % MAX_SIZE;
        }
        arr[rear] = value;
        Console.WriteLine($"Element with value {value} is successfully added to the Circular Queue");
    }

    public void Dequeue() {
        if (front == -1) {
            Console.WriteLine("Queue is Empty/Deletion is not possible");
            return;
        }
        Console.WriteLine($"Element with value {arr[front]} deleted from Circular Queue");
        if (front == rear) {
            front = rear = -1;
        } else {
            front = (front + 1) % MAX_SIZE;
        }
    }

    public void Display() {
        if (front == -1) {
            Console.WriteLine("Queue is Empty");
            return;
        }
        Console.WriteLine("The Circular Queue elements are:");
        int i = front;
        while (true) {
            Console.Write(arr[i] + " ");
            if (i == rear) break;
            i = (i + 1) % MAX_SIZE;
        }
        Console.WriteLine();
    }
}

// Driver code
class Program {
    static void Main() {
        CircularQueue cq = new CircularQueue();
        cq.Enqueue(10);
        cq.Enqueue(20);
        cq.Enqueue(30);
        cq.Enqueue(40);
        cq.Enqueue(50);
        cq.Display();
        cq.Enqueue(60);
        cq.Dequeue();
        cq.Dequeue();
        cq.Dequeue();
        cq.Dequeue();
        cq.Dequeue();
        cq.Dequeue();
        cq.Display();
    }
}

PHP

<?php

class CircularQueue {
    const MAX_SIZE = 5;
    private $arr;
    private $front;
    private $rear;

    public function __construct() {
        $this->arr = array_fill(0, self::MAX_SIZE, 0);
        $this->front = $this->rear = -1;
    }

    public function initialiseQueue() {
        $this->front = $this->rear = -1;
    }

    public function enqueue($value) {
        if (($this->front === 0 && $this->rear === self::MAX_SIZE - 1) || ($this->front === $this->rear + 1)) {
            echo "Queue Overflow\n\n";
            return;
        }
        if ($this->front === -1) {
            $this->front = $this->rear = 0;
        } else {
            $this->rear = ($this->rear + 1) % self::MAX_SIZE;
        }
        $this->arr[$this->rear] = $value;
        echo "Element with value $value is successfully added to the Circular Queue\n";
    }

    public function dequeue() {
        if ($this->front === -1) {
            echo "Queue is Empty/Deletion is not possible\n";
            return;
        }
        echo "Element with value " . $this->arr[$this->front] . " deleted from Circular Queue\n";
        if ($this->front === $this->rear) {
            $this->front = $this->rear = -1;
        } else {
            $this->front = ($this->front + 1) % self::MAX_SIZE;
        }
    }

    public function displayQueue() {
        if ($this->front === -1) {
            echo "Queue is Empty\n";
            return;
        }
        echo "The Circular Queue elements are:\n";
        $currFront = $this->front;
        $currRear = $this->rear;

        if ($currFront <= $currRear) {
            while ($currFront <= $currRear) {
                echo $this->arr[$currFront] . " ";
                $currFront++;
            }
        } else {
            while ($currFront < self::MAX_SIZE) {
                echo $this->arr[$currFront] . " ";
                $currFront++;
            }
            $currFront = 0;
            while ($currFront <= $currRear) {
                echo $this->arr[$currFront] . " ";
                $currFront++;
            }
        }
        echo "\n";
    }
}

// Driver code
$cq = new CircularQueue();
$cq->initialiseQueue();
$cq->enqueue(10);
$cq->enqueue(20);
$cq->enqueue(30);
$cq->enqueue(40);
$cq->enqueue(50);
$cq->displayQueue();
$cq->enqueue(60);
$cq->dequeue();
$cq->dequeue();
$cq->dequeue();
$cq->dequeue();
$cq->dequeue();
$cq->dequeue();
$cq->displayQueue();
?>

Output

Time Complexity

In the given C++ implementation, the time complexity of the insertion and deletion is constant. Thus, deQueue and enQueue operations get executed in O(1) time.

T(n) = O(1) for insertion and deletion

Since in the display function, we iterate through the whole circular queue once, its time complexity is,

T(n) = O(N) for displaying the elements

Where N is the current number of elements in our circular queue.

Space Complexity

A circular queue of size n is created in the given C++ implementation as soon as the program is executed. Thus, O(N) space is required for circular queue implementation where N is the maximum size of our circular queue.

Read about Application of Queue in Data Structure here.

You can also read about the topic - hash function in data structure

Application of Circular Queue

CPU Scheduling: Circular queues manage processes in round-robin scheduling, ensuring fair CPU time allocation.
Data Buffering: Used in streaming data applications (e.g., audio or video buffering) to handle continuous data flow.
Resource Management: Manages a pool of resources like printers or network connections, where resources are allocated and released in a cyclic manner.
Traffic Management: Manages packet routing in networking where packets are processed in a cyclic order.

Implementation of circular queue using Array

A circular queue using an array efficiently manages space by wrapping around when the end of the array is reached. It supports enqueue and dequeue operations while ensuring that the array's end connects to the beginning, providing a continuous cycle of elements.

C++

#include <iostream>
using namespace std;

#define MAX_SIZE 5

class CircularQueue {
    int arr[MAX_SIZE];
    int front, rear;

public:
    CircularQueue() : front(-1), rear(-1) {}

    void enqueue(int value) {
        if ((front == 0 && rear == MAX_SIZE - 1) || (front == rear + 1)) {
            cout << "Queue Overflow" << endl;
            return;
        }
        if (front == -1) front = rear = 0;
        else rear = (rear + 1) % MAX_SIZE;
        arr[rear] = value;
    }

    void display() {
        if (front == -1) {
            cout << "Queue is Empty" << endl;
            return;
        }
        int i = front;
        while (true) {
            cout << arr[i] << " ";
            if (i == rear) break;
            i = (i + 1) % MAX_SIZE;
        }
        cout << endl;
    }
};

// Example usage
int main() {
    CircularQueue cq;
    cq.enqueue(10);
    cq.enqueue(20);
    cq.enqueue(30);
    cq.display();
    return 0;
}

Java

class CircularQueue {
    private static final int MAX_SIZE = 5;
    private int[] arr = new int[MAX_SIZE];
    private int front = -1, rear = -1;

    public void enqueue(int value) {
        if ((front == 0 && rear == MAX_SIZE - 1) || (front == rear + 1)) {
            System.out.println("Queue Overflow");
            return;
        }
        if (front == -1) front = rear = 0;
        else rear = (rear + 1) % MAX_SIZE;
        arr[rear] = value;
    }

    public void display() {
        if (front == -1) {
            System.out.println("Queue is Empty");
            return;
        }
        int i = front;
        while (true) {
            System.out.print(arr[i] + " ");
            if (i == rear) break;
            i = (i + 1) % MAX_SIZE;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CircularQueue cq = new CircularQueue();
        cq.enqueue(10);
        cq.enqueue(20);
        cq.enqueue(30);
        cq.display(); 
    }
}

Python

class CircularQueue:
    MAX_SIZE = 5

    def __init__(self):
        self.arr = [0] * self.MAX_SIZE
        self.front = self.rear = -1

    def enqueue(self, value):
        if (self.front == 0 and self.rear == self.MAX_SIZE - 1) or (self.front == self.rear + 1):
            print("Queue Overflow")
            return
        if self.front == -1:
            self.front = self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.MAX_SIZE
        self.arr[self.rear] = value

    def display(self):
        if self.front == -1:
            print("Queue is Empty")
            return
        i = self.front
        while True:
            print(self.arr[i], end=" ")
            if i == self.rear:
                break
            i = (i + 1) % self.MAX_SIZE
        print()

# Example usage
cq = CircularQueue()
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.display()

Javascript

class CircularQueue {
    constructor(size) {
        this.MAX_SIZE = size;
        this.arr = new Array(size).fill(0);
        this.front = this.rear = -1;
    }

    enqueue(value) {
        if ((this.front === 0 && this.rear === this.MAX_SIZE - 1) || (this.front === this.rear + 1)) {
            console.log("Queue Overflow");
            return;
        }
        if (this.front === -1) {
            this.front = this.rear = 0;
        } else {
            this.rear = (this.rear + 1) % this.MAX_SIZE;
        }
        this.arr[this.rear] = value;
    }

    display() {
        if (this.front === -1) {
            console.log("Queue is Empty");
            return;
        }
        let i = this.front;
        while (true) {
            process.stdout.write(this.arr[i] + " ");
            if (i === this.rear) break;
            i = (i + 1) % this.MAX_SIZE;
        }
        console.log();
    }
}

// Example usage
const cq = new CircularQueue(5);
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
cq.display();

C#

using System;

class CircularQueue {
    private const int MAX_SIZE = 5;
    private int[] arr = new int[MAX_SIZE];
    private int front = -1, rear = -1;

    public void Enqueue(int value) {
        if ((front == 0 && rear == MAX_SIZE - 1) || (front == rear + 1)) {
            Console.WriteLine("Queue Overflow");
            return;
        }
        if (front == -1) front = rear = 0;
        else rear = (rear + 1) % MAX_SIZE;
        arr[rear] = value;
    }

    public void Display() {
        if (front == -1) {
            Console.WriteLine("Queue is Empty");
            return;
        }
        int i = front;
        while (true) {
            Console.Write(arr[i] + " ");
            if (i == rear) break;
            i = (i + 1) % MAX_SIZE;
        }
        Console.WriteLine();
    }
}

// Example usage
class Program {
    static void Main() {
        CircularQueue cq = new CircularQueue();
        cq.Enqueue(10);
        cq.Enqueue(20);
        cq.Enqueue(30);
        cq.Display(); 
    }
}

PHP

<?php

class CircularQueue {
    const MAX_SIZE = 5;
    private $arr;
    private $front;
    private $rear;

    public function __construct() {
        $this->arr = array_fill(0, self::MAX_SIZE, 0);
        $this->front = $this->rear = -1;
    }

    public function enqueue($value) {
        if (($this->front === 0 && $this->rear === self::MAX_SIZE - 1) || ($this->front === $this->rear + 1)) {
            echo "Queue Overflow\n";
            return;
        }
        if ($this->front === -1) {
            $this->front = $this->rear = 0;
        } else {
            $this->rear = ($this->rear + 1) % self::MAX_SIZE;
        }
        $this->arr[$this->rear] = $value;
    }

    public function display() {
        if ($this->front === -1) {
            echo "Queue is Empty\n";
            return;
        }
        $i = $this->front;
        while (true) {
            echo $this->arr[$i] . " ";
            if ($i === $this->rear) break;
            $i = ($i + 1) % self::MAX_SIZE;
        }
        echo "\n";
    }
}

// Example usage
$cq = new CircularQueue();
$cq->enqueue(10);
$cq->enqueue(20);
$cq->enqueue(30);
$cq->display();  
?>

Output

10 20 30

Implementation of circular queue using linked list

A circular queue using a linked list dynamically manages memory and handles wrap-around efficiently by linking the last node back to the first node. This setup ensures a continuous loop of elements, allowing for efficient enqueue and dequeue operations.

C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int data) : data(data), next(nullptr) {}
};

class CircularQueue {
    Node* front;
    Node* rear;

public:
    CircularQueue() : front(nullptr), rear(nullptr) {}

    void enqueue(int value) {
        Node* newNode = new Node(value);
        if (!front) {
            front = rear = newNode;
            rear->next = front;
        } else {
            rear->next = newNode;
            rear = newNode;
            rear->next = front;
        }
    }

    void display() {
        if (!front) {
            cout << "Queue is Empty" << endl;
            return;
        }
        Node* temp = front;
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != front);
        cout << endl;
    }
};

// Example usage
int main() {
    CircularQueue cq;
    cq.enqueue(10);
    cq.enqueue(20);
    cq.enqueue(30);
    cq.display(); 
    return 0;
}

Java

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class CircularQueue {
    private Node front, rear;

    public CircularQueue() {
        front = rear = null;
    }

    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (front == null) {
            front = rear = newNode;
            rear.next = front;
        } else {
            rear.next = newNode;
            rear = newNode;
            rear.next = front;
        }
    }

    public void display() {
        if (front == null) {
            System.out.println("Queue is Empty");
            return;
        }
        Node temp = front;
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != front);
        System.out.println();
    }

    public static void main(String[] args) {
        CircularQueue cq = new CircularQueue();
        cq.enqueue(10);
        cq.enqueue(20);
        cq.enqueue(30);
        cq.display();
    }
}

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularQueue:
    def __init__(self):
        self.front = self.rear = None

    def enqueue(self, value):
        new_node = Node(value)
        if self.front is None:
            self.front = self.rear = new_node
            self.rear.next = self.front
        else:
            self.rear.next = new_node
            self.rear = new_node
            self.rear.next = self.front

    def display(self):
        if self.front is None:
            print("Queue is Empty")
            return
        temp = self.front
        while True:
            print(temp.data, end=" ")
            temp = temp.next
            if temp == self.front:
                break
        print()

# Example usage
cq = CircularQueue()
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.display()

Javascript

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class CircularQueue {
    constructor() {
        this.front = this.rear = null;
    }

    enqueue(value) {
        const newNode = new Node(value);
        if (!this.front) {
            this.front = this.rear = newNode;
            this.rear.next = this.front;
        } else {
            this.rear.next = newNode;
            this.rear = newNode;
            this.rear.next = this.front;
        }
    }

    display() {
        if (!this.front) {
            console.log("Queue is Empty");
            return;
        }
        let temp = this.front;
        do {
            process.stdout.write(temp.data + " ");
            temp = temp.next;
        } while (temp !== this.front);
        console.log();
    }
}

// Example usage
const cq = new CircularQueue();
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
cq.display();

C#

using System;

class Node {
    public int Data;
    public Node Next;
    public Node(int data) {
        Data = data;
        Next = null;
    }
}

class CircularQueue {
    private Node front, rear;

    public CircularQueue() {
        front = rear = null;
    }

    public void Enqueue(int value) {
        Node newNode = new Node(value);
        if (front == null) {
            front = rear = newNode;
            rear.Next = front;
        } else {
            rear.Next = newNode;
            rear = newNode;
            rear.Next = front;
        }
    }

    public void Display() {
        if (front == null) {
            Console.WriteLine("Queue is Empty");
            return;
        }
        Node temp = front;
        do {
            Console.Write(temp.Data + " ");
            temp = temp.Next;
        } while (temp != front);
        Console.WriteLine();
    }
}

// Example usage
class Program {
    static void Main() {
        CircularQueue cq = new CircularQueue();
        cq.Enqueue(10);
        cq.Enqueue(20);
        cq.Enqueue(30);
        cq.Display(); 
    }
}

PHP

<?php

class Node {
    public $data;
    public $next;
    public function __construct($data) {
        $this->data = $data;
        $this->next = null;
    }
}

class CircularQueue {
    private $front;
    private $rear;

    public function __construct() {
        $this->front = $this->rear = null;
    }

    public function enqueue($value) {
        $newNode = new Node($value);
        if ($this->front === null) {
            $this->front = $this->rear = $newNode;
            $this->rear->next = $this->front;
        } else {
            $this->rear->next = $newNode;
            $this->rear = $newNode;
            $this->rear->next = $this->front;
        }
    }

    public function display() {
        if ($this->front === null) {
            echo "Queue is Empty\n";
            return;
        }
        $temp = $this->front;
        do {
            echo $temp->data . " ";
            $temp = $temp->next;
        } while ($temp !== $this->front);
        echo "\n";
    }
}

// Example usage
$cq = new CircularQueue();
$cq->enqueue(10);
$cq->enqueue(20);
$cq->enqueue(30);
$cq->display(); 
?>

Output

10 20 30

Frequently Asked Questions

What are the different applications of the circular queue?

Circular queues are used in memory management, traffic control systems, and CPU scheduling algorithms.

What is the difference between a circular queue and a linear queue?

A linear data structure known as a queue employs the FIFO (First In, First Out) ordering principle. A circular queue is just a linear queue variation in which the front and back ends are joined to reduce the linear queue's inefficient use of space.

What are the disadvantages of a circular queue?

You can only store as many elements in a circular queue as the length of the queue, therefore you must know the maximum size in advance. In a circular queue, some actions, like deletion or insertion, can be complicated.

What are the different ways to implement a circular queue?

There are various methods to implement a circular queue but the most common ones are using arrays and linked lists.

What are queue and their types in data structure?

A queue is a data structure that follows the property of first in first out. There are four kinds of queues available – simple queue, circular queue, priority queue, and double-ended queue.

Conclusion

Queues are data structures that resemble real-life queues and support entry from one end and exit from another end. They have several real-life applications which involve the implementation of a stack using two queues, CPU task scheduling, graph traversals, etc.

In this blog, we discussed the topic of circular queues and the different operations that we can perform on them and we saw the implementation of circular queues in C++. Queues are also an important data structure in view of interview preparations and placement. It is therefore imperative to become an expert with queues, understand what goes underneath the hood, and where you can apply your learnings.