立命館大学 情報理工学部 メディア情報学科

第６回演習

演習課題に関して

キューの概念

ここではキューについて簡単に説明します．

キューは，スタックと同様にデータ構造の一つです．配列や線形リストなどと異なり，やや抽象的なデータ構造です．実際には，配列や線形リストなどのデータ構造を用いて実現します．

キューとは，データの挿入を列の一端で行い，データの取得を列の反対で行うデータ構造のことです．キューにデータを挿入することをEnqueue，キューからデータを取得することをDequeueといいます．キューをイメージ図で表すと以下のようになります．

配列を使ったキューの実装

キューを実現する方法の１つとして，配列を使った実装方法があります．基本的な考え方は先週の演習で扱ったスタックの実装と同じです．イメージ図を下に示すので考えてみてください．

注意点：今回の課題では，Enqueueは100(=MAX)回を超えないものとする，とありますので，キューとして利用する配列を100個分確保しておけば問題ありません．しかしながら，実用的なキューを作成する場合には，Enqueueの回数は仮定できませんので，問題が発生します．Dequeueするたびに，データが格納されている範囲がどんどん後にずれていってしまうのです．データを格納する構造として連結リストを用いれば解決できますが（第7回の課題），配列のままでこの問題を解決する方法としては，配列の一方の端をもう一方の端に回りこませる方法（ラップアラウンド）があります．配列を環状にするというイメージを持ってもらえばいいです．上の図でいえば，配列のインデックスが9の次に0に戻ってくるイメージです．詳しい説明は割愛しますので，参考書などを探して考えてみてください．