2 本のスタックによるキュー

全操作が最悪 $\Theta(1)$ 時間のスタック（例えば 命題 4.2 の 1 に基づく連結リスト実装）を 2 本用意し、$\mathrm{in}$、$\mathrm{out}$ と呼ぶ。次のように操作を定める。

• $\mathrm{enqueue}(x)$：$\mathrm{in}$ に $x$ を $\mathrm{push}$ する。
• $\mathrm{dequeue}()$：$\mathrm{out}$ が空ならば、$\mathrm{in}$ が空になるまで「$\mathrm{in}$ から $\mathrm{pop}$ して $\mathrm{out}$ に $\mathrm{push}$」を繰り返す。その後 $\mathrm{out}$ が空ならエラー、そうでなければ $\mathrm{out}$ から $\mathrm{pop}$ して返す。
• $\mathrm{front}()$：同じ移送を行ったうえで $\mathrm{out}$ の $\mathrm{top}$ を返す。

このとき、この実装は 定義 7.1 の公理を満たす。さらに、空の状態から始めた任意の $m$ 回の操作列の総コストは $3m$ 以下であり、1 操作あたりの償却計算量は $O(1)$ である。ただし個々の $\mathrm{dequeue}$ の最悪計算量は、そのときの要素数を $n$ として $\Theta(n)$ である。