Queues & Design · 140Medium
Design Circular Queue
Design a circular queue of fixed capacity: enQueue(value), deQueue(), Front(), Rear(), isEmpty() and isFull(). The unused space in front of the queue must be reusable.
Constraints
- 1 <= k <= 1000
- 0 <= value <= 1000
- At most 3000 calls are made.
- API
- new MyCircularQueue(k) initialize the queue with capacity k
- enQueue(value) -> boolean insert value at the rear; return whether it succeeded
- deQueue() -> boolean delete the element at the front; return whether it
- succeeded
- Front() -> number return the front element, or -1 if the queue is empty
- Rear() -> number return the rear element, or -1 if the queue is empty
- isEmpty() -> boolean return true if the queue is empty
- isFull() -> boolean return true if the queue is full
Examples
const q = new MyCircularQueue(3); q.Front() -> -1 // empty queue q.enQueue(1) -> true q.enQueue(2); q.enQueue(3); q.enQueue(4) -> false // full q.deQueue(); q.enQueue(4) -> true // space reused, the index wraps to slot 0 q.Front() -> 2 q.Rear() -> 4
Edge cases
- Front and Rear on an empty queue return -1.
Show the target complexity (spoiler)
- Naive
- Shifting all elements on dequeue is O(n) per operation.
- Target
- O(1) per operation — a fixed array with head and tail indices advanced modulo capacity, plus a size field.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/17-queues-and-design/140-design-circular-queue.js ./practice c 140