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

プリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。

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

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

1 優先度付きキュー

2 キューの応用

3 キューマシン

4 脚注

5 関連項目

6 外部リンク

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

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

メッセージキュー: メッセージのキュー。UNIX では、msgsnd および msgrcv システム・コールにより、それぞれデータを送信および受信できる。データを送信する先は同じプロセスであってもよいし、他のプロセスであってもよい。また、Windows では、GUI プログラムへイベントを送信するのに用いる。イベント駆動型プログラミングを実現している。プログラムはメッセージ・ループでイベントを受信し、適切な動作を行うように作られる。

プログラミング言語のライブラリでの実装: プログラミング言語によっては、キューを標準ライブラリとして実装していて、プログラマがキューそのもののプログラムを書かなくても利用できるようになっている。

ミドルウェアによる実装: 主にあるプログラムから他のプログラムにデータを送信するためにキューを利用しているミドルウェアが作られている。

キューマシン

キューマシンは、中間結果格納用にキューを用いる計算モデルである。

演算はエンキューされたデータを用いて行い、その結果をデキューする。そのため、スタックマシンと同じように0オペランドの命令で表現することができる。

また、キューマシンはデータフローに沿って命令を実行することになる。これはキューマシンの特徴の一つといえる。
脚注^ 英: FIFO
^ 英: enqueue
^ 英: dequeue
^ 英: double-ended queue
^ 英: LIFO

関連項目

ウィキメディア・コモンズには、キューデータ構造に関連するカテゴリがあります。


待ち行列理論

スプーリング

データ構造

Bufferbloat

外部リンク

⇒キューの可視化（まとめ）

表

話

編

歴
データ構造
データ型

コレクション（英語版）

コンテナ

タプル

リスト

配列

可変長


連結リスト

キュー

両端キュー

優先度付きキュー


スタック

スパゲッティスタック


リングバッファ

スキップリスト

連想配列

ハッシュテーブル

ハッシュ関数

コンシステントハッシュ法

分散ハッシュテーブル


マルチマップ（英語版）

セット

マルチセット

素集合データ構造

木

二分木

二分探索木

二重連鎖木

平衡木（英語版）

2-3木

2-3 フィンガーツリー


2-3-4木

B木

B+木

B*木

平衡二分探索木

AA木

AVL木

赤黒木

スプレー木

Treap

木の回転

ヒープ

二分ヒープ

二項ヒープ

フィボナッチヒープ

トライ木

一般

基数木

接尾辞木

接尾辞配列

接尾辞オートマトン


三分探索木

整数

二分トライ木

x-高速トライ木

y-高速トライ木