How do you approach Design Circular Queue?

You can back the queue with a fixed-size array plus a head index, a count, and the capacity. Or, for an O(1) clean implementation, a plain list works if you treat enQueue as append and deQueue as removing the front.

What is the time complexity of Design Circular Queue?

Time complexity: O(1) amortized per operation with a ring-buffer array.. Space complexity: O(k)..

What are common mistakes on Design Circular Queue?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

gitGood.dev

← Back to problems

Design Circular Queue

MediumObject-Oriented Design

Description

Design a circular queue (ring buffer) with a fixed capacity `k`. A circular queue reuses freed space at the front, so it never needs to shift elements. - `enQueue(value)` inserts an element; 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 element, or `-1` if empty. - `Rear()` returns the last element, or `-1` if empty. - `isEmpty()` returns whether the queue is empty. - `isFull()` returns whether the queue is full. Implement the function `circularQueue(k, operations)` where `k` is the capacity and `operations` is a list of `[op, ...args]`: `["enQueue", v]`, `["deQueue"]`, `["Front"]`, `["Rear"]`, `["isEmpty"]`, `["isFull"]`. Return the list of results, one per operation (use null for operations that return nothing - though every operation here returns a value).

Example 1

Input: k = 3, operations = [["enQueue",1],["enQueue",2],["enQueue",3],["enQueue",4],["Rear"],["isFull"],["deQueue"],["enQueue",4],["Rear"]]

Output: [true, true, true, false, 3, true, true, true, 4]

Example 2

Input: k = 2, operations = [["isEmpty"],["enQueue",1],["isEmpty"],["Front"],["Rear"]]

Output: [true, true, false, 1, 1]

Example 3

Input: k = 1, operations = [["enQueue",5],["isFull"],["deQueue"],["isEmpty"],["Front"]]

Output: [true, true, true, true, -1]

Constraints

1 <= k <= 1000. 0 <= value <= 1000. There are at most 3000 operations. Aim for O(1) per operation.

Design Circular Queue: approach, complexity and pitfalls

A medium design problem, graded against 6 test cases (3 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

More Designproblems →

If you are stuck

Show the 3-step hint ladder

You can back the queue with a fixed-size array plus a head index, a count, and the capacity. Or, for an O(1) clean implementation, a plain list works if you treat enQueue as append and deQueue as removing the front.
Track the current size so isFull (size === k) and isEmpty (size === 0) are O(1). Reject enQueue when full and deQueue when empty by returning false.
Front is the element at the head; Rear is the most recently enqueued element. Return -1 for either when the queue is empty.

The optimal approach

Show the approach: The approach

A circular queue can be modeled with a head pointer and a count over a fixed array, but the cleanest correct approach for this operation-list format is to keep an ordered list and a capacity check. `enQueue` appends only if `size < k` (else returns false). `deQueue` removes the front only if non-empty (else false). `Front`/`Rear` return the first/last element or -1 when empty. `isEmpty`/`isFull` compare size against 0 and k.

Time: O(1) amortized per operation with a ring-buffer array.
Space: O(k).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.