キュー（queue）

テクノロジ系
アルゴリズムとプログラミング
基本情報
応用情報
重要度 ★★★★☆

先に入れたデータから先に取り出すデータ構造。先入先出（FIFO）ともいう。

もう少し詳しい説明

キューは、先に入れたものが先に出てくる入れ物です。

レジの行列を思い浮かべてください。先に並んだ人から順に会計をします。あとから来た人が先に呼ばれることはありません。この「順番が入れ替わらない」という性質をそのまま形にしたのがキューです。

レジの行列と同じで、並んだ順にそのまま処理されます。あとから来た C が先に呼ばれることはありません。この「順番が入れ替わらない」ことがキューの取り柄です。

英語では先入先出、頭文字を取って FIFO（First In First Out）と呼びます。データを入れる操作をエンキュー、取り出す操作をデキューと言います。

どこで使われているか

順番を守って待たせたい場面の、ほとんど全部です。

印刷を指示した順に紙が出てくるのも、ネットワーク機器が届いたデータを順に処理するのも、OSが実行待ちのプログラムを並べておくのもキューです。「早い者勝ちで公平に」を実現したいときは、だいたいこれが入っています。

作るときの工夫

キューをプログラムで作るときは、たいてい普通の配列を使います。ただ、素直に作ると無駄が出ます。

先頭から1つ取り出すたびに、残り全員を1つずつ前へずらすやり方だと、並んでいる数が多いほど時間がかかります。レジで1人帰るたびに、後ろに並んでいる全員が1歩ずつ前へ詰め直すようなものです。

そこで、列そのものは動かしません。かわりに「いまどこが先頭で、どこが末尾か」を数字2つで覚えておきます。取り出すときは先頭の数字を1つ進めるだけ、入れるときは末尾の数字を1つ進めるだけ。誰も動かなくて済みます。

ただしこの方法には続きがあります。出し入れを繰り返すうちに、2つの数字はどんどん配列の右へ進み、やがて終わりに達します。前のほうは空いているのに、もう入れられないという状態です。

これを避けるため、末尾が配列の終わりまで来たら先頭へ戻るようにします。配列を輪のようにつないで、同じ場所をぐるぐる使い回す形です。これを**リングバッファ（環状キュー）**と呼びます。

なお、並んだ順ではなく重要度の高いものから取り出したい場合もあります。そのときはキューではなく、優先度付きキューという別の入れ物を使います。救急外来で、来た順ではなく症状の重い人から診るのと同じ考え方です。

スタックとの違い

対になる入れ物がスタックで、こちらは後に入れたものが先に出ます（LIFO：Last In First Out）。

積み上げた本の山から1冊取るときは、一番上、つまり最後に置いたものになります。下に埋まった本を先に取ることはできません。

試験ではこの2つを並べて出すのが定番です。

試験ではこう出る

科目A（旧・午前）ではスタックとセットで「データの出し入れの順序」を問う問題が定番です。図やデータの並びを示して「最後に取り出されるのはどれか」を選ばせる形式が繰り返し出題されます。科目B（旧・午後）のアルゴリズム問題では、幅優先探索やジョブの実行順管理の中でキューが登場します。図に矢印を書き込んで順番を追えば確実に解けるので、暗記より手を動かす練習が効きます。

ミニクイズ

キューに A・B・C の順にデータを入れた後、2回取り出した。次に取り出されるデータはどれか。

正解は 3番：C

キューは先入先出（FIFO）なので、取り出される順はA→B→Cです。2回取り出した時点でAとBが出ているため、次はCになります。後入先出のスタックと混同しないよう注意してください。

間違えた用語の復習リストを見る →

最終更新：2026-09-14