キュー

キューとは、次の操作をもつ抽象データ型である。値の型を $X$、キューの全体を $\mathcal{Q}$ と書く。

• $\mathrm{empty} \in \mathcal{Q}$（空のキュー）
• $\mathrm{enqueue} : \mathcal{Q} \times X \to \mathcal{Q}$（末尾に加える）
• $\mathrm{dequeue} : \mathcal{Q} \to \mathcal{Q}$（先頭を取り除く）
• $\mathrm{front} : \mathcal{Q} \to X$（先頭を読む）
• $\mathrm{isEmpty} : \mathcal{Q} \to \{\mathrm{true}, \mathrm{false}\}$

これらは任意の $Q \in \mathcal{Q}$、$x \in X$ について次の公理を満たす。

$\mathrm{front}(\mathrm{empty})$ と $\mathrm{dequeue}(\mathrm{empty})$ は定義されない。