循環バッファ

概要 「配列リスト」は、 要素へのランダムアクセスが非常に高速という利点がある一方、 末尾以外への要素の挿入が極端に遅いという欠点がありました。 用途によってはこれでも十分なのですが、 ある用途においては、末尾だけでなく先頭にも要素の挿入・削除を行いたい場合があります。 そこで、先頭と末尾の要素の挿入・削除を高速に（オーダー O(1) で）行えるデータ構造として、 循環バッファ（circular buffer）という物が考えられています。 循環バッファはリングバッファ（ring buffer）等とも呼ばれます。 循環バッファは、その名前の通り、 配列の先頭と末尾を繋いだ環のようなイメージのデータ構造です（図1）。 循環バッファ 特徴 循環バッファは以下のような利点を持っています。 「配列リスト」と同様に、高速な（オーダー O(1)）ランダムアクセスが可能。 先頭および末尾への要素の追加・削

[W53SA]

リングバッファ

[yowano]

O(1)でランダムアクセスが可能で、且つ先頭および末尾への要素の追加・削除がO(1)で行える環状のバッファを作成する方法。