キューとは
データを保存し、取り出す構造のひとつとしてキュー構造があります。
キュー構造は、保存するデータを順番にキューにつないでいきます。データを取り出すときは、最初につないだデータから取り出し、キューから切り離します。
キューでは、最初に保存したデータを最初に取り出す方式をとります。これを、FIFO（First In First Out）と呼びます。
スタック構造については、こちらの記事でまとめていますが、スタックのデータ保存、取り出し方式は、LIFOです。
このデータの保存、取り出し順序がFIFOかLIFOかという点がキュー構造とスタック構造の違いになります。
キュー構造
キューは、下の図のような構造をしています。
この図では、queue[0]からqueue[N-1]までのN個の配列を持つキューで、図中の青色部分のqueue[2]からqueue[k]までにデータが保存されている状態を表しています。
キューには、データの先頭を示すheadとデータの終端を示すtailの２つの変数で保存されているデータの管理をします。
データをキューに保存する（enqueue）ときは、tailの次に保存し、tailの位置を一つ後ろに移動します。
データをキューから取り出す(dequeue)ときは、headのデータを受け渡し、headの位置を一つ後ろに移動します。
初期状態は、データがないので、headとtailがともにqueue[0]の位置からスタートします。
キューにデータがない状態のときは、headとtailが同じqueue配列を示しているときです。
逆にキューにデータが満杯に入っているときは、tailの次のqueue配列がheadの示している配列のときになります。
queue[N-1]までデータが保存され、次にデータを保存する場合は、queue[0]に戻ってデータが挿入されます。
キューの使い方
キューのサンプルプログラムです。
キューには、最大１００個の整数型データを保存できるようになっています。
コンソール上に「 ] 」と表示されている状態で、「i」または、「I」を入力すると、「data –> 」という文字列が表示されるので、そこに整数値を入力して、「Enter」キーを押します。
これで、キューに入力データがエンキューされます。１００個以上のデータをエンキューしようとすると「queue full」が表示されて、そのデータは保存されません。
キューのデータをデキューする場合は、コンソール上に「 ] 」と表示されている状態で、「o」または、「O」を入力すると、「queue data –> 」に続けてキューに保存されているデータの中で先頭のものが取り出され、表示されます。
デキューするデータがない場合は、「queue empty」と表示されます。
プログラムを終了するときは、「ctrl + Z」を押し、「Enter」キーで終了します。
c:\prog\algorithm>queue
]i
data --> 1
]i
data --> 2
]i
data --> 3
]o
queue data -->1
]o
queue data -->2
]o
queue data -->3
]o
queue empty
]^Z
test endキューに「１」，「２」，「３」の順にエンキューして、順次、デキューした結果です。
先に保存された「１」から順番に取り出され、キューにデータがなくなると「queue empty」が表示されています。
コメント