Implementing Circular Queue in Data Structure

A Circular Queue is a linear data structure that connects the last position back to the first, forming a circle. This design efficiently reuses the empty spaces left behind after elements are dequeued from a regular (linear) queue.

Why Circular Queue?

In a simple linear queue implemented with a fixed-size array, once elements are dequeued from the front, that space is wasted because new elements can still only be added at the rear, even if there is free space at the beginning. A circular queue solves this by wrapping the rear pointer back to index 0 when it reaches the end.

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

    def is_full(self):
        return self.size == self.capacity

    def is_empty(self):
        return self.size == 0

    def enqueue(self, item):
        if self.is_full():
            raise OverflowError("Queue is full")
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

Complexity

Applications

• CPU scheduling using round-robin algorithms.
• Buffering data streams, such as in audio/video streaming.
• Traffic light control systems that cycle through a fixed sequence.