circular buffer (tsz. circular buffers)
A circular buffer célja:
állandó idejű hozzáférés, hatékony memóriahasználat → különösen akkor, ha az adatmennyiség folyamatos, de korlátozott méretű (pl. szenzoradatok, hangfeldolgozás, hálózati pufferelés).
A puffer egy fix méretű tömb:
↑ ↑
write read
write_index: ide írjuk az új elemet.read_index: innen olvassuk a következő elemet.write_index eléri a végét → visszateker az elejére.
write_index pozícióra.write_index-et: write_index = (write_index + 1) % capacity.
read_index pozícióról.read_index-et ugyanúgy.
| Előny | Miért jó? |
|---|---|
| ⚡ Gyors | O(1) írás és olvasás |
| 🧠 Egyszerű | Csak indexek mozognak |
| 📏 Fix méretű | Nincs új memóriafoglalás |
| 🔁 Ciklikus | Jó streaming, real-time adatokhoz |
| write == read | Állapot |
|---|---|
| Igen, és üres | Üres |
| Igen, és nem olvastunk ki mindent | Tele (túlcsordulás figyelendő!) |
| Nem | Részlegesen telt |
Gyakori trükk: a puffer mérete +1 legyen, és sose töltjük teljesen tele, így könnyen eldönthető, mikor üres vagy teli.
class CircularBuffer {
vector<int> buffer;
int head = 0, tail = 0, size = 0;
int capacity;
public:
CircularBuffer(int cap) : buffer(cap), capacity(cap) {}
bool isEmpty() const { return size == 0; }
bool isFull() const { return size == capacity; }
void push(int val) {
if (isFull()) throw overflow_error("Buffer full");
buffer = val;
tail = (tail + 1) % capacity;
++size;
}
int pop() {
if (isEmpty()) throw underflow_error("Buffer empty");
int val = buffer;
head = (head + 1) % capacity;
--size;
return val;
}
};
| Tulajdonság | Circular Buffer |
|---|---|
| Sorrendiség | FIFO |
| Méret | Fix |
| Ciklusos indexelés | ✅ |
| Használat | Streaming, valós idejű rendszerek |
| Komplexitás | O(1) minden műveletre |