Back to Study Material Data Structures and Algorithms

Circular Queue

A standard array-based queue with a front and rear pointer wastes memory as operations proceed. Each dequeue advances the front pointer, leaving positions ...

Circular Queue

Why Circular Queues Solve Array Queue Space Waste

A standard array-based queue with a front and rear pointer wastes memory as operations proceed. Each dequeue advances the front pointer, leaving positions behind it permanently unused even though the array has physical space there. After n total enqueues and dequeues where n equals the array size, the rear pointer reaches the end of the array and no further enqueues are possible even if the queue currently holds zero elements. A circular queue solves this by treating the array as a ring.

In a circular queue, both the front and rear pointers wrap around to index zero when they exceed the last index. The modulo operator achieves this: after an enqueue, rear becomes (rear + 1) modulo capacity. After a dequeue, front becomes (front + 1) modulo capacity. This reuses the positions vacated by previous dequeues without copying any elements.

Distinguishing between a full queue and an empty queue is the main challenge. Both states can have front equal to rear, making them indistinguishable if only those two pointers are maintained. Three common solutions exist: maintain a separate count of stored elements, leave one slot permanently empty so that full means (rear + 1) modulo capacity equals front while empty means front equals rear, or use a boolean flag to track whether the last operation was an enqueue or a dequeue.

The count approach is the most readable. isEmpty returns count equals zero. isFull returns count equals capacity. Enqueue checks isFull, stores at rear, advances rear with modulo, and increments count. Dequeue checks isEmpty, reads from front, advances front with modulo, and decrements count.

Time complexity is O(1) for all operations. Space complexity is O(n) for n element slots, with zero wasted space after any sequence of enqueues and dequeues.

Worked example: capacity 4, initially empty. Enqueue A at index 0, rear = 1. Enqueue B at index 1, rear = 2. Dequeue from index 0, front = 1. Enqueue C at index 2, rear = 3. Enqueue D at index 3, rear = 0. Queue is full: A is gone, front = 1, rear = 0, count = 3. Wait, correcting: after dequeue of A and three enqueues of B, C, D with capacity 4, front = 1, rear = 0, count = 3. Enqueue E at index 0 (rear), rear = 1, count = 4, queue is full.

Interview tip: when asked to implement a circular queue, state upfront which disambiguation strategy you will use (count, empty slot, or flag) and why. Choosing the count method and explaining it demonstrates clarity before touching the modulo arithmetic.

Circular Queue Implementation and Edge Cases

A complete circular queue implementation must handle initialization, the full state, the empty state, and the wraparound behavior of both pointers. Writing it cleanly under interview pressure requires understanding each edge case before writing code.

Initialize an array of the given capacity. Set front to zero, rear to zero, and count to zero. The capacity is stored as a constant used in every modulo operation.

Enqueue: if count equals capacity, the queue is full, raise an error or return false. Otherwise, store the element at index rear. Set rear to (rear + 1) modulo capacity. Increment count.

Dequeue: if count equals zero, the queue is empty, raise an error or return false or a sentinel. Otherwise, store the element at index front in a temporary variable. Set front to (front + 1) modulo capacity. Decrement count. Return the stored element.

Peek: if count equals zero, raise an error. Otherwise, return the element at index front without modifying any pointer or count.

isFull: return count equals capacity. isEmpty: return count equals zero.

The wraparound case for rear happens when rear is at the last valid index (capacity minus one) and an enqueue occurs. The modulo operation sets rear to zero, and the next element is stored at the beginning of the array. The element at index zero was previously dequeued and that slot is genuinely available. Verify this is only allowed when count is less than capacity; the count check prevents overwriting a valid element even if the index calculation would land on an occupied slot.

Worked example: capacity 3. Enqueue 10: arr=[10,_,_], front=0, rear=1, count=1. Enqueue 20: arr=[10,20,_], front=0, rear=2, count=2. Dequeue: returns 10, arr=[_,20,_], front=1, rear=2, count=1. Enqueue 30: arr=[_,20,30], front=1, rear=0, count=2. Enqueue 40: arr=[40,20,30], front=1, rear=1, count=3. Full. Dequeue: returns 20, front=2, count=2.

Interview tip: write a small table showing front, rear, and count after each operation alongside the array state. This table-driven approach catches pointer bugs before they become mysterious wrong answers and demonstrates methodical testing to your interviewer.

Circular Buffers in System Programming and Networking

Circular queues, often called ring buffers or circular buffers in systems programming contexts, are the standard mechanism for passing data between components operating at different speeds. They appear in device drivers, audio processing, network packet handling, and inter-process communication.

In audio processing, a sound card generates audio samples at a fixed hardware rate while the CPU processes them at a variable software rate. A ring buffer sits between them. The hardware writes new samples at the write pointer, advancing it after each write. The software reads samples at the read pointer, advancing it after each read. As long as the write pointer does not lap the read pointer (buffer overflow) and the read pointer does not catch the write pointer (buffer underrun), the system runs smoothly. Buffer overflow causes dropped samples; underrun causes silence or crackling.

In network drivers, packets arrive at the network interface card and are placed into a ring buffer in main memory. The operating system's driver reads packets from the buffer and passes them up the networking stack. The ring buffer absorbs short bursts of arriving packets that exceed the driver's immediate processing rate without requiring dynamic memory allocation per packet, which is too slow for high-speed networking.

Lock-free ring buffers are a specialized variant used in multi-producer, multi-consumer scenarios. When one writer and one reader share the buffer, no locking is required because the writer only modifies the write pointer and the reader only modifies the read pointer. With multiple concurrent writers or readers, atomic compare-and-swap operations on the pointers replace traditional mutex locking, reducing contention and improving throughput on multi-core hardware.

The power-of-two size optimization replaces the modulo operation with a bitwise AND: (index + 1) AND (capacity - 1). This works only when capacity is a power of two and is faster on hardware that lacks a fast modulo instruction.

Worked example: a serial port ring buffer of size 8 receives the bytes H, e, l, l, o at the write pointer. The CPU reads H and e while the next byte, comma, arrives. The buffer correctly interleaves reads and writes without dropping data, demonstrating the decoupling benefit.

Interview tip: if asked about ring buffers in a system design context, mention that choosing the buffer size requires balancing latency (small buffer responds quickly) against resilience to bursts (large buffer absorbs spikes). There is no universally correct size.