ITパスポート試験 用語辞典

キュー
【Queue】
コンピュータのデータ構造の1つで、先に入力したデータが先に出力される「先入先出し」の構造を持つ。また、このようなデータの入出力方式は「First In First Out」を略して「FIFO」と呼ばれる。
キューは何かの処理の"待ち行列"を実現する際によく使われる構造で、例えば、プリンタの印刷待ち、CPUの処理待ちなどがキュー構造で処理されている。
↓ 用語データを見る
分野:
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
重要度:
(Wikipedia キュー (コンピュータ)より)

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

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

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

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

優先度つきキュー

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

キューの応用

  • メッセージキュー: メッセージのキュー。UNIX では、msgsnd および msgrcv システム・コールにより、それぞれデータを送信および受信できる。データを送信する先は同じプロセスであってもよいし、他のプロセスであってもよい。また、Windows では、GUI プログラムへイベントを送信するのに用いる。イベント駆動型プログラミングを実現している。プログラムはメッセージ・ループでイベントを受信し、適切な動作を行うように作られる。
  • プログラミング言語のライブラリでの実装: プログラミング言語によっては、キューを標準ライブラリとして実装していて、プログラマがキューそのもののプログラムを書かなくても利用できるようになっている。
  • ミドルウェアによる実装: 主にあるプログラムから他のプログラムへデータを送信するためにキューを利用しているミドルウェアが作られている。

キューマシン

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

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

また、キューマシンはデータフローに沿って命令を実行することになる。これはキューマシンの特徴の一つといえる。

「データ構造」の用語

「アルゴリズムとプログラミング」の他の分野

「テクノロジ系」の他のカテゴリ

このページのWikipediaよりの記事は、ウィキペディアの「キュー (コンピュータ)」(改訂履歴)の記事を複製、再配布したものにあたり、このページ内の該当部分はクリエイティブ・コモンズ 表示 - 継承 3.0 非移植 ライセンスの下 に提供されています。


Pagetop