Design Circular Queue: Array-Based Ring Buffer

Design Circular Queue is LeetCode problem 622. You need to build a queue with a fixed capacity that reuses array slots instead of shifting elements. The key mechanic is modular arithmetic: when a pointer reaches the end of the array, it wraps back to index 0. That wrap-around is what makes the queue "circular."

The problem

Implement the MyCircularQueue class with the following operations:

• MyCircularQueue(k) initializes the queue with a maximum size of k
• enQueue(value) inserts an element at the rear. Returns True if successful, False if the queue is full.
• deQueue() removes an element from the front. Returns True if successful, False if the queue is empty.
• Front() returns the front item. Returns -1 if the queue is empty.
• Rear() returns the rear item. Returns -1 if the queue is empty.
• isEmpty() returns True if the queue contains no elements.
• isFull() returns True if the queue contains k elements.

All operations must run in O(1) time.

Why circular?

A naive array-based queue has a problem. Every time you dequeue from the front, you either shift all remaining elements left (O(n) per dequeue) or you let the front pointer march forward and waste the space behind it. Eventually you run out of room even though the beginning of the array is empty.

A circular queue solves this by treating the array as a ring. When the rear pointer reaches the last index, the next enqueue places the element at index 0 (assuming that slot is free). The front pointer does the same thing when it advances past the end. No shifting, no wasted space.

The formula is simple: next_index = (current_index + 1) % k. That single modulo operation handles all the wrap-around logic.

The approach

You need three pieces of state alongside the array:

1. front - the index of the first element in the queue
2. rear - the index where the next element will be inserted (or the index of the last element, depending on your convention)
3. count - how many elements are currently in the queue

Using a count variable is the cleanest way to distinguish between "empty" and "full." Both states would otherwise look the same (front equals rear), which creates ambiguity if you only track two pointers. The count sidesteps that entirely.

On enQueue: check if the queue is full (count equals k). If not, place the value at the rear index, advance rear using modular arithmetic, and increment count.

On deQueue: check if the queue is empty (count is 0). If not, advance front using modular arithmetic and decrement count.

On Front and Rear: return the value at the front index or the index just before rear (accounting for wrap-around), or -1 if the queue is empty.

The solution

class MyCircularQueue:
    def __init__(self, k):
        self.data = [0] * k
        self.size = k
        self.front = 0
        self.rear = 0
        self.count = 0

    def enQueue(self, value):
        if self.isFull():
            return False
        self.data[self.rear] = value
        self.rear = (self.rear + 1) % self.size
        self.count += 1
        return True

    def deQueue(self):
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.size
        self.count -= 1
        return True

    def Front(self):
        if self.isEmpty():
            return -1
        return self.data[self.front]

    def Rear(self):
        if self.isEmpty():
            return -1
        return self.data[(self.rear - 1 + self.size) % self.size]

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == self.size

Let's break down the important details:

1. enQueue: places the value at self.rear, then moves rear forward with (self.rear + 1) % self.size. The modulo wraps rear back to 0 when it hits the end of the array.

2. deQueue: does not actually clear the old value. It just advances self.front. The old slot will get overwritten by a future enqueue. There is no need to zero it out.

3. Rear(): the last inserted element sits at (self.rear - 1 + self.size) % self.size. The + self.size prevents negative indices when rear is 0. Without it, (0 - 1) % k would give -1 in some languages.

4. isEmpty and isFull: both check the count. No ambiguity, no edge cases.

Step-by-step walkthrough

Let's trace through a full sequence of operations on a circular queue with capacity 3. Watch how the front and rear pointers move and how the wrap-around works when the array fills up.

The critical moment is Step 7. After the dequeue in Step 6 freed up index 0, the enqueue of 4 wraps the rear pointer around to the beginning of the array. The value 4 lands at index 0 even though it was inserted after values at indices 1 and 2. That is the circular buffer in action.

Complexity analysis

Time: every operation does a constant number of array accesses and arithmetic operations. No loops, no scanning.

Space: the array has exactly k slots. The three integer variables (front, rear, count) add O(1) overhead.

Building blocks

This problem exercises two fundamental patterns:

Modular arithmetic for wrap-around

The expression (index + 1) % k is the engine of the circular buffer. It maps any index to the range [0, k), so the pointer automatically wraps from the last slot back to the first. You will see this same trick in problems involving circular arrays, like rotating arrays, the Josephus problem, and circular linked list detection.

For the Rear() method, the backward version (index - 1 + k) % k handles the edge case where the index is 0. Adding k before taking the modulo ensures the result stays non-negative.

Array as a ring buffer

Instead of dynamically resizing or shifting elements, you fix the array size and let pointers chase each other around it. This is the same principle behind operating system I/O buffers, producer-consumer queues, and audio processing pipelines. The data stays put. Only the pointers move.

Edge cases

Before submitting, verify your solution handles these:

• Queue of capacity 1. enQueue, then enQueue again should fail. deQueue, then deQueue again should fail. Front and Rear return the same value.
• Alternating enQueue and deQueue. enQueue(1), deQueue, enQueue(2), deQueue. The front and rear pointers both advance and wrap correctly even with single-element cycles.
• Full queue then empty. Fill the queue to capacity, dequeue everything, then fill it again. The pointers may have wrapped multiple times. Make sure isEmpty and isFull still report correctly based on count.
• Rear() when rear is 0. After a wrap-around, rear points to index 0. Rear() must compute (0 - 1 + k) % k = k - 1 to find the last inserted element. Getting the arithmetic wrong here returns the wrong value.
• Front() and Rear() on empty queue. Both must return -1. Forgetting the empty check causes an out-of-bounds or stale-data bug.

From understanding to recall

The circular queue is one of those problems where the concept feels obvious but the implementation has subtle traps. Which direction do the pointers move? Does rear point to the next empty slot or the last filled slot? How do you compute Rear() without going negative? Is the full check count == k or front == rear?

These are small details, but under interview pressure, mixing up any one of them produces a broken solution. The code is only about 25 lines. Every line carries weight. The modular arithmetic in enQueue, the backward index in Rear(), the count-based full/empty checks. Miss one and specific test cases will fail.

Spaced repetition drilling locks in these mechanics. You write the implementation from scratch at increasing intervals until the pointer arithmetic and the count logic become muscle memory. That is the difference between "I know what a circular queue is" and "I can implement one correctly under a time limit."

Related posts

• Implement Queue Using Stacks - Another queue design problem where you build a FIFO structure from limited primitives
• Queues: First In, First Out - Deep dive into the queue data structure and FIFO ordering that underpins this problem
• LRU Cache - A harder design problem that also manages fixed-capacity storage with specific eviction rules

---

New to algorithms? Understand why O(1) operations matter with our Big O Notation Guide.