Design Circular Queue
Medium · Stack & Strings · Array · Linked List · Design · Queue
Problem
Implement a fixed-capacity first-in, first-out queue stored in a ring buffer: the slot after the last one wraps around to the first, so space freed at the front is reused at the back. Do not use a built-in queue type.
Implement MyCircularQueue:
- MyCircularQueue(k) creates a queue that holds at most k elements.
- enQueue(value) adds value at the rear; returns True on success, False if the queue is full.
- deQueue() removes the front element; returns True on success, False if the queue is empty.
- Front() / Rear() return the front / rear element, or -1 if the queue is empty.
- isEmpty() and isFull() report the queue's state.
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments.
Examples
Input: ops = ["MyCircularQueue","enQueue","enQueue","enQueue","Rear","deQueue","enQueue","Front","Rear","isFull"], args = [[2],[5],[6],[7],[],[],[8],[],[],[]] Output: [None, True, True, False, 6, True, True, 6, 8, True]
The third enQueue fails at capacity 2. After 5 is removed, 8 goes into the freed slot.
Input: ops = ["MyCircularQueue","Front","deQueue","isEmpty"], args = [[1],[],[],[]] Output: [None, -1, False, True]
An empty queue has no front and nothing to remove.
Constraints
- 1 <= k <= 1000
- 0 <= value <= 1000
- At most 3000 calls are made in total
Approaches
- Baseline: a list that shifts on every removal — time O(k) for deQueue, O(1) for the rest, space O(k)
Follow-up
What if elements can be added and removed at both ends? The head then also steps backwards, (head - 1 + k) % k, and the same array serves as a double-ended queue: see the use case “A ring buffer open at both ends”. A full ring buffer is also a sliding window, as in “Moving average over the last k values”.
Related problems
Start free on Cariara · Coding problems · System design studio
