Körkörös puffer

Utasítások

A körkörös puffer (ciklikus puffer vagy gyűrűpuffer) olyan adatszerkezet, amely egyetlen, rögzített méretű puffert használ úgy, mintha a végei össze lennének kapcsolva.

A körkörös puffer kezdetben üres, és valamilyen előre meghatározott hosszúságú. Például ez egy 7 elemű puffer:

[ ][ ][ ][ ][ ][ ][ ]

Tegyük fel, hogy egy 1-est írunk a puffer közepére (a pontos kezdőpozíció nem számít egy körkörös puffernél):

[ ][ ][ ][1][ ][ ][ ]

Ezután tegyük fel, hogy további két elem kerül hozzá, a 2 és a 3, amelyek az 1-es után fűződnek hozzá:

[ ][ ][ ][1][2][3][ ]

Ha ezután két elemet eltávolítunk a pufferből, a puffer legrégebbi értékei törlődnek. Ebben az esetben az eltávolított két elem az 1-es és a 2-es, így a pufferben csak a 3-as marad:

[ ][ ][ ][ ][ ][3][ ]

Ha a pufferben 7 elem van, akkor az teljesen tele van:

[5][6][7][8][9][3][4]

Amikor a puffer megtelik, hiba keletkezik, amely figyelmezteti a klienst, hogy a további írások mindaddig blokkolva vannak, amíg fel nem szabadul egy hely.

Ha a puffer tele van, a kliens úgy dönthet, hogy egy kényszerített írással felülírja a legrégebbi adatot. Ebben az esetben további két elem, az A és a B kerül hozzáadásra, és felülírják a 3-ast és a 4-est:

[5][6][7][8][9][A][B]

A 3-ast és a 4-est az A és a B váltotta fel, így most az 5-ös a puffer legrégebbi adata. Végül, ha két elemet eltávolítunk, akkor az 5-ös és a 6-os tér vissza eredményként, így a puffer a következő lesz:

[ ][ ][7][8][9][A][B]

Mivel van szabad hely, ha a kliens ismét a felülírást használja a C és a D tárolására, akkor az a hely kerül felhasználásra, ahol korábban az 5-ös és a 6-os volt, nem pedig a 7-es és a 8-as helye. A 7-es továbbra is a legrégebbi elem, és a puffer ismét megtelt.

[C][D][7][8][9][A][B]

---

Forrás

Wikipedia