Οδηγίες
Ο κυκλικός buffer, γνωστός και ως buffer δακτυλίου, είναι μια δομή δεδομένων που
χρησιμοποιεί έναν μοναδικό buffer σταθερού μεγέθους, σαν να ήταν συνδεδεμένος
από τη μια άκρη στην άλλη.
Αρχικά, ο κυκλικός buffer είναι κενός και έχει κάποιο προκαθορισμένο μήκος. Για
παράδειγμα, αυτός είναι ένας buffer 7 στοιχείων:
[ ][ ][ ][ ][ ][ ][ ]
Υπόθεσε ότι ένα 1 γράφεται στη μέση του buffer (η ακριβής θέση εκκίνησης δεν
έχει σημασία σε έναν κυκλικό buffer):
[ ][ ][ ][1][ ][ ][ ]
Στη συνέχεια υπόθεσε ότι προστίθενται δύο ακόμη στοιχεία, τα 2 και 3, τα οποία
προσαρτώνται μετά το 1:
[ ][ ][ ][1][2][3][ ]
Αν στη συνέχεια αφαιρεθούν δύο στοιχεία από τον buffer, αφαιρούνται οι
παλαιότερες τιμές μέσα στον buffer. Τα δύο στοιχεία που αφαιρούνται, στην
περίπτωση αυτή, είναι τα 1 και 2, αφήνοντας τον buffer με μόνο ένα 3:
[ ][ ][ ][ ][ ][3][ ]
Αν ο buffer έχει 7 στοιχεία, τότε είναι εντελώς γεμάτος:
[5][6][7][8][9][3][4]
Όταν ο buffer είναι γεμάτος, πετάει ένα σφάλμα, ειδοποιώντας τον πελάτη ότι
περαιτέρω εγγραφές είναι αποκλεισμένες μέχρι να ελευθερωθεί μια θέση.
Όταν ο buffer είναι γεμάτος, ο πελάτης μπορεί να επιλέξει να αντικαταστήσει τα
παλαιότερα δεδομένα με μια αναγκαστική εγγραφή. Σε αυτή την περίπτωση,
προστίθενται δύο ακόμη στοιχεία, τα A και B, και αντικαθιστούν τα 3 και 4:
[5][6][7][8][9][A][B]
Τα 3 και 4 έχουν αντικατασταθεί από τα A και B, με αποτέλεσμα το 5 να είναι
πλέον τα παλαιότερα δεδομένα στον buffer. Τέλος, αν αφαιρεθούν δύο στοιχεία,
τότε αυτό που θα επιστραφεί είναι τα 5 και 6, με αποτέλεσμα τον buffer:
[ ][ ][7][8][9][A][B]
Επειδή υπάρχει διαθέσιμος χώρος, αν ο πελάτης χρησιμοποιήσει ξανά την
αντικατάσταση για να αποθηκεύσει τα C και D, τότε θα χρησιμοποιηθεί ο χώρος
όπου ήταν αποθηκευμένα προηγουμένως τα 5 και 6, όχι η θέση των 7 και 8. Το 7
είναι ακόμα το παλαιότερο στοιχείο και ο buffer είναι για άλλη μια φορά
γεμάτος.
[C][D][7][8][9][A][B]
