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 |