Описание тега circular-buffer

A circular buffer (AKA cyclic buffer, ring buffer, or circular queue) is a data structure that uses a single fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.

The circular buffer uses two pointers to indicate the current beginning and ending of the data on the buffer. The old/"First In" data is deleted from the buffer as it is read, moving forward the beginning pointer. New data is added at the end of the buffer (moving forward the corresponding pointer). The buffer physical storage is the same during all the operation if the reading speed is faster than the data acquisition process.

The useful property of a circular buffer is that it does not need to have its elements shuffled around when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well suited as a FIFO (first in first out) buffer while a standard, non-circular buffer is well suited as a LIFO (last in first out) buffer.

Circular buffering makes a good implementation strategy for a queue that has fixed maximum size. Should a maximum size be adopted for a queue, then a circular buffer is a completely ideal implementation; all queue operations are constant time. However, expanding a circular buffer requires shifting memory, which is comparatively costly. For arbitrarily expanding queues, a Linked list approach may be preferred instead.

Check http://en.wikipedia.org/wiki/Circular_buffer for more information.