Introduction to Circular Queue

Last Updated : 17 Dec, 2024

A Circular Queue is another way of implementing a normal queue where the last element of the queue is connected to the first element of the queue forming a circle.

The operations are performed based on the FIFO (First In First Out) principle. It is also called ‘Ring Buffer’. In a normal Queue, we can insert elements until the queue becomes full. However once the queue becomes full, we can not insert the next element even if there is a space in front of the queue.

Table of Content

Operations on Circular Queue
Implement Circular Queue using Array
Complexity Analysis of Circular Queue Operations

Operations on Circular Queue

getFront: Get the front item from the queue.
getRear: Get the last item from the queue.
enqueue(value): To insert an element into the circular queue. In a circular queue, the new element is always inserted at the rear position.
dequeue(): To delete an element from the circular queue. In a circular queue, the element is always deleted from the front position.

Implement Circular Queue using Array

Initialize an array of size n, where n is the maximum number of elements that the queue can hold.
Initialize three variables (size, capacity, and front.)
Enqueue: To enqueue an element x into the queue, do the following:
1. Check if size == capacity (queue is full), display “Queue is full”.
2. If not full: calculate rear = (front + size) % capacity and Insert value at the rear index. Increment size by 1.
Dequeue: To dequeue an element from the queue, do the following:
1. Check if size == 0 (queue is empty), display “Queue is empty”.
2. If not empty: retrieve the element at the front index and move front = (front + 1) % capacity. Also, decrement size by 1 and return the removed element.

Illustration of Circular Queue:

Below is the implementation of above approach:

C++

// C++ program for insertion and
// deletion in Circular Queue
#include <iostream>
using namespace std;

class MyQueue {
private:
    int *arr;        
    int front, size; 
    int capacity;    

public:
  
    // Constructor to initialize the queue
    MyQueue(int c) {
        arr = new int[c];
        capacity = c;
        size = 0;
        front = 0;
    }

    // Get the front element
    int getFront() {
      
        // Queue is empty
        if (size == 0) 
            return -1; 
        return arr[front];
    }

    // Get the rear element
    int getRear() {
      
        // Queue is empty
        if (size == 0) 
            return -1; 
        int rear = (front + size - 1) % capacity;
        return arr[rear];
    }

    // Insert an element at the rear
    void enqueue(int x) {
      
        // Queue is full
        if (size == capacity) 
            return; 
        int rear = (front + size) % capacity;
        arr[rear] = x;
        size++;
    }

    // Remove an element from the front
    int dequeue() {
      
        // Queue is empty
        if (size == 0) 
            return -1;
        int res = arr[front];
        front = (front + 1) % capacity;
        size--;
        return res;
    }
};

int main() {
    MyQueue q(4);
    q.enqueue(10);
    cout << q.getFront() << " " << q.getRear() << endl;
    q.enqueue(20);
    cout << q.getFront() << " " << q.getRear() << endl;
    q.enqueue(30);
    cout << q.getFront() << " " << q.getRear() << endl;
    q.enqueue(40);
    cout << q.getFront() << " " << q.getRear() << endl;
    q.dequeue();
    cout << q.getFront() << " " << q.getRear() << endl;
    q.dequeue();
    cout << q.getFront() << " " << q.getRear() << endl;
    q.enqueue(50);
    cout << q.getFront() << " " << q.getRear() << endl;
    return 0;
}

Java

// Java program for insertion and
// deletion in Circular Queue
class MyQueue {
    private int[] arr;   
    private int front;   
    private int size;    
    private int capacity; 

    // Constructor to initialize the queue
    public MyQueue(int c) {
        arr = new int[c];
        capacity = c;
        size = 0;
        front = 0;
    }

    // Get the front element
    public int getFront() {
      
        // Queue is empty
        if (size == 0) 
            return -1;
        return arr[front];
    }

    // Get the rear element
    public int getRear() {
      
        // Queue is empty
        if (size == 0) 
            return -1; 
        int rear = (front + size - 1) % capacity;
        return arr[rear];
    }

    // Insert an element at the rear
    public void enqueue(int x) {
      
        // Queue is full   
        if (size == capacity) 
            return; 
        int rear = (front + size) % capacity;
        arr[rear] = x;
        size++;
    }

    // Remove an element from the front
    public int dequeue() {
      
        // Queue is empty
        if (size == 0) 
            return -1; 
        int res = arr[front];
        front = (front + 1) % capacity;
        size--;
        return res;
    }
}

class GfG {
  
    public static void main(String[] args) {
        MyQueue q = new MyQueue(4);
        q.enqueue(10);
        System.out.println(q.getFront() + " " + q.getRear());
        q.enqueue(20);
        System.out.println(q.getFront() + " " + q.getRear());
        q.enqueue(30);
        System.out.println(q.getFront() + " " + q.getRear());
        q.enqueue(40);
        System.out.println(q.getFront() + " " + q.getRear());
        q.dequeue();
        System.out.println(q.getFront() + " " + q.getRear());
        q.dequeue();
        System.out.println(q.getFront() + " " + q.getRear());
        q.enqueue(50);
        System.out.println(q.getFront() + " " + q.getRear());
    }
}

Python

# python3 program for insertion and
# deletion in Circular Queue
class MyQueue:
    def __init__(self, c):
        self.l = [None] * c
        self.cap = c  
        self.size = 0  
        self.front = 0  

    def getFront(self):
      
        # Check if queue is empty
        if self.size == 0:
            return None
        return self.l[self.front]  

    def getRear(self):
      
        # Check if queue is empty
        if self.size == 0:
            return None
          
        # Calculate rear index
        rear = (self.front + self.size - 1) % self.cap  
        return self.l[rear]  

    def enqueue(self, x):
      
        # Check if queue is full
        if self.size == self.cap:
            return
          
        # Calculate rear index
        rear = (self.front + self.size) % self.cap  
        self.l[rear] = x 
        self.size += 1 

    def dequeue(self):
      
        # Check if queue is empty
        if self.size == 0:
            return None
        res = self.l[self.front]  
        
        # Move front index circularly
        self.front = (self.front + 1) % self.cap 
        self.size -= 1  
        return res  

q = MyQueue(4)
q.enqueue(10)
print(q.getFront(), q.getRear())
q.enqueue(20)
print(q.getFront(), q.getRear())
q.enqueue(30)
print(q.getFront(), q.getRear())
q.enqueue(40)
print(q.getFront(), q.getRear())
q.dequeue()
print(q.getFront(), q.getRear())
q.dequeue()
print(q.getFront(), q.getRear())
q.enqueue(50)
print(q.getFront(), q.getRear())

// C# program for insertion and
// deletion in Circular Queue
using System;

class MyQueue {
    private int[] arr;  
    private int front;  
    private int size;   
    private int capacity; 

    // Constructor to initialize the queue
    public MyQueue(int c) {
        arr = new int[c];
        capacity = c;
        size = 0;
        front = 0;
    }

    // Get the front element
    public int getFront() {
      
        // Queue is empty
        if (size == 0) 
          return -1;
        return arr[front];
    }

    // Get the rear element
    public int getRear() {
      
        // Queue is empty
        if (size == 0) 
          return -1;
        int rear = (front + size - 1) % capacity;
        return arr[rear];
    }

    // Insert an element at the rear
    public void enqueue(int x) {
      
        // Queue is full
        if (size == capacity) return; 
        int rear = (front + size) % capacity;
        arr[rear] = x;
        size++;
    }

    // Remove an element from the front
    public int dequeue() {
      
        // Queue is empty
        if (size == 0) return -1; 
        int res = arr[front];
        front = (front + 1) % capacity;
        size--;
        return res;
    }
}
class GfG {
  
        static void Main(string[] args) {
        MyQueue q = new MyQueue(4);
        q.enqueue(10);
        Console.WriteLine(q.getFront() + " " + q.getRear());
        q.enqueue(20);
        Console.WriteLine(q.getFront() + " " + q.getRear());
        q.enqueue(30);
        Console.WriteLine(q.getFront() + " " + q.getRear());
        q.enqueue(40);
        Console.WriteLine(q.getFront() + " " + q.getRear());
        q.dequeue();
        Console.WriteLine(q.getFront() + " " + q.getRear());
        q.dequeue();
        Console.WriteLine(q.getFront() + " " + q.getRear());
        q.enqueue(50);
        Console.WriteLine(q.getFront() + " " + q.getRear());
    }
}

JavaScript

// JS program for insertion and
// deletion in Circular Queue
class MyQueue {
    constructor(c) {
        this.arr = new Array(c).fill(null);
        this.capacity = c; 
        this.size = 0; 
        this.front = 0;
    }

    // Get the front element
    getFront() {
    
        // Queue is empty
        if (this.size === 0) return null;
        return this.arr[this.front];
    }

    // Get the rear element
    getRear() {
    
        // Queue is empty
        if (this.size === 0) return null; 
        let rear = (this.front + this.size - 1) % this.capacity;
        return this.arr[rear];
    }

    // Insert an element at the rear
    enqueue(x) {
    
        // Queue is full
        if (this.size === this.capacity) return; 
        let rear = (this.front + this.size) % this.capacity;
        this.arr[rear] = x;
        this.size++;
    }

    // Remove an element from the front
    dequeue() {
    
        // Queue is empty
        if (this.size === 0) return null; 
        let res = this.arr[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.size--;
        return res;
    }
}

const q = new MyQueue(4);
q.enqueue(10);
console.log(q.getFront(), q.getRear());
q.enqueue(20);
console.log(q.getFront(), q.getRear());
q.enqueue(30);
console.log(q.getFront(), q.getRear());
q.enqueue(40);
console.log(q.getFront(), q.getRear());
q.dequeue();
console.log(q.getFront(), q.getRear());
q.dequeue();
console.log(q.getFront(), q.getRear());
q.enqueue(50);
console.log(q.getFront(), q.getRear());

Output

Complexity Analysis of Circular Queue Operations

Time Complexity:

Operation	Time Complexity
enqueue(x)	O(1)
dequeue()	O(1)
getFront()	O(1)
getRear()	O(1)

Auxiliary Space: O(size), where size is the number of elements in the circular queue.

Related article:

Abstract data types, Applications, Advantages and Disadvantages of Circular Queue – GeeksforGeeks

Introduction to Circular Linked List

Akash Gupta

Improve

Article Tags :

Practice Tags :

Queue

Introduction to Circular Queue

Operations on Circular Queue

Implement Circular Queue using Array

Complexity Analysis of Circular Queue Operations

Operation

Time Complexity

Similar Reads

Thank You!

What kind of Experience do you want to share?