| 「キュー」は、よくスタックとセットで語られるデータ構造です。 | ||
| スタックはデータが積み重ねられるイメージで、後から入れられたデータが先に取り出されますが、キューでは先に入れたデータが先に取り出されます。これを FIFO(First In/First Out) と呼びます。スタックが LIFO だったのを思い出してください。 | ||
| 図にするとこうなります。 | ||
 |
||
| 上の図だけ見ると、「だから何？」と言いたくなりますね。どっちもたいして変わらないじゃないかという気がします。が、実際にはキューには特別な意味が込められていて、別名を「待ち行列」と言います。処理待ちのデータを並べておく入れ物のような使い方をします。キューに入っているのは処理されるのを今か今かと待っているデータの並びです。そういう気持ちを込めて図解すると、次のようになります（図解というより挿し絵ですが）。 | ||
 |
||
| この微妙なニュアンス、わかってもらえました？ | ||
| スタックについてはどんな実装になっているのか解説しましたが、キューを実現する方法についてはここでは詳しく解説しないことにしましょう。方法はいくつもあると思います。スタックのようにメモリ領域とポインタで実現することもできますし、linked list 構造を使う方法もあります。 | ||
|
※
|
もちろんいろいろな実現方法があるのはスタックも同じことです。一般に「スタック」と言ったらデータ構造の種類のひとつをそう呼ぶのであって、それは「概念」です。前回解説した実装方法は、CPU が関数呼び出しやパラメータを扱う際に使用するスタック（の一種）の場合です。自分で作るときは、別にどんな方法で実装しても良いのです。 | ||
| さて、スタックとキューはどのように使い分けたら良いでしょう? | ||
| スタックは最近のデータを先に使うので、ネスト(入れ子)に向いています。今の状態をとっておいて後で取り戻すのにも使えます。関数呼び出しがまさにそれですね。ある関数から別の関数が呼び出され、そこからまた別の関数が呼び出されるネスト構造になっています。また、呼び出しもとのアドレスをとっておいて、サブルーチンからの復帰に使います。 | ||
 |
キューは先にあったデータから処理するので、順番待ちのような構造に使います。典型的なのは、これから実行するコマンドの一時的な記憶領域です。
オンラインシステムの端末機がたくさんあるような状況を考えてみると想像がつくでしょう。各端末から送られて来たコマンドがメインコンピューターに一時的に蓄積される必要がありますが、こういうときにキュー構造が使われます。銀行の ATM なども(たぶん)そうなっているのではないでしょうか。 |
||
| Windows や Mac などのイベント駆動型（event driven）プログラムを書いたことがある人はわかると思いますが、GUI のイベントもキューに入っていますね（Event Queue などと呼びます）。ユーザーがどこをクリックしたかとか、何のキーを押したかなどのイベントが一時的にキューに格納され、イベントループで１つずつ取り出されて処理されます。 | ||
| 今回は "Hello, world" とはあまり関係ない話でしたが、スタックとキューはどちらも基本的で重要な構造なので、ぜひセットで覚えておいてください。 | ||
| 次回は、スタックとセットで語られることの多いもうひとつのものについて説明します。 | ||
 |
|
（"Hello, ANOTHER world!" は2001年11月から2002年11月にかけて作成されたコンテンツです。）
目次に戻る