キューとは (FIFO - First In, First Out の原則)

**キューとは (FIFO - First In, First Out の原則)**は、先に追加した要素を先に取り出すFIFOデータ構造である。

仕組み

enqueueは末尾へ追加し、dequeueは先頭から削除する。配列では循環インデックスを使うと要素のシフトを避けられる。

計算量・性質

リングバッファまたは先頭・末尾参照付きリストならenqueueとdequeueはO(1)。

具体例

A,B,Cをenqueueするとdequeueの順はA,B,Cになる。

限界と注意点

単純配列で毎回シフトするとdequeueがO(n)になる。満杯と空の判定も区別する。