Design Circular Queue

Difficulty: Medium Source: NeetCode

Problem

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”. Implement the MyCircularQueue class:

MyCircularQueue(k) — Initializes the object with the size of the queue k.

enQueue(value) — Inserts an element into the circular queue. Returns True if the operation is successful.

deQueue() — Deletes an element from the circular queue. Returns True if the operation is successful.

Front() — Gets the front item from the queue. Returns -1 if the queue is empty.

Rear() — Gets the last item from the queue. Returns -1 if the queue is empty.

isEmpty() — Checks whether the circular queue is empty or not.

isFull() — Checks whether the circular queue is full or not.

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]

Constraints:

1 <= k <= 1000

0 <= value <= 1000

At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, isFull

Prerequisites

Before attempting this problem, you should be comfortable with:

Modular Arithmetic — using % to wrap indices around a fixed-size array
Queue FIFO Semantics — elements are added at the rear and removed from the front
Fixed-Size Array — pre-allocating storage and using pointers to track bounds

1. Array with Head/Tail Pointers (Optimal)

A circular queue is just a fixed-size array where the front and rear pointers wrap around using modular arithmetic. Instead of shifting elements when we dequeue (which would be O(n)), we just move the head pointer forward. The “circle” just means index k-1 wraps back to index 0.

We track:

self.queue — the underlying array (pre-allocated with k slots)
self.head — index of the front element
self.count — how many elements are currently in the queue (simpler than tracking both head and tail without ambiguity)

The tail index is derived as (self.head + self.count - 1) % self.k.

Initial (k=3):
Queue: [_, _, _]
head=0, count=0

enQueue(1):
Queue: [1, _, _]
head=0, count=1

enQueue(2):
Queue: [1, 2, _]
head=0, count=2

enQueue(3):
Queue: [1, 2, 3]
head=0, count=3 (full!)

deQueue():  (removes front element, value=1)
head=1, count=2
Queue: [1, 2, 3]  (1 is still there but logically removed)

enQueue(4):
tail = (1 + 2) % 3 = 0
Queue: [4, 2, 3]  (overwrites old slot 0)
head=1, count=3

Front() = queue[head] = queue[1] = 2
Rear()  = queue[(1+3-1)%3] = queue[0] = 4

Algorithm

__init__(k): Allocate array of size k, set head = 0, count = 0, k = k.
enQueue(value): If full, return False. Write to (head + count) % k. Increment count. Return True.
deQueue(): If empty, return False. Advance head = (head + 1) % k. Decrement count. Return True.
Front(): If empty, return -1. Return queue[head].
Rear(): If empty, return -1. Return queue[(head + count - 1) % k].
isEmpty(): Return count == 0.
isFull(): Return count == self.k.

Solution

class MyCircularQueue:
    def __init__(self, k: int):
        self.k = k
        self.queue = [0] * k
        self.head = 0    # index of front element
        self.count = 0   # number of elements currently stored

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        tail_idx = (self.head + self.count) % self.k
        self.queue[tail_idx] = value
        self.count += 1
        return True

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

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.head]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        tail_idx = (self.head + self.count - 1) % self.k
        return self.queue[tail_idx]

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.k


# Test cases
q = MyCircularQueue(3)
print(q.enQueue(1))   # True
print(q.enQueue(2))   # True
print(q.enQueue(3))   # True
print(q.enQueue(4))   # False (full)
print(q.Rear())       # 3
print(q.isFull())     # True
print(q.deQueue())    # True
print(q.enQueue(4))   # True
print(q.Rear())       # 4
print(q.Front())      # 2

print("---")

# Test wrap-around
q2 = MyCircularQueue(2)
print(q2.enQueue(1))   # True
print(q2.enQueue(2))   # True
print(q2.isFull())     # True
print(q2.deQueue())    # True
print(q2.enQueue(3))   # True  (wraps to slot 0)
print(q2.Front())      # 2
print(q2.Rear())       # 3

print("---")

# Edge case: empty queue
q3 = MyCircularQueue(1)
print(q3.Front())     # -1
print(q3.Rear())      # -1
print(q3.deQueue())   # False
print(q3.enQueue(5))  # True
print(q3.Front())     # 5
print(q3.Rear())      # 5
print(q3.isFull())    # True

Complexity

Time: O(1) — all operations are O(1) with modular arithmetic
Space: O(k) — fixed array of size k

2. Linked List Approach

Intuition

Alternatively, we can use a doubly linked list with a count. enQueue appends to the tail and deQueue removes from the head. No modular arithmetic needed, but we have node allocation overhead. This is cleaner conceptually but slightly more memory-intensive due to pointer overhead per node.

Solution

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class MyCircularQueue:
    def __init__(self, k: int):
        self.k = k
        self.count = 0
        self.head = None  # front of queue
        self.tail = None  # rear of queue

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        node = Node(value)
        if self.tail:
            self.tail.next = node
        self.tail = node
        if not self.head:
            self.head = node
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.head = self.head.next
        if not self.head:
            self.tail = None
        self.count -= 1
        return True

    def Front(self) -> int:
        return self.head.val if self.head else -1

    def Rear(self) -> int:
        return self.tail.val if self.tail else -1

    def isEmpty(self) -> bool:
        return self.count == 0

    def isFull(self) -> bool:
        return self.count == self.k

# Test
q = MyCircularQueue(3)
print(q.enQueue(1), q.enQueue(2), q.enQueue(3))  # True True True
print(q.enQueue(4))   # False
print(q.Rear())       # 3
print(q.deQueue())    # True
print(q.enQueue(4))   # True
print(q.Rear())       # 4

Complexity

Time: O(1) — all operations are O(1)
Space: O(k) — at most k nodes allocated

Common Pitfalls

Using head == tail to check empty/full — it’s ambiguous. If head and tail point to the same index, you can’t tell if the queue is empty or full. That’s why tracking count separately (or keeping one slot always empty) is the standard solution.

Forgetting modular arithmetic. When the tail index reaches k-1, the next enQueue should write to index 0. Always compute tail as (head + count) % k — never just count.

Off-by-one in Rear(). Rear is (head + count - 1) % k, not (head + count) % k. The -1 is because count elements occupy indices head through head + count - 1.

Keyboard shortcuts

Note Book