リングバッファ

説明

循環バッファ、サイクリックバッファ、リングバッファは、単一の固定サイズのバッファを、端と端がつながっているかのように使うデータ構造です。

循環バッファは最初は空で、あらかじめ決められた長さを持っています。たとえば、7要素のバッファは次のようになります。

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

バッファの中央に1が書き込まれたとします（循環バッファでは、正確な開始位置は問題になりません）。

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

次に、さらに2つの要素、2と3が追加され、1の後ろに付け加えられたとします。

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

ここで2つの要素をバッファから取り除くと、バッファの中で最も古い値が取り除かれます。この場合、取り除かれる2つの要素は1と2で、バッファには3だけが残ります。

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

バッファに7つの要素が入ると、完全にいっぱいになります。

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

バッファがいっぱいのときはエラーが発生し、空きができるまでそれ以上の書き込みがブロックされることをクライアントに知らせます。

バッファがいっぱいのときは、強制的な書き込みによって最も古いデータを上書きすることを選べます。この場合、さらに2つの要素AとBが追加され、3と4を上書きします。

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

3と4がAとBに置き換わり、5がバッファの中で最も古いデータになりました。最後に、2つの要素を取り除くと、返されるのは5と6で、バッファは次のようになります。

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

空きがあるので、クライアントが再び上書きでCとDを格納すると、7と8の位置ではなく、以前5と6が格納されていた場所が使われます。7は依然として最も古い要素で、バッファは再びいっぱいになります。

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

---

出典

Wikipedia