622. Design Circular Queue

Problem¶

Implement a fixed-capacity FIFO queue without a built-in queue:

enQueue(value) and deQueue() return whether the operation succeeded.
Front() and Rear() return the first and last values, or -1 when empty.
isEmpty() and isFull() report the queue’s state.
Reuse freed slots by wrapping around the underlying array.

Capacity = 2
Operation      Result   Queue (front → rear)
enQueue(10)    True     [10]
enQueue(20)    True     [10, 20]
enQueue(30)    False    [10, 20]
deQueue()      True     [20]
enQueue(30)    True     [20, 30]
Front()        20       [20, 30]
Rear()         30       [20, 30]

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:

Key trick¶

Track only the front index and element count; modulo arithmetic gives both the next insertion position and the rear position.

Trap¶

Equal indices can mean either empty or full; use a count to distinguish them.
Wrap indices with modulo instead of shifting elements.
Check emptiness before reading; removed values can remain in the array.

Why is it interesting?¶

A logical FIFO sequence can wrap across a physical array while every operation stays constant-time.

Python solution¶

class MyCircularQueue:
    def __init__(self, k: int):
        self.values = [0] * k
        self.capacity = k
        self.head = 0
        self.size = 0

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

        # The next free slot follows the current logical sequence.
        idx = (self.head + self.size) % self.capacity
        self.values[idx] = value
        self.size += 1
        return True

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

        # Advancing the head removes the value logically; no clearing needed.
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return True

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

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        idx = (self.head + self.size - 1) % self.capacity
        return self.values[idx]

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

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

Time: \(O(k)\) initialization; \(O(1)\) per operation. Space: \(O(k)\).

Comment on my solution¶

Your solution is correct, with \(O(1)\) operations and \(O(k)\) space.

The size == 1 adjustment in deQueue() is redundant: after removing from a two-element queue, first already equals last.
Keeping both first and last works, but last can be derived from first and size, reducing bookkeeping.
Leaving deleted values in the array is safe because size determines which slots are valid.

# Ideas
# [.,.,.]
# [1,.,.] enque 1
# [1,2,.] enque 2
# [1,2,3] enque 3
# [1,2,3]
# [.,2,3] deque
# [.,.,3] deque
# where to enque?
# - maybe use a doubly linked list with sentinel at both
#   ends like LRU cache implementation
#   - with a size
#   - and 2 pointers for where to deque and where to enqueue
#
# [.,.,.]
# [1,.,.] enque 1
# [1,2,.] enque 2
# [1,2,3] enque 3
# [1,2,3]
# [2,3,.] deque
# [3,.,.] deque
#
# [1,2,.]
#  f l
# [.,2,.]
#    fl
# [.,.,.]
#    l f

# WORKS
class MyCircularQueue:
    def __init__(self, k: int):
        self.length = k
        self.size = 0
        self.first = -1
        self.last = -1
        self.values = [-1] * k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.last = (self.last + 1) % self.length
        self.values[self.last] = value
        self.size += 1
        if self.size == 1:
            self.first = self.last
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.first = (self.first + 1) % self.length
        self.size -= 1
        if self.size == 1:
            self.last = self.first
        return True


    def Front(self) -> int:
        return -1 if self.isEmpty() else self.values[self.first]

    def Rear(self) -> int:
        return -1 if self.isEmpty() else self.values[self.last]

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

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