Circular buffer

Circular buffering makes a good implementation strategy for a queue that has fixed maximum size.

However, expanding a circular buffer requires shifting memory, which is comparatively costly.

For arbitrarily expanding queues, a linked list approach may be preferred instead.

[6] In this case, the buffer is empty if the start and end indexes are equal and full when the in-use size is Length − 1.

[8][disputed – discuss] (Naturally, the underlying buffer‘s length must then equal some multiple of the system’s page size.)

Reading from and writing to the circular buffer may then be carried out with greater efficiency by means of direct memory access; those accesses which fall beyond the end of the first virtual-memory region will automatically wrap around to the beginning of the underlying buffer.

When the read offset is advanced into the second virtual-memory region, both offsets—read and write—are decremented by the length of the underlying buffer.

[9] Fixed-sized compressed circular buffers use an alternative indexing strategy based on elementary number theory to maintain a fixed-sized compressed representation of the entire data sequence.

A ring showing, conceptually, a circular buffer. This visually shows that the buffer has no real end and it can loop around the buffer. However, since memory is never physically created as a ring, a linear representation is generally used as is done below.
A 24-byte keyboard circular buffer. When the write pointer is about to reach the read pointer—because the microprocessor is not responding—the buffer stops recording keystrokes. On some computers a beep would be played.
Circular buffer implementation in hardware, US patent 3979733, fig4