スタックとキューの両方の端を使う
両端キューは、先頭と末尾の両方で追加や削除ができるデータ構造です。英語名のdequeはdouble-ended queueから来ています。末尾へ追加して先頭から取り出せばFIFOのキュー、同じ端で追加と削除を行えばLIFOのスタックとして使えます。ここで重要なのは、どの操作をどの端へ行うかです。名前にqueueが含まれていても、すべての使い方で必ず先入れ先出しになるわけではありません。必要な操作を一覧にし、先頭・末尾・中央のどこをよく触るかを決めると、配列や連結リストとの選択が明確になります。
操作列を先頭から書いて追う
空の状態から末尾へAを追加し、末尾へBを追加し、先頭へXを追加すると、先頭からX、A、Bとなります。先頭を取り出せばX、次に末尾を取り出せばBが返り、中にはAが残ります。最後の取り出しがBなのは、最初に追加されたAを優先するFIFOの操作ではなく、末尾を選んだからです。例では記号を要素として扱っています。複数の要素が同じ値でも、それぞれの追加位置と取り出し位置を追えるようにすると、向きの取り違えを見つけやすくなります。実装の添字を使う前に、この抽象的な操作の結果を確定します。
両端の速さと中央の速さは違う
実装には循環配列、連結されたブロック、連結リストなどが考えられます。両端の操作を効率よく行えても、任意の中央要素への参照が常にO(1)になるとは限りません。Pythonのcollections.dequeは、両端の追加・削除がおおむねO(1)の操作である一方、中央への添字アクセスは長さに応じて高くなります。動的配列の末尾追加の償却費用と、先頭削除で要素をずらす費用も区別します。同じdequeという抽象でも、確保の粒度や局所性は異なります。性能の結論には、具体的な実装と操作の比率が必要です。
上限に達したときの規則を決める
容量上限を持つdequeでは、いっぱいになった後の挙動が重要です。エラーにする、待つ、古い要素を捨てるなど、用途に合う規則を選びます。Pythonのmaxlen付きdequeでappendを続ける場合、反対側から古い要素が落ちる動きがあり、仕事を必ず全件処理するキューとは違います。たとえば直近の観測履歴には適していても、未処理の決済要求を黙って捨てる用途には向きません。容量を設定しただけでバックプレッシャーが成立するとは考えず、追加失敗や破棄が呼出し側へどう伝わるかを仕様として確認します。
一操作の安全性と複合操作を分ける
並行して使う場合、個々のappendやpopが安全でも、「空でないことを確認してから取り出す」という二操作の組合せまで原子的とは限りません。確認直後に別の消費者が最後の要素を取れば、次のpopは空の状態を扱う必要があります。待機が必要な生産者・消費者では、ロックや条件変数を含むキュー用のAPIが適切な場合もあります。特定言語のランタイムの性質を、別の実装や別バージョンへ無条件に一般化しません。操作の境界と所有者を定め、空、満杯、停止、キャンセルのそれぞれでどう動くかを設計します。
用途ごとの結果を確かめる
BFSでは、発見した頂点を末尾へ追加して先頭から取る操作を使えます。スライディングウィンドウの最大値を管理する方法では、両端から不要な候補を除くdequeが役立ちます。ただし後者は値の単調性を保つ追加の規則があり、dequeを選ぶだけでアルゴリズムが完成するわけではありません。検証では空、一要素、両端を交互に触る列、容量上限、同じ値の重複を試します。ここでのX、A、Bの列は操作の意味の例で、性能測定ではありません。速さだけでなく、順序、破棄、例外の仕様が必要な仕事に合っているかを確かめます。