キュー 【queue】 待ち行列

概要

キュー（queue）とは、最も基本的なデータ構造の一つで、要素を入ってきた順に一列に並べ、先に入れた要素から順に取り出すという規則で出し入れを行うもの。窓口などの順番を待つ人の行列をモデル化したものとも言える。

キューは先頭が常に最も古い要素になるデータ構造で、新しい要素は必ず末尾に追加される。取り出すときは常に先頭の最も古い要素から取り出される。このように先に入れたものほど先に取り出される管理方式を「FIFO」（First-In First-Out：先入れ先出し）という。

実装上は、キューのために確保された記憶領域の中ですべての要素が到着順に並ぶとは限らず、実際の位置や順序とは別に到着順や末尾の位置などの情報を内部的に記録・管理する手法が用いられることが多い。人間の行列のように要素が取り出されるたびに残りのすべての要素の物理的な位置を隣（一つ前）に移動させるのは非効率だからである。

バリエーションとして、列の両端から要素の追加や取り出しを行える「両端キュー」（double-ended queue）や、追加する要素に優先度を設定して、優先度の高いものから取り出すようにする「優先度付きキュー」（priority queue）などがある。

一方、「先に足された要素ほど後に取り出される」（末尾から順に取り出す）という規則で要素の出し入れを管理するデータ構造は「スタック」（stack）と呼ばれる。そのような管理方式を「LIFO」（Last-In First-Out：後入れ先出し）あるいは「FILO」（First-In Last-Out：先入れ後出し）という。

要素の出し入れ

キューに要素を追加する操作を「エンキュー」（enqueue）、取り出す操作を「デキュー」（dequeue）という。エンキューされた要素はキューの末尾に追加され、キューの要素数は1増加する。

デキューを指示するとキューの先頭の要素が取り出され、その要素はキューから取り除かれる。先頭から2番目にあった要素（2番目に古かったデータ）が新しい先頭になり、キューの要素数は1減少する。

キューイング (queuing/queueing)

キューを用いて要素の管理を行うことを「キューイング」（queuing）という。キューイングは機器間やプログラム間など独立に動作する二つの主体の間で非同期にデータの受け渡しを行う手法としてよく用いられる。システム間で汎用的にデータを受け渡しするシステムを「メッセージキュー」（message queue）という。

例えば、コンピュータからプリンタにデータを伝送する速度とプリンタがデータを紙に印刷する速度では、後者のほうが圧倒的に遅い。伝送と印刷を同時に行おうとするとコンピュータ側はほとんどの時間待たされることになり無駄であるため、印刷データを一旦キューに保管し、プリンタの処理の進み具合に応じて専用の制御プログラムが少しずつデータを伝送する手法が用いられる。