リングバッファ

容量 $m$ の配列 $A[0..m-1]$、先頭位置 $h$（$0 \le h \le m-1$）、要素数 $n$（$0 \le n \le m$）を保持し、次のように操作を定める。

• $\mathrm{enqueue}(x)$：$n < m$ のとき $A[(h + n) \bmod m] \leftarrow x$、$n \leftarrow n + 1$。
• $\mathrm{dequeue}()$：$n > 0$ のとき戻り値を $A[h]$ とし、$h \leftarrow (h + 1) \bmod m$、$n \leftarrow n - 1$。
• $\mathrm{front}()$：$n > 0$ のとき $A[h]$ を返す。

このとき、キューの内容を先頭から順に $q_0, q_1, \ldots, q_{n-1}$ とすると、常に $q_i = A[(h + i) \bmod m]$ が成り立ち、定義 7.1 の公理が満たされる。また 3 つの操作はいずれも最悪 $\Theta(1)$ 時間である。