What is a Circular Queue

Illustration of Circular Queue Operations

To better understand how a circular queue works, let's visualize its operations through a simple example. Imagine a circular queue that can hold up to five elements.

Initial State: Assume the queue is empty. The front and rear pointers are at position -1, indicating an empty state.

Enqueue 5, 3, and 9:

• Add 5: Rear moves to 0, Front is at 0, Queue now is [5].
   
• Add 3: Rear moves to 1, Queue now is [5, 3].
   
• Add 9: Rear moves to 2, Queue now is [5, 3, 9].

Dequeue:

• Remove 5: Front moves to 1, leaving Queue as [3, 9]. The position where 5 was gets cleared.

Enqueue 7 and 2:

• Add 7: Rear moves to 3, Queue becomes [3, 9, 7].
   
• Add 2: Rear moves to 4, Queue becomes [3, 9, 7, 2].

Circular Behavior:

• If we add another element, say 4, and the queue is full, the rear will need to wrap around to the start if there is a space due to prior dequeues.

Dequeue Twice:

• Remove 3: Front moves to 2, Queue shows [9, 7, 2].
   
• Remove 9: Front moves to 3, Queue shows [7, 2].

Enqueue 6:

• Since there’s a wrap-around, Rear goes back to 0 (the initial position), Queue finally looks like [6, 7, 2].
   

This example shows how the circular queue handles overflow by utilizing empty spaces left from dequeued elements, effectively maintaining its fixed size. It demonstrates the efficient use of space, as no position is wasted once it becomes available again. The front and rear pointers simply loop around the queue structure, ensuring seamless and continuous operations.

How to Implement a Circular Queue

Implementing a circular queue involves setting up a data structure with operations to add and remove elements efficiently. Here, we will discuss how to implement a circular queue : 

Setting Up: First, you need an array to hold the queue's elements and two pointers, front and rear, initially set to -1 to indicate the queue is empty.

Enqueue (Add Element)

• Check if Full: Before adding an element, check if the queue is full. If rear + 1 is equal to front, the queue is full.
   
• Initial Add: If the queue is empty (front and rear are -1), set both front and rear to 0.
   
• Wrap Around: If adding an element would exceed the array's limit, wrap the rear pointer to 0 (circular motion).
   
• Add the Element: Place the new element at the position indicated by rear and move the rear pointer one position forward.

Dequeue (Remove Element)

• Check if Empty: Before removing an element, check if the queue is empty (front is -1).
   
• Remove Element: Take out the element at front and, if only one element was left, reset front and rear to -1.
   
• Move Front: If more elements are left, move the front pointer forward, wrapping around to 0 if it goes past the last array index.
   
• Peek (Get Element at Front without Removing):
   
• Check if Empty: Ensure the queue isn't empty.
   
• Return Element: Return the element at the front position.

Example Code

• Python

Python

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1

    def enqueue(self, item):
        if (self.rear + 1) % self.size == self.front:
            print("Queue is full")
        elif self.front == -1:
            self.front = self.rear = 0
            self.queue[self.rear] = item
        else:
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = item
        print(f"Inserted {item}")

    def dequeue(self):
        if self.front == -1:
            print("Queue is empty")
        elif self.front == self.rear:
            print(f"Removed {self.queue[self.front]}")
            self.front = self.rear = -1
        else:
            print(f"Removed {self.queue[self.front]}")
            self.front = (self.front + 1) % self.size

    def display(self):
        if self.front == -1:
            print("Queue is empty")
        elif self.rear >= self.front:
            print("Elements in the circular queue are:", end=" ")
            for i in range(self.front, self.rear + 1):
                print(self.queue[i], end=" ")
            print()
        else:
            print("Elements in the circular queue are:", end=" ")
            for i in range(self.front, self.size):
                print(self.queue[i], end=" ")
            for i in range(0, self.rear + 1):
                print(self.queue[i], end=" ")
            print()

    def peek(self):
        if self.front == -1:
            print("Queue is empty")
        else:
            return self.queue[self.front]

# Create a circular queue of size 5
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.dequeue()
cq.enqueue(4)
cq.display()

You can also try this code with Online Python Compiler

Run Code

Output

Inserted 1
Inserted 2
Inserted 3
Removed 1
Inserted 4
Elements in the circular queue are: 2 3 4 

Implement Circular Queue Using Array

This approach ensures efficient space utilization and provides constant time operations, like enqueue and dequeue.

Steps to Implement Circular Queue Using Array

Initialization

• Start with an array of a fixed size. This size will determine the maximum number of elements the queue can hold.
   
• Initialize two pointers, front and rear, to -1 to indicate that the queue is empty.

Enqueue Operation (Add Element)

• Check Full Condition: First, check if the queue is full by seeing if (rear + 1) % array_size == front. If true, the queue is full, and no more elements can be added.
   
• Add First Element: If the queue is empty (front == -1), set both front and rear to 0 and insert the element at rear.
   
• Add Subsequent Elements: If not full, increment the rear pointer by one position circularly using the modulus operation (rear = (rear + 1) % array_size) and insert the new element at the rear position.

Dequeue Operation (Remove Element)

• Check Empty Condition: Before removing, check if the queue is empty by checking if front == -1. If true, the queue is empty, and there's nothing to remove.
   
• Remove Element: Remove the element at the front position.
   
• Single Element Condition: If the queue becomes empty after the dequeue operation (front == rear), reset both front and rear to -1.
   
• Adjust Front Pointer: Otherwise, increment the front pointer circularly (front = (front + 1) % array_size).

Peek Operation

Simply return the element at the front index without modifying the queue.

Example : 

• Python
• C++
• Java
• C

Python

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = self.rear = -1

    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front

    def is_empty(self):
        return self.front == -1

    def enqueue(self, value):
        if self.is_full():
            print("Queue is full")
            return
        if self.is_empty():
            self.front = 0
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = value
        print(f"Enqueued: {value}")

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty")
            return
        removed_value = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        print(f"Dequeued: {removed_value}")

    def peek(self):
        if self.is_empty():
            print("Queue is empty")
            return
        return self.queue[self.front]
# Create a circular queue of size 5
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.dequeue()
cq.enqueue(40)
cq.display()

You can also try this code with Online Python Compiler

Run Code

C++

#include <iostream>
using namespace std;

class CircularQueue {
private:
    int front, rear, size;
    int *queue;
public:
    CircularQueue(int sz) {
        front = rear = -1;
        size = sz;
        queue = new int[sz];
    }

    void enqueue(int value) {
        if ((rear + 1) % size == front) {
            cout << "Queue is full" << endl;
            return;
        }
        if (front == -1)
            front = 0;
        rear = (rear + 1) % size;
        queue[rear] = value;
        cout << "Enqueued: " << value << endl;
    }

    int dequeue() {
        if (front == -1) {
            cout << "Queue is empty" << endl;
            return -1;
        }
        int data = queue[front];
        if (front == rear)
            front = rear = -1;
        else
            front = (front + 1) % size;
        cout << "Dequeued: " << data << endl;
        return data;
    }

    void display() {
        if (front == -1) {
            cout << "Queue is empty" << endl;
            return;
        }
        cout << "Queue elements are: ";
        int i;
        for (i = front; i != rear; i = (i + 1) % size)
            cout << queue[i] << " ";
        cout << queue[i] << endl;
    }
};

int main() {
    CircularQueue q(5);
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.dequeue();
    q.enqueue(40);
    q.display();
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

public class CircularQueue {
    private int[] queue;
    private int front, rear, size;

    public CircularQueue(int size) {
        this.size = size;
        queue = new int[size];
        front = rear = -1;
    }

    public void enqueue(int value) {
        if ((rear + 1) % size == front) {
            System.out.println("Queue is full");
            return;
        }
        if (front == -1)
            front = 0;
        rear = (rear + 1) % size;
        queue[rear] = value;
        System.out.println("Enqueued: " + value);
    }

    public int dequeue() {
        if (front == -1) {
            System.out.println("Queue is empty");
            return -1;
        }
        int data = queue[front];
        if (front == rear)
            front = rear = -1;
        else
            front = (front + 1) % size;
        System.out.println("Dequeued: " + data);
        return data;
    }

    public void display() {
        if (front == -1) {
            System.out.println("Queue is empty");
            return;
        }
        System.out.print("Queue elements: ");
        for (int i = front; i != rear; i = (i + 1) % size)
            System.out.print(queue[i] + " ");
        System.out.println(queue[rear]);
    }

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

You can also try this code with Online Java Compiler

Run Code

C

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

int queue[SIZE], front = -1, rear = -1;

void enqueue(int value) {
    if ((rear + 1) % SIZE == front) {
        printf("Queue is full\n");
        return;
    }
    if (front == -1)
        front = 0;
    rear = (rear + 1) % SIZE;
    queue[rear] = value;
    printf("Enqueued: %d\n", value);
}

int dequeue() {
    if (front == -1) {
        printf("Queue is empty\n");
        return -1;
    }
    int data = queue[front];
    if (front == rear)
        front = rear = -1;
    else
        front = (front + 1) % SIZE;
    printf("Dequeued: %d\n", data);
    return data;
}

void display() {
    if (front == -1) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    for (int i = front; i != rear; i = (i + 1) % SIZE)
        printf("%d ", queue[i]);
    printf("%d\n", queue[rear]);
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    dequeue();
    enqueue(40);
    display();
    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Enqueued: 10
Enqueued: 20
Enqueued: 30
Dequeued: 10
Enqueued: 40
Queue elements: 20 30 40

Complexity Analysis of Circular Queue Operations

Complexity tells us about the time it takes to complete a task, like adding or removing an item in the queue, as the number of items grows.

Time Complexity

• Enqueue (Adding an Element): This operation takes a fixed amount of time, regardless of how many elements are in the queue. We call this constant time, or O(1), because it doesn't change with the size of the queue.
   
• Dequeue (Removing an Element): Just like enqueue, dequeue also operates in constant time, O(1). Removing an element always involves updating a couple of pointers, which takes the same amount of time no matter how full the queue is.
   
• Peek (Viewing the Front Element): Looking at the front element is also a constant time operation, O(1), because it directly accesses the element at the front pointer without any extra work.

Space Complexity

The space complexity of a circular queue is O(n), where n is the capacity of the queue. This means the amount of memory needed depends on the maximum number of items the queue can hold. The space needed does not increase as you add or remove elements; it stays the same, defined by the maximum capacity set when the queue is created.
 

These complexities show that circular queues are very efficient for tasks where items are continuously added and removed. The operations are fast because they only require updating pointers and don't involve moving all other elements around. This makes circular queues a great choice in scenarios where performance matters, like in system buffers, resource management, or handling real-time data.

Applications of Circular Queue

Here are some of the main applications where circular queues make a big difference:

Computer Systems

• CPU Scheduling: Circular queues are often used in managing processes within operating systems. They help organize the tasks waiting for CPU time, ensuring each process gets a turn and managing them efficiently as they rotate through their cycles.
   
• Memory Management: Buffers, areas where data is temporarily stored while being transferred from one place to another, often use circular queues. This helps in continuously managing data flow, especially in streaming or real-time data processing.

Networking

• Traffic Management: In network routers and switches, circular queues help manage packets of data waiting to be sent across the network, ensuring smooth data flow and reducing congestion or packet loss.
   
• Resource Allocation: Managing limited resources like bandwidth or connections can be done effectively with circular queues, as they allocate and recycle resources without interruptions.

Application Level

• Event Handling Systems: Many applications that need to handle a flow of incoming events, such as user inputs or system actions, use circular queues. This ensures all events are processed in a timely manner without any being skipped.
   
• Data Stream Management: Applications that deal with continuous data streams, such as multimedia applications or telemetry systems, use circular queues to maintain a steady handling of data samples.

Consumer Devices

Circular Buffers in Media Players: Audio and video players use circular buffers to preload media data, which allows for smooth playback and control over streaming media, reducing lags or buffer underflow.

Frequently Asked Questions

What makes a circular queue different from a normal queue?

A circular queue uses its space more efficiently by wrapping around to the beginning when it reaches the end, unlike a normal queue that leaves space unused after dequeuing elements.

Can a circular queue become full if there is an empty space at the beginning?

Yes, a circular queue can be full even if there are empty spaces at the beginning because it depends on the position of the front and rear pointers. If the rear pointer is just behind the front pointer, the queue is considered full.

How do you check if a circular queue is empty or full?

The queue is empty if the front pointer is at -1. It’s full if (rear + 1) % capacity == front, which means the next position of the rear after incrementing will point to the front.

Conclusion

In this article, we have learned about circular queues, a dynamic data structure that optimizes storage use and improves data processing efficiency. We covered how circular queues operate, including their basic operations like enqueue and dequeue, and explored how to implement them using arrays in various programming languages. We also talked about their applications across different fields such as computer systems, networking, and consumer devices, demonstrating their wide-ranging utility. 

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.