Design Circular Queue LeetCode 622 Guide

LeetCode 622 asks you to design a circular queue that supports six operations: MyCircularQueue(k) initializes the queue with capacity k; enQueue(value) inserts an element at the rear if not full; deQueue() removes the front element if not empty; Front() returns the front element without removing it; Rear() returns the rear element; isEmpty() returns true if the queue has no elements; and isFull() returns true when all k slots are occupied.

A circular queue, also called a ring buffer, is a linear data structure that reuses the same fixed array by wrapping the front and rear pointers around to index 0 when they reach the end of the array. This avoids the inefficiency of shifting elements on every dequeue, giving true O(1) operations for all six methods.

The challenge is managing the pointer arithmetic correctly — especially the Rear() access which must return the last filled slot, not the next empty slot — and handling the empty versus full distinction without ambiguity.

A naïve array queue shifts all elements left on every dequeue, which is O(n). A smarter approach uses a front pointer and advances it without shifting, but this causes the "front creep" problem: after many enqueue and dequeue cycles, the front pointer has advanced so far that the usable portion of the array shrinks even though elements were removed from the front.

A circular buffer solves this by treating the array as a ring. When the rear pointer reaches index k-1, the next enqueue wraps rear back to index 0 — if that slot was freed by an earlier dequeue. The array is always fully utilized, and no elements are ever moved. This is the fundamental insight behind ring buffers used in producer-consumer queues, audio buffers, and network packet queues.

The wrap-around is implemented with a single modulo operation: rear = (rear + 1) % k. This transforms a linear array into a conceptually circular structure. The same operation applies to the front pointer on dequeue: front = (front + 1) % k. Both pointers chase each other around the ring forever as long as the queue is used.

The circular queue needs three pieces of state: a front pointer (index of the first element), a rear pointer (index of the next empty slot), and a count of elements currently stored. Initialize all three to 0. Front and rear both start at index 0; count starts at 0 meaning the queue is empty.

The count variable cleanly resolves the classic ambiguity in circular buffers: when front == rear, does that mean the queue is empty or full? With a separate count, isEmpty() is simply count == 0 and isFull() is count == k. No slot is ever wasted, and the logic is unambiguous. Without count, you would need to waste one slot to distinguish the two cases — meaning a capacity-k queue would only store k-1 elements.

Some implementations compute the element count on the fly as (rear - front + k) % k, but this requires the wasted-slot convention and special-casing. Using an explicit count variable keeps all six methods simple and readable at the cost of one extra integer of state.

EnQueue first checks isFull() and returns false immediately if the queue has no room. Otherwise it writes value into data[rear], advances rear = (rear + 1) % k, increments count, and returns true. The write happens before the advance — rear always points to the next empty slot, not the last filled slot.

DeQueue first checks isEmpty() and returns false if there is nothing to remove. Otherwise it advances front = (front + 1) % k and decrements count, returning true. The data at the old front index does not need to be cleared — it will be overwritten naturally when rear wraps back around to that slot in a future enQueue.

Both operations are O(1) with no shifting, copying, or searching. The array indices never exceed k-1 because modular arithmetic constrains them. The count variable ensures the pointers never overtake each other — front never advances past rear and rear never overflows past front.

Front() returns data[front] if the queue is not empty, or -1 otherwise. This is straightforward because front always points to the oldest element still in the queue — the one that would be removed next by deQueue.

Rear() requires more care. Because rear points to the NEXT empty slot (one past the last filled slot), returning data[rear] would be wrong — it gives the next position to write, not the last position written. The correct formula is data[(rear - 1 + k) % k]. The +k before the modulo guards against the case where rear is 0: without it, (0 - 1) % k would be -1 in most languages, causing an index error.

This asymmetry between Front and Rear — one direct, one offset by one — is the most common source of bugs in circular queue implementations. Understanding that rear is always one ahead of the last element, and compensating with (rear - 1 + k) % k, is the key insight for the Rear() method.

The Python implementation stores the array as self.data = [0] * k, with self.front = self.rear = self.count = 0 and self.k = k. EnQueue writes self.data[self.rear] = value, advances rear with modulo, increments count. DeQueue advances front with modulo, decrements count. Front returns self.data[self.front]. Rear returns self.data[(self.rear - 1 + self.k) % self.k]. Both access methods check isEmpty() first. The whole class is about 20 lines.

The Java implementation uses an int[] data array, int front, rear, count, and int k in the constructor. All six methods mirror the Python logic. Java's % operator returns negative results for negative operands, so (rear - 1 + k) % k is essential — (rear - 1) % k alone would give -1 when rear == 0. Using k as the modulus base (not data.length) makes the +k guard correct since k == data.length.

A linked list alternative can implement the same interface using Node objects with next pointers. It avoids the fixed array allocation and supports dynamic capacity growth, but it uses more memory per element (pointer overhead) and has worse cache locality than the array version. For LeetCode 622 with fixed k, the array approach is preferred.

Design Hit Counter (LeetCode 362) also uses a circular buffer of fixed size 300 to store timestamps and counts, with a similar front/rear modular arithmetic pattern. The key difference is that hit counter buckets store aggregated counts rather than individual values, but the ring buffer technique is identical. Mastering LeetCode 622 makes the hit counter straightforward.

Implement Queue Using Stacks (LeetCode 232) explores a different constraint: building queue behavior from stack primitives. It highlights the FIFO versus LIFO distinction and the amortized O(1) trick of lazy-transfer between two stacks. Together with Design Circular Queue, these two problems give a complete picture of queue implementation tradeoffs.

LRU Cache (LeetCode 146) extends queue-like design thinking to a combined HashMap plus doubly linked list, supporting O(1) get and put with eviction. The Circular Queue, Hit Counter, and LRU Cache problems form a natural progression in data structure design — each adds one layer of complexity over the last and together they cover the core patterns asked in system design interviews.