キュー（英: queue）あるいは待ち行列は、コンピュータにおける基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー[2]、取り出すことをデキュー[3]という。
プリンターへの出力処理や、ウィンドウシステムにおけるイベントあるいはメッセージのハンドリング、プロセスの管理など、データを入力された順番通りに処理する必要があるケースに用いられる。また、個々のタスクの実行時間が予測できない、あるいは実行に時間がかかってしまい、即座に（同期的に）実行することができない場合、キューを使っていったんタスクを溜め込んでおき、後からタスクを取り出して非同期で実行する、というような目的で使用できる。
キューの変形として、先頭と末尾の両端から入出力を行えるものを両端キュー[4]という。
キューとは逆に後入れ先出し[5]のリスト構造を持つデータバッファをスタックと呼ぶ。
プログラミング言語によっては、キューを標準ライブラリとして実装していて、プログラマがキューそのもののプログラムを書かなくても利用できるようになっている。標準ライブラリとして用意されていない場合であっても、他のデータ構造、例えばリンクリストをキューと見立てて利用することも多い。
優先度付きキュー
キューに追加する要素に優先度をつけ、優先度に基づいて、キュー内でソートするものを優先度付きキューという。高速化のための各種アルゴリズムが研究されており、また様々な他のアルゴリズムで間接的に使われている。
キューの応用
- UNIXでは、
msgsndおよびmsgrcvシステム・コールにより、それぞれデータを送信および受信できる。データを送信する先は同じプロセスであってもよいし、他のプロセスであってもよい。 - Microsoft Windowsでは、メッセージループを持つスレッドあるいはプロセスにイベントを送信するのに用いられ、イベント駆動型プログラミングを実現している。特にGUIアプリケーションで必須であり、プログラムは受信したイベントメッセージを1つずつメッセージループ内で取得し、適切なプロシージャ（イベントハンドラー）に配送し、イベントに対応する動作を実行する。メッセージ情報は
MSG構造体[6]によるインターフェイスを介して提供される。
- コマンドキュー: ソフトウェアまたはハードウェアに複数のコマンド（命令）を送信して非同期実行させるためのキュー。
- 例えばグラフィックスハードウェア (GPU) との双方向通信には時間がかかるので、スループットを向上するためにほとんどの描画命令は応答が不要な単方向形式となっており、いったんコマンドキューにキューイングされ、まとめて非同期にバッチ処理される。
- コマンドキューはハードウェアに近いデバイスドライバー層で実装してあり、上位レベルのAPIやミドルウェアを利用するアプリケーション層では意識しないで済むこともあるが、下位レベルのAPIではミドルウェアやアプリケーション側で明示的にコマンドキューを利用することもある[7]。
- タスクキュー: ワーカースレッドやサービスプロセスに委譲する処理を一時的に溜め込んでおくためのキュー[8]。
キューマシン
キューマシンは、中間結果格納用にキューを用いる計算モデルである。
演算はエンキューされたデータを用いて行い、その結果をデキューする。そのため、スタックマシンと同じように0オペランドの命令で表現することができる。
また、キューマシンはデータフローに沿って命令を実行することになる。これはキューマシンの特徴の一つといえる。
脚注
関連項目
外部リンク
- キューの可視化（まとめ）