待ち行列。FIFOとも呼ばれる方式で、最初に入ったものが最初に取り出される形式のデータ格納方法。

目次 概要 特徴 用途 実装

概要

行列は一つの列であり、順番に並ぶ。基本的には、割り込んだりは原則としてできない、先入れ先出し型(FIFO)のリストである。但し、処理によっては特定のジョブを優先して取り出して処理したりする場合もある。

このためキューは、複数箇所から一ヶ所宛にデータを与えるような処理によく使われている。

特徴

用途

処理をすべきだが、何らかの理由(マシン負荷が重い、ネットワークが黒い、起動直後で制御したいプロセッサーがまだ起動していないなど)によってすぐに実行できない場合、その処理はキューにためられ、適当なときに処理される。

入ったものから順番に処理されるので処理順が狂うことが原則としてなく、このため今すぐに処理できないものをとりあえず保存する必要がある場合などに適している。

実装

キューにデータを追加することをenqueueといい、キューからデータを取り出すことをdequeueという。

実装方法は様々考えられるが、使い終わったものは即不要になるので削除されても差し支えない。しかし、enqueue時にメモリー確保してdequeue時にメモリー解放では処理も重く非効率であることから、キューの代表的な実装方法はリングバッファーである。リングバッファーは、実際のバッファー領域と、二つのポインターのみで実装できる。

リンク

関連する用語
FIFO
キューイング
スプール
バッファー
スタック

[再検索] [戻る]