Design Circular Queue
Core idea: A queue on a fixed array runs off the end as you enqueue and dequeue — unless you glue the end back to the start. Track
head, asize, and step indices with% capacity, and a single pre-allocated array becomes an O(1) FIFO that never moves an element and never wastes a slot.
1. The problem, in a fresh setting
You're writing the driver for a network interface card (NIC). The hardware and your driver share a fixed ring of k pre-allocated packet slots: the NIC enqueues arriving packets at the tail, your driver dequeues them from the head. You may not allocate per packet (it's a hot path and memory is fixed), and you must answer—in constant time—"what's at the head?", "what's at the tail?", "is it empty?", "is it full?".
Implement MyCircularQueue with:
| Operation | Meaning |
|---|---|
MyCircularQueue(k) |
create a ring holding up to k items |
enQueue(x) |
add x at the rear; return False if full |
deQueue() |
remove the front item; return False if empty |
Front() / Rear() |
peek front / rear value, or -1 if empty |
isEmpty() / isFull() |
status checks |
Example (capacity 3):
| Call | Returns | Ring (front→rear) |
|---|---|---|
enQueue(10) |
True |
[10] |
enQueue(20) |
True |
[10,20] |
enQueue(30) |
True |
[10,20,30] |
enQueue(40) |
False |
full |
deQueue() |
True |
[20,30] |
enQueue(40) |
True |
[20,30,40] (40 wrapped into slot 0) |
Rear() |
40 |
[20,30,40] |
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson