Thinkers'Studio
JavaとC言語の自習ツール
キュー(待ち行列)

キューの要点

 キュー(queue)は、複数のデータを取り扱うときのデータ構造のひとつです。
 次のような特徴を持ちます。
  • 順番待ちの列に並ぶように、データが最後尾に入る
     データを取り出すときは、列の先頭から取り出します(下の図のようなイメージです)。
  • データをキューに入れる操作はエンキュー(enqueue)、取り出す操作はデキュー(dequeue)という
     【参考】 英語の接頭辞 "en" は「〜の中に」、"de" は「〜から除去」などの意を持ちます
  • 列の先頭にあるデータだけが取り出しの対象になる
     順番を飛ばして、列の2番目以降のデータを取り出すことはできません。
     下の図で、B や C は取り出せません。A を取り出すと、B が列の先頭になるので B を取り出せます。 キューのイメージ
     データはお行儀よく並び、順番を守って、列の先頭から出て行きます。
  • このような方式は、次のように呼ばれる
     先に入れたデータが先に出る --「先入れ先出し」(FIFO : First In First Out)
     (「後入れ後出し」(LILO : Last In Last Out)も同じことを言っています)

キューの例

 キューのデータ構造を使う例としては、メッセージキューが挙げられます。 異なるアプリケーション間でデータをやり取りするとき、送信したメッセージを相手側がすぐに受け取れる訳ではありません。そこで、キューにメッセージを残しておき、受信側は自分のタイミングでそれを読み出して処理します。それぞれのアプリケーションは独立性を保ちながら、比較的簡単にデータ連携が実現できます。
 また、高速道路の渋滞予測や、レジや銀行の窓口数の検討など、待ち行列理論を使うシミュレーションプログラムでもキューが用いられます。

基本情報試験のキューに関する出題

 キューは、スタックとともに基本情報技術者試験の午前の出題範囲に含まれています。
 スタックは、キューと異なり、先に入れたデータが最後に出るデータ構造です。両者の違いをよく知っておきましょう。

 下に、キュー関連の基本情報の過去問を 2問用意しました。 力試しにやってみてください。

  (平成25年秋期 基本情報技術者試験 午前問5)
FEキュー問題1

  (平成24年秋期 基本情報技術者試験 午前問5)
FEキュー問題2