両端キュー
両端キューの効率的実装方法は2つある。ひとつは動的配列を修正したもので、もうひとつは双方向連結リストを使った実装である。
動的配列による実装は、どちらの方向にも成長できる動的配列を使うもので、配列デック (array deque) とも呼ぶ。配列デックは動的配列でもあるため、定数時間でランダムアクセスが可能で参照の局所性もよいが、途中への挿入/削除が非効率だが両端での挿入/削除が定数時間になっている。典型的実装として以下の2つがある。
リングバッファに両端キューの内容を格納し、バッファが満杯になったときだけサイズを拡大する。これはサイズ拡大の頻度を減らすことができるが、インデックスのために余分な分岐命令を必要とする。
配列の真ん中から両端キューの内容を配置していき、どちらかの端まで満杯になったときにサイズを拡大する。この場合、サイズ拡大の頻度は多くなるし、一方の端でのみ追加する場合はメモリ空間を無駄にする割合が大きい。