LeetCode 622: Design Circular Queue

Problem Restatement

We need to design a circular queue.

A queue follows FIFO order: first in, first out.

A circular queue uses a fixed-size array, but when the end of the array is reached, the next position wraps around to the beginning. This lets the queue reuse empty space created by earlier removals.

The class must support these operations:

Front() and Rear() return -1 when the queue is empty.

enQueue() returns False when the queue is full.

deQueue() returns False when the queue is empty.

Input and Output

Example class shape:

class MyCircularQueue:

    def __init__(self, k: int):
        ...

    def enQueue(self, value: int) -> bool:
        ...

    def deQueue(self) -> bool:
        ...

    def Front(self) -> int:
        ...

    def Rear(self) -> int:
        ...

    def isEmpty(self) -> bool:
        ...

    def isFull(self) -> bool:
        ...

Examples

Start with a circular queue of size 3.

q = MyCircularQueue(3)

Insert three values:

q.enQueue(1)  # True
q.enQueue(2)  # True
q.enQueue(3)  # True

Now the queue is full:

[1, 2, 3]
 front = 0
 size = 3

Trying to insert another value fails:

q.enQueue(4)  # False

The rear value is 3:

q.Rear()  # 3

The queue is full:

q.isFull()  # True

Remove the front value:

q.deQueue()  # True

Now 1 is removed. The front moves to 2.

[1, 2, 3]
    front = 1
    size = 2

Insert 4.

Because the array is circular, 4 goes into the old position at index 0.

q.enQueue(4)  # True

The logical queue is now:

2, 3, 4

The physical array may look like:

[4, 2, 3]
 front = 1
 size = 3

The rear value is now:

q.Rear()  # 4

First Thought: Use a Python List Directly

A simple queue can be written with a Python list:

queue.append(value)
queue.pop(0)

But pop(0) is O(n) because all later elements must shift left.

This problem asks us to design a fixed-size circular queue. We want each operation to run in constant time.

So we should not move elements around. Instead, we keep pointers.

Key Insight

Use a fixed array of length k.

Keep two pieces of state:

The rear index can be computed when needed.

If the queue has capacity capacity, then the next insertion position is:

(front + size) % capacity

The rear index is:

(front + size - 1) % capacity

The modulo operation is what makes the queue circular.

For example, if capacity = 3, then index 3 wraps to index 0:

3 % 3 == 0

Algorithm

Initialize:

self.queue = [0] * k
self.capacity = k
self.front = 0
self.size = 0

For enQueue(value):

1. If the queue is full, return False.
2. Compute the insertion index:

index = (self.front + self.size) % self.capacity

3. Store the value there.
4. Increase size.
5. Return True.

For deQueue():

1. If the queue is empty, return False.
2. Move front forward by one circular step:

self.front = (self.front + 1) % self.capacity

3. Decrease size.
4. Return True.

For Front():

1. If empty, return -1.
2. Return self.queue[self.front].

For Rear():

1. If empty, return -1.
2. Compute:

index = (self.front + self.size - 1) % self.capacity

3. Return self.queue[index].

For isEmpty():

return self.size == 0

For isFull():

return self.size == self.capacity

Correctness

The array has fixed length capacity, and all array accesses use modulo capacity. Therefore every computed position is a valid array index.

The variable front always points to the first logical element of the queue when the queue is not empty. Initially the queue is empty, so there is no front element. After the first successful insertion, the insertion index is (front + size) % capacity = 0, so the first element is stored at index 0, matching front.

For enQueue, the new value must be added after all existing queue elements. Since there are size elements starting at front, the next free logical position is front + size. Taking modulo capacity maps that logical position back into the fixed array. So the new value is placed at the correct rear position.

For deQueue, removing the front element means the next element becomes the new front. Advancing front by one circular step gives exactly that position. Decreasing size keeps the number of stored elements correct.

Front() returns the element at front, which is the first logical element by the invariant above.

Rear() returns the element at logical position front + size - 1, which is the last stored element. Taking modulo capacity gives its physical array index.

isEmpty() is correct because the queue has no elements exactly when size == 0.

isFull() is correct because the queue has used every available slot exactly when size == capacity.

Therefore all operations preserve the circular queue behavior.

Complexity

The full data structure uses O(k) space for the fixed array.

Implementation

class MyCircularQueue:

    def __init__(self, k: int):
        self.queue = [0] * k
        self.capacity = k
        self.front = 0
        self.size = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False

        index = (self.front + self.size) % self.capacity
        self.queue[index] = value
        self.size += 1

        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False

        self.front = (self.front + 1) % self.capacity
        self.size -= 1

        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1

        return self.queue[self.front]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1

        index = (self.front + self.size - 1) % self.capacity
        return self.queue[index]

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

    def isFull(self) -> bool:
        return self.size == self.capacity

Code Explanation

The array is allocated once:

self.queue = [0] * k

We do not grow or shrink it.

The queue capacity is stored separately:

self.capacity = k

The front pointer starts at index 0:

self.front = 0

The current queue has no elements:

self.size = 0

When inserting, we first reject the operation if the queue is full:

if self.isFull():
    return False

Then we compute the next insertion slot:

index = (self.front + self.size) % self.capacity

This slot may be at the end of the array, or it may wrap around to the beginning.

When deleting, we do not erase the old value. We only move the logical front:

self.front = (self.front + 1) % self.capacity

The old value can stay in the array because it is outside the logical queue. Future insertions may overwrite it.

The rear value is not stored as a separate pointer. It is computed from front and size:

index = (self.front + self.size - 1) % self.capacity

This keeps the state small and avoids pointer synchronization bugs.

Testing

def run_tests():
    q = MyCircularQueue(3)

    assert q.enQueue(1) is True
    assert q.enQueue(2) is True
    assert q.enQueue(3) is True
    assert q.enQueue(4) is False

    assert q.Rear() == 3
    assert q.isFull() is True

    assert q.deQueue() is True
    assert q.enQueue(4) is True

    assert q.Rear() == 4
    assert q.Front() == 2

    q2 = MyCircularQueue(1)
    assert q2.isEmpty() is True
    assert q2.Front() == -1
    assert q2.Rear() == -1
    assert q2.enQueue(10) is True
    assert q2.isFull() is True
    assert q2.enQueue(20) is False
    assert q2.Front() == 10
    assert q2.Rear() == 10
    assert q2.deQueue() is True
    assert q2.deQueue() is False
    assert q2.isEmpty() is True

    print("all tests passed")

run_tests()

Test meaning: