Körkörös puffer

Utasítások

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

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őhely nem számít egy körkörös pufferben):

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

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

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

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

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

Ha a puffer 7 elemet tartalmaz, akkor teljesen tele van:

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

Amikor a puffer megtelt, hiba keletkezik, ami jelzi a kliensnek, hogy a további írások blokkolva vannak, amíg egy hely fel nem szabadul.

Amikor a puffer tele van, a kliens úgy dönthet, hogy egy kényszerített írással felülírja a legrégebbi adatokat. 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-at és a 4-et:

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

A 3-at és a 4-et felváltotta az A és a B, így most az 5 a legrégebbi adat a pufferben. Végül, ha két elemet eltávolítunk, akkor az 5-öt és a 6-ot kapnánk vissza, így a puffer:

[ ][ ][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 azt a helyet fogja használni, ahol korábban az 5 és a 6 volt, nem pedig a 7 és a 8 helyét. A 7 még mindig a legrégebbi elem, és a puffer ismét tele van.

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

---

Forrás

Wikipedia