Circular Queue

Overview

A circular queue is a special type of queue that treats the underlying array as circular. When the rear reaches the end of the array, it wraps around to the beginning, allowing efficient use of space.

The Circular Structure

Instead of a linear array where space is wasted after dequeuing, a circular queue reuses empty spaces at the front. The front and rear pointers move through the array and wrap around when they reach the end, creating a circular path.

Why Use Circular Queues

In a regular queue implemented with an array, once items are removed from the front, that space is lost. A circular queue reuses that space, making it more memory-efficient for fixed-size queues that frequently enqueue and dequeue items.

Front and Rear Pointers

The circular queue uses two pointers: front points to the first element, and rear points to where the next element will be inserted. When enqueueing, rear moves forward. When dequeueing, front moves forward. Both wrap around using modulo arithmetic.

Checking Full and Empty

Distinguishing between a full and empty circular queue can be tricky since both conditions might look similar. Common solutions include keeping one slot always empty or using a counter to track the number of elements currently in the queue.