What is Circular Queue: Explanation, Example, and Uses

A circular queue is a data structure that uses a fixed-size buffer in a circular way, where the end connects back to the start. It efficiently manages elements by reusing empty spaces created when items are removed, avoiding wasted space common in regular queues.

How It Works

A circular queue works like a line of people waiting, but when the line reaches the end of the space, it loops back to the beginning if there is room. Imagine a circular track where runners keep going around; similarly, the queue's start and end wrap around in a circle.

This means when you remove an item from the front, the space it occupied becomes free, and new items can be added there instead of only at the end. This avoids the problem of a regular queue where the end moves forward and leaves unused space at the front.

Two pointers, usually called front and rear, keep track of where to remove and add items. When rear reaches the last position, it moves back to zero if space is available, making the queue circular.

Example

This example shows a simple circular queue implementation in Python with basic operations: enqueue (add), dequeue (remove), and display.

python

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

    def enqueue(self, data):
        if ((self.rear + 1) % self.size == self.front):
            print("Queue is full")
            return
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = data

    def dequeue(self):
        if self.front == -1:
            print("Queue is empty")
            return None
        data = self.queue[self.front]
        if self.front == self.rear:
            self.front = -1
            self.rear = -1
        else:
            self.front = (self.front + 1) % self.size
        return data

    def display(self):
        if self.front == -1:
            print("Queue is empty")
            return
        i = self.front
        elements = []
        while True:
            elements.append(str(self.queue[i]))
            if i == self.rear:
                break
            i = (i + 1) % self.size
        print("Queue:", " -> ".join(elements))

# Usage example
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.enqueue(40)
cq.display()
print("Dequeued:", cq.dequeue())
cq.display()
cq.enqueue(50)
cq.enqueue(60)
cq.display()
cq.enqueue(70)  # Should show full message

Output

Queue: 10 -> 20 -> 30 -> 40
Dequeued: 10
Queue: 20 -> 30 -> 40
Queue: 20 -> 30 -> 40 -> 50 -> 60
Queue is full

When to Use

Use a circular queue when you need a fixed-size buffer that efficiently reuses space, such as in:

• Handling streaming data where old data is removed and new data added continuously.
• Managing tasks in a round-robin scheduler where each task gets a turn in a cycle.
• Implementing buffers in hardware or software like keyboard buffers or network packet buffers.

It is ideal when you want to avoid the wasted space problem of a normal queue and need constant time operations for adding and removing elements.

Key Points

• A circular queue connects the end back to the start to reuse space.
• It uses two pointers, front and rear, to track elements.
• It prevents wasted space common in linear queues.
• Operations like enqueue and dequeue run in constant time.
• Commonly used in buffering and scheduling tasks.

Key Takeaways

A circular queue efficiently reuses space by connecting the end back to the start.

It uses front and rear pointers to manage adding and removing elements in constant time.

Ideal for fixed-size buffers like streaming data or task scheduling.

Prevents wasted space that happens in normal linear queues.

Commonly applied in hardware buffers and round-robin task management.