circular buffer

In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer 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. There were early circular buffer implementations in hardware.

In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer 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. There were early circular buffer implementations in hardware. This image shows a partially full buffer with Length = 7: This image shows a full buffer with four elements (numbers 1 through 4) having been overwritten: In the beginning the indexes end and start are set to 0. The circular buffer write operation writes an element to the end index position and the end index is incremented to the next buffer position. The circular buffer read operation reads an element from the start index position and the start index is incremented to the next buffer position. The start and end indexes alone are not enough to distinguish between buffer full or empty state while also utilizing all buffer slots, but can be if the buffer only has a maximum in-use size of Length − 1. 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. Another solution is to have another integer count that is incremented at a write operation and decremented at a read operation. Then checking for emptiness means testing count equals 0 and checking for fullness means testing count equals Length. The following source code is a minimal C++ implementation. push() puts an item in the buffer, pop() gets an item from the buffer. Both functions take care about the capacity of the buffer: import std; using std::array; using std::runtime_error; template class CircularBuffer { private: array data{}; size_t head = 0; size_t tail = 0; size_t size = 0; public: bool isEmpty() const noexcept { return size == 0; } bool isFull() const noexcept { return size == N; } size_t getSize() const noexcept { return size; } void push(const T& value) { if (isFull()) { throw runtime_error("Buffer is full"); } data[tail] = value; tail = (tail + 1) % N; ++size; } T pop() { if (isEmpty()) { throw runtime_error("Buffer is empty"); } T value = data[head]; head = (head + 1) % N; --size; return value; } T peek() const { if (isEmpty()) { throw runtime_error("Buffer is empty"); } return data[head]; } }; int main() { CircularBuffer buffer; buffer.push(1); buffer.push(2); buffer.push(3); std::println("{}", buffer.pop()); // prints 1 buffer.push(4); while (!buffer.isEmpty()) { std::println("{}", buffer.pop()); } }

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373518894 under CC BY-SA 4.0; modifications have been made.