Hack University
431/670

431. Design Circular Queue

Medium

Build a fixed-capacity FIFO queue that recycles its storage: when elements are dequeued from the front, the freed space becomes available again for new elements at the back — conceptually the buffer's end wraps around to its beginning. This structure is also called a ring buffer.

Implement a class MyCircularQueue constructed with the capacity k, supporting:

  • enQueue(value) — append value at the back. Returns true on success, false if the queue is full.
  • deQueue() — remove the front element. Returns true on success, false if the queue is empty.
  • front() — the front element, or -1 if the queue is empty.
  • rear() — the back element, or -1 if the queue is empty.
  • isEmpty() — whether the queue holds no elements.
  • isFull() — whether the queue holds k elements.

Every operation should run in O(1).

Example 1:

Input: MyCircularQueue(3); enQueue(10), enQueue(20), enQueue(30), enQueue(40), Rear(), isFull(), deQueue(), enQueue(40), Rear(), Front()

Output: [true, true, true, false, 30, true, true, true, 40, 20]

Explanation: The fourth enQueue fails because capacity is 3. After one deQueue frees the slot that held 10, enQueue(40) succeeds by reusing it — the back has wrapped around. The front is now 20.

Example 2:

Input: MyCircularQueue(1); isEmpty(), deQueue(), Front(), enQueue(7), isFull(), Front(), Rear(), deQueue(), Rear()

Output: [true, false, -1, true, true, 7, 7, true, -1]

Explanation: With capacity 1, a single element makes the queue full. Front and Rear on an empty queue return -1, and deQueue on an empty queue returns false.

Constraints:

  • 1 ≤ k ≤ 1000
  • 0 ≤ value ≤ 1000
  • At most 3000 operations per test.
  • Each operation must run in O(1) for the intended solution.

Hints:

A fixed array of size k plus some bookkeeping is enough — the trick is deciding what the bookkeeping is.

Keep a head index and a size counter. The back position is then (head + size − 1) mod k, and enQueue writes at (head + size) mod k.

The mod-k arithmetic is what makes the buffer "circular": indexes past the end wrap back to slot 0. The size counter cleanly separates full (size == k) from empty (size == 0), which raw head/tail pointers alone cannot.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: MyCircularQueue(3); enQueue(10), enQueue(20), enQueue(30), enQueue(40), Rear(), isFull(), deQueue(), enQueue(40), Rear(), Front()

Expected output: [true, true, true, false, 30, true, true, true, 40, 20]