エンキュー/デキュー【enqueue/dequeue】

概要

キューは要素を一列に並べたデータ構造で、順番を待つ人の行列のように、最も古い要素を最も先に取り出すという「先入れ先出し」（FIFO：First-In First-Out）ルールに基づいて要素の出し入れを行う。

「エンキュー」（enqueue）操作はキューの末尾に新しい要素を追加する。要素の数は1増加する。この要素が取り出されることになるのはその時点で存在する要素の中で最も後になる。「デキュー」（dequeue）操作はキューの先頭から要素を取り出し、先頭から2番目にあった要素が新たに先頭になる。要素の数は1減少する。

この「先頭」「末尾」はキューとしての論理的な位置関係を表し、実装上のデータの記憶領域において物理的に先頭や末尾に対応するとは限らない。例えば、配列を用いてキューを実装する場合には、デキューが行われたからといってすべての要素を一つ前の配列変数にコピーし直すのは非効率であるため、現在のキューの「先頭」「末尾」の位置を変数に格納して、配列上を「先頭」「末尾」の位置が後方に移動していくという実装とすることが多い。