Tampon circulaire

Instructions

Un tampon circulaire, tampon cyclique ou tampon annulaire est une structure de données qui utilise un unique tampon de taille fixe comme s'il était relié de bout en bout.

Au départ, un tampon circulaire est vide et possède une longueur prédéfinie. Par exemple, voici un tampon de 7 éléments :

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

Supposons qu'un 1 soit écrit au milieu du tampon (l'emplacement de départ exact n'a pas d'importance dans un tampon circulaire) :

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

Supposons ensuite que deux éléments supplémentaires, 2 et 3, soient ajoutés à la suite du 1 :

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

Si on retire ensuite deux éléments du tampon, ce sont les valeurs les plus anciennes du tampon qui sont retirées. Les deux éléments retirés, dans ce cas, sont 1 et 2, ce qui ne laisse que 3 dans le tampon :

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

Si le tampon contient 7 éléments, il est alors complètement plein :

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

Lorsque le tampon est plein, une erreur est levée, avertissant le client que les écritures suivantes sont bloquées jusqu'à ce qu'un emplacement se libère.

Lorsque le tampon est plein, le client peut choisir d'écraser les données les plus anciennes par une écriture forcée. Dans ce cas, deux éléments supplémentaires, A et B, sont ajoutés et écrasent les 3 et 4 :

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

Les 3 et 4 ont été remplacés par A et B, ce qui fait de 5 la donnée la plus ancienne du tampon. Enfin, si on retire deux éléments, ce qui serait renvoyé est 5 et 6, ce qui donne le tampon :

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

Comme de l'espace est disponible, si le client utilise à nouveau l'écrasement pour stocker C et D, c'est l'emplacement où 5 et 6 étaient stockés auparavant qui sera utilisé, et non celui de 7 et 8. 7 reste l'élément le plus ancien et le tampon est de nouveau plein.

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

---

Source

Wikipedia