キューとリングバッファについてやさしい言葉で解説してみる

TIGの仁木です。アルゴリズムとデータ構造連載の6日目です。

2020年の夏のLT大会でドーナツみたいという気分でリングバッファが好きと言ってしまったので、この連載でやさしい言葉で紹介してみようと思います。

リングバッファとは

キューに使われる構造で、一時領域（バッファ）が再利用できるように環状（リング）になったものです。キューとは何か解説しながら、なぜリングバッファが登場するかについて順に説明しようと思います。

キュー(FIFO)

キューは処理速度や並列度の異なるシステムの間で一時的にデータを貯めておく領域として利用されます。特徴として、最初に登録されたものが最初に取り出されるFirst-in First-outの考え方をもつ構造です。次に取り出される要素の場所と、次に登録されるべき場所（番号）を覚えているため、キューを探索せずにすぐに取り出すことができます。

待ち行列とも呼ばれていて、データに順番がついているためシステム間でデータの追い越しが発生しないという利点があります。回転寿司で例えると、最初に受付で紙に名前を書いた人が最初に席に案内されて寿司が食べられるイメージです。

ちなみに、よく対比されるデータ構造としてスタック（Last-in First-out)があります。最後に入った要素が最初に取り出されるような構造をしていて、身近なもので例えようとするとずるいと思ってしまう構造なのですが、入れ子構造の処理をする時に便利な構造で、（）がついた計算や、掛け算と足し算など、優先順位のある四則演算などに用いられるデータ構造です。

キューの話に戻って、寿司屋では、店員側では席に通したあとは、紙の名前を消していき消されていない一番上の人の名前を呼ぶようなオペレーションをとっているところが多いのではないでしょうか。人が増えると書けるところがなくなって、次の紙が必要となります。キューでも同じで、次の紙=新しい領域となり、領域が有限のコンピューター上では、領域が枯渇してしまう問題があります。そこで領域を再利用する方法がリングバッファという構造です。

リングバッファではデータの番号が最大の時で、最小の番号が空いている場合は次のデータの格納場所として上書き利用します。（寿司屋だと来店人数を調べる関係や紙の上書きの手間などで上書きしないほうがいいのかもしれませんが..）

ちなみにキューの中にデータが満タンになり、新しいデータを格納できない場合は、キューの手前のシステムで待ちが発生して遅くなったり、処理順序がおかしくなってしまったりするので、キューの後ろの処理速度を考慮して必要な分だけ深い（長い）キューを設計しておく必要があります。

まとめ

今回はキューとリングバッファについてやさしい言葉で解説してみました。

ハードウェア記述言語でシミュレーションまでしてみようかなと思っていたのですが、準備の都合でまた今度にします。

アルゴリズムやデータ構造はコンピュータの領域の制限や、計算時間の制限の中でどの方法を用いるのが効果的か考えて作られているもので、調べてみると結構面白いです。個人的には今回でいうと寿司屋の受付表のような身近なものと結びつけて考えたりできるのが楽しいので、もし読んでいて共感した方は多分調べてみると楽しいと思います。