circular buffer Algorithm
A circular buffer, also known as a ring buffer or cyclic buffer, is a fixed-size data structure that efficiently manages a continuous stream of incoming data. The algorithm behind this buffer maintains a constant-sized queue of elements, where the oldest element is overwritten by the newest one when the buffer is full, providing a circular or wrap-around effect. This unique property makes circular buffers ideal for applications that require continuous data processing, such as audio/video streaming, network packet buffering, or data logging systems, where a fixed amount of the most recent data needs to be preserved.
The circular buffer algorithm utilizes two pointers, typically called the read and write pointers or head and tail, to manage the insertion and removal of elements. The write pointer is advanced as new data is written into the buffer, and the read pointer is advanced as data is read or consumed. When either pointer reaches the end of the buffer, it wraps around to the beginning, creating the circular effect. To determine if the buffer is empty or full, one can compare the positions of the read and write pointers. If both pointers are at the same position, the buffer is considered empty. If the write pointer is one position behind the read pointer, the buffer is considered full. This approach allows for efficient management of the buffer without the need for shifting data or resizing the data structure, leading to improved performance and reduced computational overhead.
//
// Queue: the entities in the collection are kept in
// order and the principal (or only) operations on the
// collection are the addition of entities to the rear
// terminal position
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/data-scructures/
// https://github.com/allalgorithms/cpp
//
// Contributed by: Carlos Abraham
// Github: @abranhe
//
#include <iostream>
#include <vector>
template <typename T, long SZ>
class circular_buffer
{
private:
T* m_buffer;
long m_index;
public:
circular_buffer()
: m_buffer {new T[SZ]()}
, m_index {0}
{
}
~circular_buffer()
{
delete m_buffer;
}
std::vector<T> get_ordered() noexcept
{
std::vector<T> vec;
for (long i = 0; i < SZ; ++i)
vec.push_back(m_buffer[(i + m_index) % SZ]);
return vec;
}
void push(T x) noexcept
{
m_buffer[m_index] = x;
m_index = (m_index + 1) % SZ;
}
};
int main()
{
circular_buffer<int, 4> buf;
buf.push(1);
buf.push(2);
buf.push(3);
buf.push(4);
buf.push(5);
buf.push(6);
for (auto x : buf.get_ordered())
std::cout << x << std::endl;
}
