Design Circular Queue

MediumDesignLeetCode 622 ↗World 9-4

0:00 / 0:00

Build a fixed-size ring queue: keep a head index and a count, wrap every step with modulo, and each operation is constant time.

▼

The problem

LeetCode 622 (Medium). Implement MyCircularQueue(k), a FIFO queue with room for k items, with enQueue(value) (add at the back; false if full), deQueue() (remove from the front; false if empty), Front() and Rear() (the first and last items, -1 if empty), isEmpty() and isFull(), each in O(1).

Example (LeetCode's, walked through in scenes 2 and 6): MyCircularQueue(3), then enQueue(1) true, enQueue(2) true, enQueue(3) true, enQueue(4) false, Rear() 3, isFull() true, deQueue() true, enQueue(4) true, Rear() 4.

TRY IT ON LEETCODE ▶

The solution

class MyCircularQueue:
    def __init__(self, k):
        self.q, self.k = [0] * k, k
        self.head = self.count = 0
    def enQueue(self, value):
        if self.count == self.k: return False
        self.q[(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):
        if self.count == 0: return -1
        return self.q[self.head]
    def Rear(self):
        if self.count == 0: return -1
        return self.q[(self.head + self.count - 1) % self.k]
    def isEmpty(self): return self.count == 0
    def isFull(self): return self.count == self.k

Transcript

Design Circular Queue. Build a queue with room for k items: enqueue at the back, dequeue from the front, peek with Front and Rear, and check isEmpty and isFull. All in O of one.

Take k equals three. Enqueue one, two, three and four: true, true, true, then false. Rear gives three, and isFull, true. Dequeue, enqueue four, and Rear gives four.

The simple way is a plain list. Dequeue removes index zero, so every item behind it shifts forward: O of k. Never shifting just wastes the front.

The fix: bend the array into a wheel, with k slots, a head index and a count. Enqueue writes at head plus count, mod k. Dequeue moves head forward one, mod k. Rear is head plus count minus one, mod k. Count zero is empty; count k is full.

In code: enqueue checks for full, writes at the tail and bumps the count. Dequeue checks for empty, steps head and drops the count. Front reads the head slot; Rear, the slot before the tail.

Walking it: one, two and three board slots zero, one and two. Four finds the count at three: full, so false. Rear is slot two: three. Dequeue: one leaves, and head moves to slot one. Four boards at one plus two, mod three: slot zero, wrapping around. Rear is now four.

Each call is a few steps: O of one time, and O of k space.

Count the riders, write at head plus count, and wrap with mod k. That's Design Circular Queue.