PROFILPELAJAR.COM

キュー（英: queue）あるいは待ち行列は、コンピュータにおける基本的なデータ構造の一つ。データを先入れ先出し^[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー^[2]、取り出すことをデキュー^[3]という。

プリンターへの出力処理や、ウィンドウシステムにおけるイベントあるいはメッセージのハンドリング、プロセスの管理など、データを入力された順番通りに処理する必要があるケースに用いられる。また、個々のタスクの実行時間が予測できない、あるいは実行に時間がかかってしまい、即座に（同期的に）実行することができない場合、キューを使っていったんタスクを溜め込んでおき、後からタスクを取り出して非同期で実行する、というような目的で使用できる。

キューの変形として、先頭と末尾の両端から入出力を行えるものを両端キュー^[4]という。

キューとは逆に後入れ先出し^[5]のリスト構造を持つデータバッファをスタックと呼ぶ。

プログラミング言語によっては、キューを標準ライブラリとして実装していて、プログラマがキューそのもののプログラムを書かなくても利用できるようになっている。標準ライブラリとして用意されていない場合であっても、他のデータ構造、例えばリンクリストをキューと見立てて利用することも多い。

優先度付きキュー

→「優先度付きキュー」も参照

キューに追加する要素に優先度をつけ、優先度に基づいて、キュー内でソートするものを優先度付きキューという。高速化のための各種アルゴリズムが研究されており、また様々な他のアルゴリズムで間接的に使われている。

キューの応用

メッセージキュー: 通信のために使用されるメッセージのキュー。

UNIXでは、msgsnd および msgrcv システム・コールにより、それぞれデータを送信および受信できる。データを送信する先は同じプロセスであってもよいし、他のプロセスであってもよい。

Microsoft Windowsでは、メッセージループを持つスレッドあるいはプロセスにイベントを送信するのに用いられ、イベント駆動型プログラミングを実現している。特にGUIアプリケーションで必須であり、プログラムは受信したイベントメッセージを1つずつメッセージループ内で取得し、適切なプロシージャ（イベントハンドラー）に配送し、イベントに対応する動作を実行する。メッセージ情報はMSG構造体^[6]によるインターフェイスを介して提供される。