キュー (コンピュータ)
出典: フリー百科事典『ウィキペディア（Wikipedia）』
キュー (queue)、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し (FIFO: First In First Out) のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー (Enqueue) 、取り出すことをデキュー (Dequeue) という。
プリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。
キューの変形として、先頭と末尾の両端から入出力を行えるものを両端キュー(double-ended queue, deque)という。
キューとは逆にLIFO（後入れ先出し）のリスト構造を持つデータバッファをスタックと呼ぶ。
目次 |
[編集] 優先度つきキュー
「優先度つきキュー」も参照
キューに追加する要素に優先度をつけ、優先度に基づいて、キュー内でソートするのを優先度つきキューといい、高速化のためのアルゴリズムが色々研究されていて、また、色々な他のアルゴリズムで間接的に使われている。
[編集] キューの応用
- メッセージキュー: メッセージのキュー
- メッセージ・キュー (UNIX): msgsnd() および msgrcv() システム・コールにより、それぞれデータを送信および受信できる。データを送信する先は同じプロセスであってもよいし、他のプロセスであってもよい。
- メッセージ・キュー (Windows): GUI プログラムへイベントを送信するのに用いる。イベント駆動型プログラミングを実現している。プログラムはメッセージ・ループでイベントを受信し、適切な動作を行うように作られる。
- プログラミング言語のライブラリでの実装: プログラミング言語によっては、キューを標準ライブラリとして実装していて、プログラマがキューそのもののプログラムを書かなくても利用できるようになっている。
- ミドルウェアによる実装: 主にあるプログラムから他のプログラムへデータを送信するためにキューを利用しているミドルウェアが作られている。
[編集] キューマシン
キューマシンは、中間結果格納用にキューを用いる計算モデルである。
演算はエンキューされたデータを用いて行い、その結果をデキューする。そのため、スタックマシンと同じように0オペランドの命令で表現することができる。
また、キューマシンはデータフローに沿って命令を実行することになる。これはキューマシンの特徴の一つといえる。
[編集] 関連項目
[編集] 外部リンク
 |
この「キュー (コンピュータ)」はコンピュータに関連した書きかけ項目です。この記事を加筆して下さる協力者を求めています（PJ コンピュータ / Portal:コンピュータ）。 |
