MediumArrayLinked ListDesignQueueUpdated Sep 2026

622. Design Circular Queue

Asked at NVIDIA

Difficulty

Medium

Time

O(1) per operation

Space

O(k)

Pattern

Array

Companies

1

Problem

Design a fixed-size queue that uses a circular buffer (also called a ring buffer). A queue is FIFO: the first value you add is the first value you remove. The twist is that the storage is a circle — when you reach the last slot, the next slot is the first one again.

Implement a class MyCircularQueue with a constructor MyCircularQueue(k) that creates a queue holding at most k values. Support these methods:

  • enQueue(value) — add value at the back. Return true if it fits, false if the queue is already full.
  • deQueue() — remove the value at the front. Return true if something was removed, false if the queue was empty.
  • Front() — return the front value, or -1 if the queue is empty.
  • Rear() — return the back value, or -1 if the queue is empty.
  • isEmpty() — return true when there are no values.
  • isFull() — return true when the queue holds exactly k values.

You must build the storage yourself. Do not use your language's built-in queue or deque. Every operation should run in O(1) time, so you cannot shift elements around on each dequeue.

A queue in a circle of slots

buf123012frontrearAfter enQueue 1, 2, 3 the queue is full: front is 1,rear is 3buf423012frontrearAfter deQueue (1 leaves) and enQueue 4, the new valuewraps into slot 0
Capacity 3: values enter at the back and leave at the front, and the buffer wraps around.

Constraints

  • ●1 <= k <= 1000
  • ●0 <= value <= 1000
  • ●At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

Examples

Example 1
Input["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"] [[3], [1], [2], [3], [4], [], [], [], [4], []]
Output[null, true, true, true, false, 3, true, true, true, 4]
WhyCapacity is 3. Adding 1, 2, 3 succeeds and fills the queue. Adding 4 fails because the queue is full. Rear is 3. After deQueue removes 1, there is room again, so enQueue(4) succeeds and Rear becomes 4.

Asked At

1 companies
CompanyDifficulty
NVIDIAMediumView all NVIDIA questions →

How to Think About It

1

A plain array with pop(0) shifts every element: O(n) per dequeue. A ring buffer avoids shifting by letting indices wrap around.

2

Key insight: store a head index and a count. The tail slot is (head + count) % capacity. Tracking count avoids the classic ambiguity where head == tail could mean either empty or full.

3

enQueue: if full, return false; write at (head + count) % k and increment count. deQueue: if empty, return false; advance head = (head + 1) % k and decrement count.

4

Front is buf[head]; Rear is buf[(head + count - 1) % k]. Both return -1 when the queue is empty.

5

Walkthrough with capacity 3: enQueue 1, 2, 3 -> full, so enQueue 4 fails. Rear = 3. deQueue removes 1, head moves to index 1. enQueue 4 writes to index 0 (wraps). Rear = 4.

Optimal Approach

State: buf of size k, head = 0, count = 0.

enQueue(v): if count == k return false; buf[(head + count) % k] = v; count += 1; return true.
deQueue(): if count == 0 return false; head = (head + 1) % k; count -= 1; return true.
Front(): -1 if empty, else buf[head].
Rear(): -1 if empty, else buf[(head + count - 1) % k].
isEmpty(): count == 0. isFull(): count == k.

Time: O(1) per operation. Space: O(k).

head plus count

buf123012headcount = 3, k = 3: enQueue writes at (0 + 3) % 3 = 0but count == k, so it returns falsebuf123012headdeQueue drops buf[head] and moves head to (0 + 1) % 3= 1, count = 2buf423012headenQueue(4) writes at (1 + 2) % 3 = 0, count = 3; Rearreads (1 + 3 - 1) % 3 = 0tail slot = (head + count) % kRear = buf[(head + count - 1) % k]empty: count == 0, full: count == k
The tail slot is always (head + count) % k, so no shifting is ever needed.
ComplexityTime O(1) per operationSpace O(k)Each method touches a constant number of array slots; the O(k) space is the fixed buffer itself.

What Trips People Up in Real Interviews

1

Using only head and tail pointers without a count or a spare slot. Then head == tail is ambiguous between empty and full.

2

Forgetting the modulo when computing the rear index, which reads past the end after wrap-around.

3

Returning a stale value from Front/Rear on an empty queue instead of -1.

4

Using a dynamic list with pop(0). That is not a ring buffer and costs O(n) per dequeue.

Solution Code

O(1) per operation time
class MyCircularQueue:
    def __init__(self, k):
        self.buf = [0] * k
        self.k = k
        self.head = 0
        self.count = 0

    def enQueue(self, value):
        if self.count == self.k:
            return False
        self.buf[(self.head + self.count) % self.k] = value
        self.count += 1
        return True

    def deQueue(self):
        if self.count == 0:
            return False
        self.head = (self.head + 1) % self.k
        self.count -= 1
        return True

    def Front(self):
        return -1 if self.count == 0 else self.buf[self.head]

    def Rear(self):
        if self.count == 0:
            return -1
        return self.buf[(self.head + self.count - 1) % self.k]

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

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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Design Circular Queue problem?

Design Circular Queue asks you to implement a fixed-capacity FIFO queue backed by a ring buffer, supporting enqueue, dequeue, front, rear, and empty/full checks. It is a systems-flavored design question — ring buffers show up in network drivers, logging, and producer-consumer pipelines.

How do you solve Design Circular Queue?

The optimal approach runs in O(1) per operation time and O(k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Design Circular Queue?

Design Circular Queue is asked at NVIDIA. It is a medium difficulty problem.

What are common mistakes on Design Circular Queue?
  • Using only `head` and `tail` pointers without a count or a spare slot. Then `head == tail` is ambiguous between empty and full.
  • Forgetting the modulo when computing the rear index, which reads past the end after wrap-around.
  • Returning a stale value from `Front`/`Rear` on an empty queue instead of `-1`.
  • Using a dynamic list with `pop(0)`. That is not a ring buffer and costs `O(n)` per dequeue.