Design Circular Queue — Ring Buffer Implementation

Problem Statement#

Design a circular queue with fixed capacity supporting: enQueue(value) inserts at the rear (returns false if full); deQueue() removes from the front (returns false if empty); Front() and Rear() peek at front/rear (-1 if empty); isEmpty() and isFull() check state.

Constraints:

• 1 <= k <= 1000 (capacity)
• 0 <= value <= 1000
• At most 3000 calls total

Input:  k=3, enQueue(1), enQueue(2), enQueue(3), enQueue(4), Rear(), isFull(), deQueue(), enQueue(4), Rear()
Output: true, true, true, false, 3, true, true, true, 4

Input:  k=1, enQueue(5), enQueue(5), Rear()
Output: true, false, 5

Why This Problem Matters#

Circular buffers (ring buffers) are one of the most widely used data structures in systems programming. Embedded real-time systems, network driver packet queues, audio buffer management, and OS kernel I/O ring buffers (like Linux's io_uring) all use this design. Amazon's DynamoDB streaming, Kinesis consumer shards, and Apache Kafka's internal log segments all implement ring buffer semantics.

This problem appears in Amazon and embedded systems interviews because it tests your understanding of modular arithmetic for wrapping indices, and your ability to design a fixed-memory structure that avoids dynamic allocation. Candidates who implement this correctly demonstrate familiarity with systems-level thinking.

The distinction between empty and full states (both of which have head == tail in naive implementations) must be resolved explicitly—typically with a size counter or by sacrificing one slot.

The Core Insight#

Use a fixed-size array with head (front pointer), tail (rear pointer), and size counter. Advance pointers with (pointer + 1) % k to wrap around. Track size separately to distinguish empty (size == 0) from full (size == k)—this avoids the ambiguity of the one-slot-wasted approach.

enQueue: if full, return false; if empty, set both head and tail to 0; else advance tail; write value; increment size. deQueue: if empty, return false; decrement size; if now empty, reset both pointers; else advance head.

The modular arithmetic is the key implementation detail: indices wrap seamlessly so no explicit boundary checking is needed beyond the full/empty guards.

Visual Dry Run#

Solution (Optimal)#

class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [0] * k
        self.head = self.tail = -1
        self.size = 0
        self.k = k
 
    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        if self.isEmpty():
            self.head = self.tail = 0
        else:
            self.tail = (self.tail + 1) % self.k
        self.q[self.tail] = value
        self.size += 1
        return True
 
    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.size -= 1
        if self.size == 0:
            self.head = self.tail = -1
        else:
            self.head = (self.head + 1) % self.k
        return True
 
    def Front(self) -> int:
        return -1 if self.isEmpty() else self.q[self.head]
 
    def Rear(self) -> int:
        return -1 if self.isEmpty() else self.q[self.tail]
 
    def isEmpty(self) -> bool:
        return self.size == 0
 
    def isFull(self) -> bool:
        return self.size == self.k

class MyCircularQueue {
    constructor(k) {
        this.q = new Array(k);
        this.h = this.t = -1;
        this.sz = 0;
        this.k = k;
    }
 
    enQueue(v) {
        if (this.isFull()) return false;
        if (this.isEmpty()) this.h = this.t = 0;
        else this.t = (this.t + 1) % this.k;
        this.q[this.t] = v;
        this.sz++;
        return true;
    }
 
    deQueue() {
        if (this.isEmpty()) return false;
        this.sz--;
        if (this.sz === 0) this.h = this.t = -1;
        else this.h = (this.h + 1) % this.k;
        return true;
    }
 
    Front() { return this.isEmpty() ? -1 : this.q[this.h]; }
    Rear()  { return this.isEmpty() ? -1 : this.q[this.t]; }
    isEmpty() { return this.sz === 0; }
    isFull()  { return this.sz === this.k; }
}

Time: O(1) for all operations
Space: O(k) — fixed-size array regardless of operations performed

Common Mistakes#

• Not resetting head and tail to -1 after the last element is dequeued—Front() and Rear() would return stale values
• Advancing tail before checking if the queue is empty—on the first enqueue, both head and tail must start at index 0
• Using head == tail to detect both empty and full—this is ambiguous; always use a size counter or one-slot sacrifice
• Forgetting the modulo wrap: tail = (tail + 1) % k not tail = tail + 1
• Returning 0 instead of -1 from Front() and Rear() when the queue is empty

Interview Tips#

• Draw the ring buffer as a circle with arrows advancing clockwise—this makes the modulo wrap immediately visual
• Explain the empty/full ambiguity upfront and state which resolution you chose (size counter is cleanest)
• Mention the real-world use cases: Linux io_uring, network card DMA rings, and OS scheduler run queues are all ring buffers
• For thread safety follow-up: atomic increment of head and tail with memory fences is the lock-free producer-consumer pattern

Follow-up Questions#

• How would you make this thread-safe for a single producer and single consumer? (Lock-free ring buffer: producer advances tail atomically, consumer advances head atomically, no locks needed when indices are independent)
• How would you implement a deque (double-ended queue) using a circular array? (Advance head backward for front insert, advance tail backward for rear remove, using same modulo arithmetic)
• How does Linux io_uring use a ring buffer? (Two rings: submission queue from user to kernel, completion queue from kernel to user—both are lock-free circular buffers)
• What happens if you use (tail - head + k) % k == 0 to check empty? (Ambiguous with full; this is why size counter or one wasted slot is preferred)
• How would you grow the ring buffer dynamically when full? (Copy elements in order from head to a new larger array, reset head to 0 and tail to old size)

Key Takeaways#

• A circular queue uses a fixed array with head and tail pointers advanced via (ptr + 1) % k
• Use a size counter to distinguish empty (size == 0) from full (size == k) without ambiguity
• On the first enQueue, initialise both head and tail to 0; on the last deQueue, reset both to -1
• All operations are O(1); space is exactly O(k) regardless of how many operations are performed
• The ring buffer pattern is used in Linux io_uring, network packet queues, audio buffers, and OS scheduler run queues
• For lock-free concurrent use, a single producer and single consumer can operate on head and tail independently without locks
• Always return -1 (not 0 or null) from Front() and Rear() when the queue is empty