A fixed-size FIFO queue backed by a ring buffer. When the buffer is full, new writes overwrite the oldest element in O(1) time.
A circular buffer uses a fixed-size array with two pointers — head (read position) and tail (write position). Both advance modularly through the array, wrapping around when they reach the end.
Index: [0] [1] [2] [3] [4]
Data: [C] [D] [_] [A] [B]
^tail ^head
When tail catches head (size == capacity), the next write overwrites the element at head and advances both pointers.
| Operation | Time | Space |
|---|---|---|
| append | O(1) | O(1) |
| pop | O(1) | O(1) |
| peek | O(1) | O(1) |
| getitem | O(1) | O(1) |
Space: O(n) where n = capacity (fixed at construction).
Audio/Video Streaming: Buffers incoming frames, discarding old ones when the consumer falls behind. The overwrite behavior is desirable — old frames are stale.
Embedded Systems: Fixed memory allocation with no dynamic resizing. Critical for real-time systems where malloc is forbidden.
Network Buffers: Packet capture ring buffers (e.g., libpcap) store the last N packets for analysis.
Log Buffers: Keep the last N log entries. When full, oldest entries are silently discarded.
Sliding Window Algorithms: Maintaining a window of the last K elements for moving averages, rate limiting, or protocol flow control.