Lesson 10.2 · Queue, Deque and Monotonic Queue
Circular Buffers
A fixed array where the front and back indexes wrap around with % capacity, so no element ever has to shift.
12 min
Think of it like this
A revolving sushi belt with a fixed number of plates: the chef adds plates at one point, diners take them at another, and both points keep moving round the same loop.
1.Head, size and wrap-around
Keep head (index of the front) and size. The back position is (head + size) % capacity. Enqueue writes there and increments size; dequeue advances head = (head + 1) % capacity and decrements size. Nothing moves, so every operation is O(1).
enqueue 1, 2, 3; dequeue; enqueue 41
0↑head
2
13
2State(vars)
size = 3 (full)
Step 1/3After three enqueues the buffer is full.
Remember
- back = (head + size) % capacity.
- Track size to tell full from empty.
- No shifting: O(1) per operation.
Common mistakes
- Using only head and tail indexes without a size or an empty slot: full and empty look the same.