キュー (コンピュータ)
From Wikipedia, the free encyclopedia
キュー（英: queue）あるいは待ち行列は、コンピュータにおける基本的なデータ構造の一つ。データを先入れ先出し（FIFO）のリスト構造で保持するものである。また、バッファサイズが固定の場合、リングバッファを用いることもある。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー（enqueue）、取り出すことをデキュー（dequeue）という。
プリンターへの出力処理や、ウィンドウシステムにおけるイベントあるいはメッセージのハンドリング、プロセスの管理、探索などのアルゴリズムの下請けなど、データを入力された順番通りに処理する必要があるケースに用いられる。また、個々のタスクの実行時間が予測できない、あるいは実行に時間がかかってしまい、即座に（同期的に）実行することができない場合、キューを使っていったんタスクを溜め込んでおき、後からタスクを取り出して非同期で実行する、というような目的で使用できる。
キューの変形として、先頭と末尾の両端から入出力を行えるものを両端キュー（double-ended queue）という。
キューとは逆に後入れ先出し（LIFO）のリスト構造を持つデータバッファをスタックと呼ぶ。
プログラミング言語によっては、キューを標準ライブラリとして実装していて、プログラマがキューそのもののプログラムを書かなくても利用できるようになっている。標準ライブラリとして用意されていない場合であっても、他のデータ構造、例えばリンクトリストをキューと見立てて利用することも多い。
優先度付きキュー
キューの応用
- UNIXでは、
msgsndおよびmsgrcvシステム・コールにより、それぞれデータを送信および受信できる。データを送信する先は同じプロセスであってもよいし、他のプロセスであってもよい。 - Microsoft Windowsでは、メッセージループを持つスレッドあるいはプロセスにイベントを送信するのに用いられ、イベント駆動型プログラミングを実現している。特にGUIアプリケーションで必須であり、プログラムは受信したイベントメッセージを1つずつメッセージループ内で取得し、適切なプロシージャ（イベントハンドラー）に配送し、イベントに対応する動作を実行する。メッセージ情報は
MSG構造体[1]によるインターフェイスを介して提供される。
- コマンドキュー: ソフトウェアまたはハードウェアに複数のコマンド（命令）を送信して非同期実行させるためのキュー。
- 例えばグラフィックスハードウェア (GPU) との双方向通信には時間がかかるので、スループットを向上するためにほとんどの描画命令は応答が不要な単方向形式となっており、いったんコマンドキューにキューイングされ、まとめて非同期にバッチ処理される。
- コマンドキューはハードウェアに近いデバイスドライバー層で実装してあり、上位レベルのAPIやミドルウェアを利用するアプリケーション層では意識しないで済むこともあるが、下位レベルのAPIではミドルウェアやアプリケーション側で明示的にコマンドキューを利用することもある[2]。
- タスクキュー: ワーカースレッドやサービスプロセスに委譲する処理を一時的に溜め込んでおくためのキュー[3]。
キューマシン
キューマシンは、中間結果格納用にキューを用いる計算モデルである。[4][5][6][7][8]
演算はデータをデキューして行い、その結果をエンキューする（スタックマシンの、ポップ＝デキューでプッシュ＝エンキューだと考えれば良い）。そのため、スタックマシンと同じように0オペランドの命令で表現することができる。
また、キューマシンはデータフローに沿って命令を実行することになる。これはキューマシンの特徴の一つといえる。
PostScript風の、しかしスタックではなくキュー（FIFO）ベースの言語「FIFOL」があり[9][10][11][12]、不動点プログラミングについて考察されていたり[13]、万能機械の実装が（万能チューリング機械のようにして）示されている[14]。 [15]も参照。
ここでは例として 9 * (8 - 1) / (3 + 6) という式からのコード生成と、そのキューマシンでの実行を見てゆく。
式を二分木であらわし、幅優先探索の逆順で、一番下の葉から横に、次いで上に、の順でたどってゆき、現れたノードを順にトークン（コマンド）にしてゆく。
キューマシンのJavaで実装したサンプルを以下に示す。
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.StringTokenizer;
class QueueMachine {
public static void main (final String[] args) {
final String machineCode = "8 1 9 - 3 6 * + /";
final Queue<Integer> q = new LinkedList<Integer>();
final StringTokenizer st = new StringTokenizer(machineCode);
for (;;) {
try {
final String token = st.nextToken();
System.out.print(q + " : ");
try {
q.add(Integer.valueOf(token));
} catch (final NumberFormatException e) {
final int a, b;
switch (token.charAt(0)) {
case '+':
a = q.remove().intValue();
b = q.remove().intValue();
q.add(Integer.valueOf(a + b));
break;
case '-':
a = q.remove().intValue();
b = q.remove().intValue();
q.add(Integer.valueOf(a - b));
break;
case '*':
a = q.remove().intValue();
b = q.remove().intValue();
q.add(Integer.valueOf(a * b));
break;
case '/':
a = q.remove().intValue();
b = q.remove().intValue();
q.add(Integer.valueOf(a / b));
break;
default:
throw new RuntimeException();
}
}
System.out.println(token);
} catch (final NoSuchElementException e) {
break;
}
}
System.out.println(q);
}
}
実行結果を以下に示す。［］内がキューの内容、コロンの右が実行しようとしているトークン（コマンド）である。右端からエンキュー、左端からデキューしている。
$ java QueueMachine [] : 8 [8] : 1 [8, 1] : 9 [8, 1, 9] : - [9, 7] : 3 [9, 7, 3] : 6 [9, 7, 3, 6] : * [3, 6, 63] : + [63, 9] : / [7]
