Sign in to watch this lesson
Algorithms - Linear Data Structures · 3:58
Queues, Deques and Ring Buffers
A queue hands items out in the order they arrived. We draw a capacity-8 ring buffer as a clock face: ticks 101 to 108 fill it, 109 has to wait, two reads free slots and the producer wraps from slot 7 back to slot 0. Two ever-growing counters tell full from empty, and a power-of-two mask picks the slot; on this Mac the mask beat a general modulo and the ring beat std::queue. Then libc++'s std::deque: 4 KB blocks and a map of pointers, a new block on push_front, stable references, slower scans than a vector, plus a queue made of two stacks.
You will learn
- Implement a fixed-capacity ring buffer with two monotonically increasing counters, telling full from empty by tail - head
- Explain why power-of-two capacities let slot = counter & (C - 1) replace a modulo, and what breaks otherwise
- Describe how libc++'s std::deque stores blocks plus a map, why references survive pushes at the ends and why scans are slower than a vector's
- Build a FIFO queue from two stacks and argue its amortised O(1) cost