【Common Lisp】
キューの基本の使い方
（データ構造とアルゴリズム）

by
  • キューはFIFOのデータ構造で、BFS以外にもタスクスケジューリング・バッファ・スライディングウィンドウなど幅広い場面で使われます。
  • FIFOキューの実装は「リスト系→consセル系→ベクタ系」と段階的に改良でき、循環キューはベクタ系にmod循環を加えて領域を使い回せるようにしたものです。
  • dequeは循環キューにpush-frontとpop-backを足した拡張で、キューとしてもスタックとしても効率的に使えます。
  • 優先度付きキューは、要素を一つずつ積んだり、取り出したりする操作はキューに似ていますが、内部は完全二分木の構造で自動的に優先度で並べ替えられます。

関連記事

1. キュー（queue）というデータ構造

「キュー（queue）」は、待ち行列のように、先に並んだものから順に処理するためのデータ構造です。

「先入れ先出し（First In, First Out）」の頭文字から、「FIFO」のデータ構造ともいいます。
キューが必要になるのは、「複数のものを順番に処理したい」場面です。

たとえば、プリンターに複数の印刷指示が届いたとき、送った順に印刷されるのはキューで管理しているからです。
Webサーバーに同時にリクエストが届いたとき、順番に処理するのも同じ仕組みです。

その基本の操作は、

  • キューの末尾にデータを追加する enqueue
  • キューの先頭からデータを取り出す dequeue

です。

enqueue :C
:C を末尾に追加する

        front          rear
         ↓             ↓
queue:  [:A] → [:B] → [:C]

dequeue → :A を取り出す

        front   rear
         ↓      ↓
queue:  [:B] → [:C]Code language: CSS (css)

プログラミングでは、グラフの幅優先探索（BFS）のように、探索候補をキューに入れておいて、順番に探索を進めていく、というパターンもよく出てきます1。

Common Lispには標準のキュー型がないので、用途に応じて自分で実装します。

種類内部構造取り出し方主な用途
FIFOキュー線形（配列・連結リスト）入れた順BFS、タスク処理、バッファ
循環キュー線形（リングバッファ）入れた順組み込み・長時間動作のFIFO
両端キュー（deque）線形（リングバッファ）両端から選べる0-1 BFS、単調キューの基盤
優先度付きキュー木（二分ヒープ）優先度順Dijkstra法、ヒープソート

FIFOキュー・循環キュー・dequeは同じ線形構造の系譜で、順に拡張関係にあります。
一方、優先度付きキューは、内部構造が大きく異なります。

2. リストを使った実装

2.1. append + pop + setf

FIFOキューの実装は、「何のコストを消すか」という観点で段階的に複雑になります。

もっともシンプルな実装は、リストをそのまま使うもの。
Common Lispの標準リスト操作 append と pop で、簡易的にキューとして利用できます。

(defparameter *q* '())

;; enqueue: 末尾に追加
(setf *q* (append *q* (list :a)))
(setf *q* (append *q* (list :b)))
(setf *q* (append *q* (list :c)))
;; *q* => (:A :B :C)

;; dequeue: 先頭を取り出してqを更新
(pop *q*)
;=> :A
;; *q* => (:B :C)

;; empty判定
(null *q*)
;=> NILCode language: Lisp (lisp)

ただし、appendは、リストにリストをつないだ新しいリストを返す関数です。
頻繁に末尾に1つずつ要素を追加するのには、4つの難点があります。

  • 要素を追加するために、既存リストのconsセルをすべてコピーすること。
  • 要素の追加してもシンボル *q* は元のリストなので再束縛する必要があること。
  • 末尾まで n 回の cdr によるアクセスが必要なこと。
  • 要素を格納するために毎回新しいconsセルを割り当てる必要があること。

つまり、n要素のキューへのenqueueは、毎回 O(n)のコンスセルを用意するため、メモリの割り当て（アロケーション）が発生します。
また、その都度コピーで不要になったリストは廃棄されるので、不要になったメモリの回収（ガベージコレクション）も頻繁に発生します。

2.2. nconc に変えるとコピーは省けるが……

メモリ割り当てを効率化するには、appendの代わりにnconcを使う方法があります。

nconcは、コピーせずに既存リストの末尾セルのcdrを直接書き換えます。
アロケーションコストはappendがO(n)、nconcがO(1)になります。

注意が必要なのは、setfによるシンボルの再束縛です。

(setf *q* (nconc *q* (list :d)))Code language: Lisp (lisp)

nconcは、リストそのものに要素を追加するので、setfが不要に思えます。
ところが、キューが空のときに、困ったことが発生します。

nconcは*q*が空のとき、末尾セルを書き換える対象がないので、新しくコンスセルを生成して返します。
すると、*q*は空リストを指したままになってしまうのです。

(defparameter *q* '()) ;=> *Q*
(nconc *q* (list 1))   ;=> (1)
*q*                    ;=> NILCode language: Lisp (lisp)

つまり、リストをそのままキューとして使うと、「末尾セルのポインタの書き換え」と「変数への再束縛」の2つを常に意識する必要があります。

2.3. enqueueマクロを定義する

再束縛を意識せずに、push/popと同じように扱うには enqueueマクロを作ります。

(defmacro enqueue (q x)
  `(setf ,q (nconc ,q (list ,x))))

(defparameter *q* '())
(enqueue *q* :a)   ; (setf *q* (nconc *q* (list :a))) に展開される
(enqueue *q* :b)
(enqueue *q* :c)
;; *q* => (:A :B :C)

(pop *q*)   ; dequeueはpopをそのまま使う
;=> :ACode language: Lisp (lisp)

リスト方式のメリットは、実装の短さと手軽さです。
リスト自体がキューになるので、デバッグ時にprintで中身をそのまま確認できます。
再帰で自然にリストを構築するLispのスタイルとも馴染みがよいです。

ただし、まだ要素を追加するときの走査コストO(n)が問題になります。

2.4. 【補足】consセルで包んで関数で実装する

ちなみに、enqueueマクロはsetfを隠蔽しますが、シンボルへの再束縛が不要な形にすれば関数としても実装できます。

それは、consセルでリストを包むことです。
そうすれば、シンボルの指すconsセルは固定され、関数からもキューの状態を変えられます。

(defun make-queue/box ()
  (cons nil nil))
;; carにキュー本体のリストを入れ、 cdrは使わない

(defun enqueue/box (q x)
  (setf (car q)
        (nconc (car q) (list x)))
  q)

(defun dequeue/box (q)
  (pop (car q)))

(defun queue-empty-p/box (q)
  (null (car q)))Code language: Lisp (lisp)

シンボルは、いわば「先頭リストの先頭（car）」に束縛します。
consセルのcdr側は何も使いません。

(defparameter *q* (make-queue/box))

(enqueue/box *q* :a)
(enqueue/box *q* :b)
(enqueue/box *q* :c)

(car *q*)
;; => (:A :B :C)Code language: Lisp (lisp)

enqueue/dequeueは中身だけを書き換えるので、*q*が指すconsセル自体は変わりません。
その代わり、dequeue ではなくリストそのものを得るには、car で間接的にアクセスする必要がある点には注意が必要です。

マクロ版と関数版の使い分けはこうなります。

  • enqueueマクロ: シンボルにリストを直接束縛し手軽さを維持。
  • enqueue/func: consセルに包むことで関数として渡せ、高階関数・クロージャと組み合わせられる。

末尾を探すためにリスト全体を毎回たどる（走査はO(n)のまま）ため、n要素に対してn回enqueueするとO(n²)。
要素数が増える用途に使うとすぐに遅くなります2。

2.5. 逆順スタック（蓄積リスト）

リストの末尾に要素を追加すると、辿っていくのに時間がかかります。
そこで、場合によっては、とりあえずどんどん先頭に追加して、必要になったらまとめて反転する、というアプローチも有効です。

(let ((acc '()))
  (push :a acc)   ; O(1)
  (push :b acc)   ; O(1)
  (push :c acc)   ; O(1)
  (nreverse acc)) ; 最後の1回だけ反転
;=> (:A :B :C)Code language: Lisp (lisp)

先頭へのpushはO(1)で、最後にnreverseしてFIFO順に戻します3。。

ただし、逆順スタックは、厳密にはキューではありません。
途中で取り出せないからです。
しかし、「処理途中で取り出す操作が不要」なケースなら高速に処理できます。
たとえば、幅優先探索で経路を(push dir path)で積んでおき、最後に(nreverse path)で返す、というパターンがこれにあたります。

3. consセルに末尾ポインタを持つ実装

3.1. consセルキュー（head/tail）

リストの末尾追加がO(n)になる原因は「末尾を毎回探しに行く」ことでした。

末尾セルへのポインタを持っておけば、O(1)で追加できます。
これは、リストをconsセルで包む方法（enqueue/box）の応用です。

(defun make-queue/cons () 
  (cons nil nil))Code language: Lisp (lisp)

使っていなかったconsセルのcdr部を末尾セルの記憶用に使います。

(defun enqueue/cons (q x)
  (let ((cell (list x)))
    (if (car q)
        (setf (cdr (cdr q)) cell   ; 末尾セルの次に繋ぐ
              (cdr q)       cell)  ; 末尾ポインタを更新
        (setf (car q)       cell   ; 空なら先頭も設定
              (cdr q)       cell)))
  q)

(defun dequeue/cons (q)
  (let ((cell (car q)))
    (when cell
      (prog1 (car cell)
        (setf (car q) (cdr cell))
        (unless (car q) (setf (cdr q) nil))))))

(defun queue-empty-p/cons (q) (null (car q)))Code language: Lisp (lisp)

これなら、enqueue・dequeueともにO(1)です。

make-queue/cons:
  q = (nil . nil)
       head  tail

enqueue :A:
  cell = (:A . nil)
  q = (head . tail)
       ↓       ↓
      [:A|nil]
      (同じcellをheadとtailが指す)

enqueue :B:
  tailが指すcellの次に[:B|nil]を繋ぐ
  tailポインタを[:B|nil]に更新

  q = (head . tail)
       ↓       ↓
      [:A|●]→[:B|nil]

enqueue :C:
  q = (head .      tail)
       ↓               ↓
      [:A|●]→[:B|●]→[:C|nil]

dequeue → :A:
  headを[:B|●]に進める
  q = (head .      tail)
            ↓          ↓
           [:B|●]→[:C|nil]

末尾ポインタを持つことで末尾追加がO(1)になりました。
ただし、まだ要素追加のたびにconsセルが生成され、メモリ割り当てがあります。
要素が多くなると、メモリ割り当てとガベージコレクションの時間は無視できません4。

3.2. defstruct版（読みやすくした派生）

ちなみに、head/tailキューの設計は、car/cdrが多く出てきて意味がわかりにくいです。

しかし、オブジェクトに 2つの要素があればよいので、consセルではなくても構いません。
そこで、defstructのフィールド名に変えても同じように動作させることができます5。

(defstruct linked-queue 
  head tail)

(defun enqueue/linked (q x)
  (let ((cell (list x)))
    (if (linked-queue-head q)
        (setf (cdr (linked-queue-tail q)) cell
              (linked-queue-tail q)       cell)
        (setf (linked-queue-head q)       cell
              (linked-queue-tail q)       cell)))
  q)

(defun dequeue/linked (q)
  (let ((cell (linked-queue-head q)))
    (when cell
      (prog1 (car cell)
        (setf (linked-queue-head q) (cdr cell))
        (unless (linked-queue-head q)
          (setf (linked-queue-tail q) nil))))))

(defun queue-empty-p/linked (q)
  (null (linked-queue-head q)))Code language: Lisp (lisp)
q の構造:
  #S(linked-queue
     :head → [:A|●]→[:B|●]→[:C|nil]
     :tail →              ↑ここ)

(car q) のかわりに (linked-queue-head q)
(cdr q) のかわりに (linked-queue-tail q)Code language: CSS (css)

「先頭と末尾を持つ」という意図がフィールド名で明示されるだけで、実行速度は変わりません6。
難点としては、コードがやや冗長で長くなることです。

3.3. 2リストキュー（front/rear）

2リストキューは、(front . rear)の2つのリストを持ち、consセルからアクセスする設計です。

head/tailキューと似ていますが、rearリストは末尾セルではなく、要素を追加するためのサブリストです。
逆順スタックとhead/tailキューを組み合わせた方法で、enqueueのときにはrearリストに逆順で積んでおき、frontが空になったときだけ反転させてfrontに移します。

(defun make-queue/2list ()
  (cons nil nil))  ; (front . rear)

(defun enqueue/2list (q x)
  (push x (cdr q)) q)

(defun normalize/2list (q)
  (when (null (car q))
    (setf (car q) (nreverse (cdr q))
          (cdr q) nil)) q)

(defun dequeue/2list (q)
  (normalize/2list q)
  (when (car q)
    (prog1 (car (car q))
      (setf (car q) (cdr (car q))))))

(defun queue-empty-p/2list (q)
  (and (null (car q)) (null (cdr q))))Code language: Lisp (lisp)

normalizeのタイミングでreverseのコストが集中し、その1回のdequeueだけO(n)になります7。
ただ、全体としてはenqueue・dequeueがともに均しO(1)になります8。

しかし、リスト実装の常として、やはりconsのメモリ割り当てが大量に発生するのと、dequeueにかかる時間が不安定になるため、リアルタイム性が必要な場面（毎操作が一定時間内に終わる必要があるシステム）には向かないです。

4. 配列を使った実装

4.1. 可変長配列 + headインデックス

リストを使った実装は、効率化していく過程で、make-queue, enqueue, dequeue, queue-empty-pの関数が必要になります。

それなら、データ構造はリストにこだわらず、配列を使うのも選択肢になります。

配列はまとめて連続したメモリを割り当てられるので、consセルの割り当てよりも軽量になります。
ただし、配列の場合は、「先頭の要素を消す」ということが苦手です。
そこで、まずは素朴な実装として、「要素を消さない」というアプローチがあります。
メモリに余裕があり、最大数が決まっているなら、問題なく答えが出るからです。

(defstruct vector-queue
  (data (make-array 16 :adjustable t :fill-pointer 0))
  (head 0))

(defun enqueue/vector (q x)
  (vector-push-extend x (vector-queue-data q))
  q)

(defun dequeue/vector (q)
  (let ((head (vector-queue-head q))
        (data (vector-queue-data q)))
    (when (< head (fill-pointer data))
      (prog1 (aref data head)
        (incf (vector-queue-head q))))))

(defun queue-empty-p/vector (q)
  (= (vector-queue-head q) (fill-pointer (vector-queue-data q))))Code language: Lisp (lisp)

この方法では、dequeueは要素を物理的に消さず、headインデックスを進めるだけです。
いわば、意図的な「メモリリーク」です。

enqueue :A → :B → :C:

  data: [:A][:B][:C][  ][  ][  ]
  head:  0
         ↑
  fill-pointer: 3

dequeue → :A:
  headを1進めるだけで :Aは消さない。

  data: [:A][:B][:C][  ][  ][  ]
             ↑(読み飛ばす)
  head:      1Code language: CSS (css)

処理済み要素が配列に残りますが、1回の処理で終了するプログラムなら影響しません。
ただ、長時間動かすプログラムではメモリが解放されないという問題があります9

4.2. 固定長配列 + head/tailインデックス

配列を使った実装で、もっと空間計算量を割り切ってしまえば、固定長配列を使う方法もあります。

固定長キューでは、末尾位置をベクタサイズと連動したfill-pointerではなく、自前の tailで管理します。

要素の拡張は高コストのため、最大要素数が事前に計算できるなら、あらかじめ確保してしまえば、処理時間は短く、シンプルになります。

(defstruct fixed-queue
  data
  (head 0 :type fixnum)
  (tail 0 :type fixnum))

(defun make-fixed-queue (capacity)
  (make-fixed-queue :data (make-array capacity)))

(defun enqueue/fixed (q x)
  (setf (aref (fixed-queue-data q) (fixed-queue-tail q)) x)
  (incf (fixed-queue-tail q))
  q)

(defun dequeue/fixed (q)
  (when (< (fixed-queue-head q) (fixed-queue-tail q))
    (prog1 (aref (fixed-queue-data q) (fixed-queue-head q))
      (incf (fixed-queue-head q)))))

(defun queue-empty-p/fixed (q)
  (= (fixed-queue-head q) (fixed-queue-tail q)))Code language: Lisp (lisp)

自動拡張をなくすることで、メモリの再割り当てがなくなります。
ただし、利用可能数を超えるとインデックスが範囲外になるためエラーになります。
何を入れるか汎用的に使いたい場面には向かないです。

競技プログラミングのような、答えを出して終わり、というプログラムなら使ってみる価値はあります。

4.3. 循環キュー（Circular Queue）

固定長配列のメモリを再利用する仕掛けが、循環キューです。

循環キューでは、要素数countと最大容量capacityを保持します。

固定長配列では、dequeue済みの領域は二度と使われませんでした。
しかし、headやtailが配列末尾に到達したら、0に戻るようにすることができます。
headとtailを容量の剰余を取るようにすると、循環して使用済みの領域を再利用できます。

(defstruct circular-queue
  data
  (head     0 :type fixnum)
  (tail     0 :type fixnum)
  (count    0 :type fixnum)
  (capacity 0 :type fixnum))

(defun make-circular-queue (capacity)
  (make-circular-queue :data     (make-array capacity)
                       :capacity capacity))

(defun cq-empty-p (q) 
  (zerop (circular-queue-count q)))
(defun cq-full-p
  (q) (= (circular-queue-count q) (circular-queue-capacity q)))

(defun cq-enqueue (q x)
  (assert (not (cq-full-p q)))
  (setf (aref (circular-queue-data q) (circular-queue-tail q)) x)
  (setf (circular-queue-tail q)
        (mod (1+ (circular-queue-tail q)) (circular-queue-capacity q)))
  (incf (circular-queue-count q)))

(defun cq-dequeue (q)
  (unless (cq-empty-p q)
    (prog1 (aref (circular-queue-data q) (circular-queue-head q))
      (setf (circular-queue-head q)
            (mod (1+ (circular-queue-head q)) (circular-queue-capacity q)))
      (decf (circular-queue-count q)))))Code language: Lisp (lisp)

headとtailが配列の端に達したら先頭に戻るので、固定サイズのメモリを永続的に使い回せます。

キューの実装では、循環キューがよく使われます。

C++のstd::queueの内部実装（std::dequeベース）やOSのリングバッファがこの構造です10。

ただし、容量がいっぱいになって、tailがheadに追いついてしまったときの動作には注意が必要です。
なので、問題に合わせてキューの容量を適切に選択する必要があります。

4.4. 整数エンコードのfixnum配列

データがいくつかの小さな整数値のセットと決まっているなら、一つの数値に「エンコード」すると、キューへの出し入れを高速化できます。

たとえば、(r, c, d)の３つを保存するなら、wを決めてひとまとめの数値にできます。

(defun encode-state (r c d w)
  (declare (type fixnum r c d w))
  (the fixnum (+ d (* 4 (+ c (* r w))))))

(defun decode-state (state w)
  (declare (type fixnum state w))
  (let* ((d    (mod state 4))
         (base (floor state 4))
         (c    (mod base w))
         (r    (floor base w)))
    (values r c d)))

(defun make-fixnum-queue (capacity)
  (make-fixed-queue :data (make-array capacity :element-type 'fixnum)))Code language: Lisp (lisp)

リストをenqueueするのではなく、複数の数値を一つにかけ合わせて保存し、必要なときに復元します。

ただし、状態を整数にエンコード・デコードするので、エンコード方法を間違えると衝突やデコードの誤りが起きることに注意が必要です。

5. 両端キュー（deque）

両端キューは、前にも後ろにも追加・取り出しができるキューです。

「Double-Ended Queue」の略で、「deque（デック）」とも呼ばれます11。

5.1. リングバッファで実装したdeque

循環キューにpush-frontとpop-backを加えると、dequeになります。

追加するコードはpush-frontの(mod (1- head) capacity)とpop-backの(mod (1- tail) capacity)の2行だけです12。

deque（循環キュー + 両端操作）:
  push-back  ○   pop-front  ○
  push-front ○   pop-back   ○   ← modで戻るだけ

循環キューはmodで循環するFIFOキューでしたが、headを「1つ戻す」操作を追加するだけで、前からも追加できるようになります。

(defstruct deque
  data
  (head     0 :type fixnum)
  (tail     0 :type fixnum)
  (count    0 :type fixnum)
  (capacity 0 :type fixnum))

(defun make-deque (capacity)
  (make-deque :data (make-array capacity) :capacity capacity))

(defun deque-empty-p (dq) (zerop (deque-count dq)))

(defun push-back (dq x)
  (assert (< (deque-count dq) (deque-capacity dq)))
  (setf (aref (deque-data dq) (deque-tail dq)) x)
  (setf (deque-tail dq) (mod (1+ (deque-tail dq)) (deque-capacity dq)))
  (incf (deque-count dq)))

(defun push-front (dq x)
  (assert (< (deque-count dq) (deque-capacity dq)))
  (setf (deque-head dq) (mod (1- (deque-head dq)) (deque-capacity dq)))
  (setf (aref (deque-data dq) (deque-head dq)) x)
  (incf (deque-count dq)))

(defun pop-front (dq)
  (unless (deque-empty-p dq)
    (prog1 (aref (deque-data dq) (deque-head dq))
      (setf (deque-head dq) (mod (1+ (deque-head dq)) (deque-capacity dq)))
      (decf (deque-count dq)))))

(defun pop-back (dq)
  (unless (deque-empty-p dq)
    (setf (deque-tail dq) (mod (1- (deque-tail dq)) (deque-capacity dq)))
    (prog1 (aref (deque-data dq) (deque-tail dq))
      (decf (deque-count dq)))))

(defun peek-front (dq)
  (unless (deque-empty-p dq)
    (aref (deque-data dq) (deque-head dq))))

(defun peek-back (dq)
  (unless (deque-empty-p dq)
    (aref (deque-data dq) (mod (1- (deque-tail dq)) (deque-capacity dq)))))Code language: Lisp (lisp)

dequeは、両端からO(1)で追加・取り出しができるので、スタックとしてもキューとしても利用できます。
ただし、固定長の循環キューを元にしているため、容量を事前に決める必要がある。

また、modの計算が毎回入るので、単純なFIFOキューより実装が複雑です。
とくに、push-frontのインデックス計算（mod (1- head) capacity）は、言語によっては負の剰余になるので、符号に注意が必要です13。**

5.2. 0-1 BFSでの経路計算で使う

0-1 BFS（辺の重みが0か1の最短路）では、重み0の辺で到達した頂点を先頭に、重み1の辺で到達した頂点を末尾に追加します14。

(let ((dq (make-deque (* v 2))))
  (push-back dq start)
  (loop until (deque-empty-p dq)
        for v = (pop-front dq)
        do (loop for (next cost) in (neighbors v)
                 when (distを更新できる場合)
                   do (if (= cost 0)
                          (push-front dq next)
                          (push-back  dq next)))))Code language: Lisp (lisp)

5.3. 単調キュー（Monotonic Queue）アルゴリズム

dequeの使い方には、「単調キュー（Monotonic Queue）」というアルゴリズムもあります。

「単調キュー」は、データ構造としてはdequeを使います。
「捨てるルールを守りながらdequeを使うアルゴリズム」で、捨てるルールは問題によって変わります15。

  • 最大値を求めたい
    → 単調減少を保つ（新要素より小さいものを末尾から捨てる）
  • 最小値を求めたい
    → 単調増加を保つ（新要素より大きいものを末尾から捨てる）

ルールは固定できないので、問題ごとにdequeを操作するコードを書きます。

5.4. スライディングウィンドウの最大値で単調キューを使う

たとえば、単調キューを使うと、スライディングウィンドウの最大・最小がO(n)で求められます。

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

ウィンドウ [1  3 -1] → 最大 3
            [3 -1 -3] → 最大 3
              [-1 -3  5] → 最大 5
          ...

単調キューは、インデックスを格納し、値が単調減少になるよう管理します。

新しい要素を追加するとき、それより小さい末尾要素は「もうどのウィンドウでも最大値になれない」ので捨てます。

(defun sliding-window-max (nums k)
  (let* ((n      (length nums))
         (result (make-array (- n k -1)))
         (dq     (make-deque n))
         (ri     0))
    (loop for i from 0 below n do
      ;; ウィンドウの外に出た先頭を捨てる
      (when (and (not (deque-empty-p dq))
                 (= (peek-front dq) (- i k)))
        (pop-front dq))
      ;; 末尾の、現在要素以下のインデックスを捨てる
      (loop while (and (not (deque-empty-p dq))
                       (<= (aref nums (peek-back dq))
                           (aref nums i)))
            do (pop-back dq))
      (push-back dq i)
      (when (>= i (1- k))
        (setf (aref result ri) (aref nums (peek-front dq)))
        (incf ri)))
    result))Code language: Lisp (lisp)

単調キューの核心は、pop-backで「意味を失った要素を積極的に捨てる」です16。

単調キューは、高速なアルゴリズムですが、使えるシチュエーションには前提条件があります。
ウィンドウが固定サイズでない場合や、最大・最小以外のクエリ（k番目など）には使えません。

また、「なぜ捨てていいのか」という不変条件の理解が直感に反しやすく、実装ミスが起きやすいです17。

6. 優先度付きキュー（Priority Queue）

「優先度付きキュー」は「キュー」という名前がついていますが、内部構造はFIFOキューやdequeとは別物で、完全二分木を配列で表現した二分ヒープで実装します。

キューに似ているのは、「enqueueで追加し、dequeueで取り出す」というインターフェースだけで、取り出される順序は入れた順ではありません。
優先度順、つまり、数値の小さい順か大きい順です。

最小ヒープ（親が子より小さい）の配列表現:

index:  0   1   2   3   4   5
      [ 1][ 3][ 2][ 6][ 4][ 5]

木の構造:
        1   ← index 0
       / \
      3   2  ← index 1, 2
     / \ /
    6  4 5   ← index 3, 4, 5

index i の親:   floor((i-1) / 2)
左の子:         (2*i) + 1
右の子:         (2*i) + 2

FIFOキューが「First In, First Out」なら、優先度付きキューはさしずめ「First In, Min Out（あるいは Max Out）」と言えそうです18。

6.1. 優先度付きキューでDijkstra法を解く

「優先度キュー」が有効なのは、たとえばDijkstra法では「距離が最小の頂点から処理する」ときです。

頂点がV個、辺がE個のグラフの場合、優先度付きキューなしではO(V²)ですが、二分ヒープを使うとO((V+E) log V)になります19。

6.2. 優先度付きキューの実装

二分ヒープの実装では、enqueue・dequeueは、ちょっと並べ替えコストがあり、ともにO(log n)になります20。

(defstruct min-heap
  (data  (make-array 16 :adjustable t :fill-pointer 0))
  (order #'<))

(defun heap-parent (i)  (floor (1- i) 2))
(defun heap-left   (i)  (1+ (* 2 i)))
(defun heap-right  (i)  (* 2 (1+ i)))
(defun heap-size   (h)  (fill-pointer (min-heap-data h)))
(defun heap-ref    (h i)(aref (min-heap-data h) i))

(defun heap-swap (h i j)
  (rotatef (aref (min-heap-data h) i)
           (aref (min-heap-data h) j)))

(defun heap-precedes-p (h i j)
  (funcall (min-heap-order h) (heap-ref h i) (heap-ref h j)))Code language: Lisp (lisp)

enqueueは末尾に追加して上に浮かせます（sift-up）。

(defun heap-push (h x)
  (vector-push-extend x (min-heap-data h))
  (sift-up h (1- (heap-size h))))

(defun sift-up (h i)
  (loop while (> i 0)
        for parent = (heap-parent i)
        while (heap-precedes-p h i parent)
        do (heap-swap h i parent)
           (setf i parent)))Code language: Lisp (lisp)

dequeueは先頭を取り出し、末尾を先頭に置いて下に沈めます（sift-down）。

(defun heap-pop (h)
  (assert (> (heap-size h) 0))
  (prog1 (heap-ref h 0)
    (let ((last (vector-pop (min-heap-data h))))
      (when (> (heap-size h) 0)
        (setf (aref (min-heap-data h) 0) last)
        (sift-down h 0)))))

(defun sift-down (h i)
  (loop
    (let* ((l    (heap-left i))
           (r    (heap-right i))
           (size (heap-size h))
           (best i))
      (when (and (< l size) (heap-precedes-p h l best)) (setf best l))
      (when (and (< r size) (heap-precedes-p h r best)) (setf best r))
      (if (= best i)
          (return)
          (progn (heap-swap h i best)
                 (setf i best))))))Code language: Lisp (lisp)

ただし、優先度キューは、優先度順の取り出しがO(log n)と高速ですが、要素を探して削除したり変更したりするのは苦手です。
ヒープ内での位置を探す必要があるため、O(n)になります。
特に、同優先度の要素がある場合、順序保証がないため取り出し順は不定で、削除するには「遅延削除」をする必要があります21。

(let ((pq (make-min-heap :order (lambda (a b) (< (car a) (car b))))))
  (heap-push pq (list 0 start))
  (loop until (zerop (heap-size pq))
        for (dist v) = (heap-pop pq)
        unless (already-settled-p v)
          do (settle v dist)
             (loop for (next cost) in (edges v)
                   do (heap-push pq (list (+ dist cost) next)))))Code language: Lisp (lisp)

7. まとめ

【線形構造】
FIFOキュー
  ├─ リスト系
  │   1a. リスト + append/pop/setf  末尾追加O(n)。
コピーが毎回起きる。
  │   1b. リスト + nconc            コピーは省けるが空チェックのsetfが必要。
  │   1c. リスト + enqueueマクロ    push/popと対称的に書ける。
O(n)は残る。
  │   1d. リスト + 関数             consセルで包む。
関数として渡せる。
  │   2.  逆順スタック              追加O(1)だが途中取り出し不可。
蓄積用。
  │
  ├─ consセル系（末尾ポインタを持つ）
  │   3. consセルキュー             追加・取り出しO(1)。
構造説明向き。
  │   4. defstruct版                3と同じ設計。
フィールド名で可読性向上。
  │   5. 2リストキュー              front/rearをconsセルで管理。
均しO(1)。
  │
  └─ ベクタ系（consアロケーションを排除）
      6. adjustable vector          consなし。
自動拡張あり。
      7. 固定長配列                 再アロケーションもなし。
headは前進のみ。
      8. 循環キュー                 modで循環。
領域を使い回せる。
      9. fixnum配列+整数エンコード   enqueueのlistconsも消す。
          ↓ push-front/pop-backを追加
deque（両端キュー、Double-Ended Queue）
  └─ 循環キューの拡張。
リングバッファで両端操作をO(1)で実現。
      └─ 単調キュー（dequeの操作パターン）
             スライディングウィンドウの最大・最小をO(n)で求める。

【木構造】
優先度付きキュー
  └─ 二分ヒープ（完全二分木の配列表現）で実装。
     取り出し口はキューに似るが内部構造は別物。
     最小ヒープ（:order #'<）と最大ヒープ（:order #'>）は比較関数だけが違う。
     Dijkstra法・ヒープソートに使う。Code language: HTML, XML (xml)
  1. OSのラウンドロビンスケジューリングはキューの代表的な応用で、各プロセスをキューに並べ、一定時間ずつCPUを割り当てて末尾に戻すことを繰り返す。これにより複数プロセスが公平にCPUを使える。 – Introduction to Operating Systems – Scheduling
  2. appendはリストを末尾まで走査して新しいリストを作るため、n要素のリストへの追加はO(n)。n回繰り返すとO(1+2+…+n) = O(n²/2) = O(n²)になる。これは挿入ソートの最悪計算量と同じ構造。
  3. nreverseはリストを破壊的に反転する。reverseが新しいリストを返すのに対し、nreverseは元のconsセルのcdrポインタを書き換えるため、元のリストを参照する変数は不定状態になる。使用後は必ず戻り値を使う。
  4. SBCLのGCはコピーGCベースで、短命なオブジェクトはminor GCで回収される。ただし大量のアロケーションはminor GCの頻度を上げ、全体の実行時間に影響する。競プロでの実測では、consキューからfixnum配列キューに切り替えると数百msの改善が見られることがある。
  5. SBCLのデフォルトのコントロールスタックサイズはスレッドごとに2MBで、–control-stack-sizeオプションで変更できる。1000×1000グリッドの再帰DFSでは最大100万段の呼び出しが積み重なり、確実にスタックを溢れさせる。 – SBCL User Manual
  6. defstructはCommon Lispの標準マクロで、コンストラクタ・アクセサ・型述語を自動生成する。生成されるアクセサ関数はinline宣言することでcar/cdrの直書きと同等の速度になる
  7. 最悪ケースのO(n)を回避する手法として、Okasakiはlazy evaluationを使ったreal-time queueを提案している。reverseのコストを後続の操作に少しずつ分散させることで、すべての操作を厳密にO(1)にできる。ただし実装が複雑になる。 – Purely Functional Data Structures – Chris Okasaki
  8. 2リストキューのアモータイズド解析はChris Okasakiの著書で詳しく扱われている。各要素はrearへのpush（1回）・frontへのreverse（最大1回）・frontからのpop（1回）の計3回しか操作されないため、n回の操作の合計コストはO(n)になる。 – Purely Functional Data Structures – Chris Okasaki (Cambridge University Press, 1998)
  9. vector-push-extendの拡張倍率はCommon Lisp仕様では未定義で実装依存。SBCLでは一般的に2倍に拡張される。最大要素数が予測できる場合は(make-array N :adjustable t :fill-pointer 0)で初期サイズを指定しておくと拡張を避けられる。
  10. C++のstd::queueはstd::dequeをデフォルトのコンテナとして使うラッパーで、push/pop/frontのみを公開する。Linux kernelのkfifo（カーネルのFIFOバッファ）もリングバッファ実装で、head/tailをpower-of-2のマスク演算で循環させている。 – Linux kernel kfifo documentation
  11. 「デキュー（dequeue）」は、キューから先頭要素を取り出す操作の名前で、全く別のものです。 –
  12. Common LispのmodはC言語の%と違い、結果が除数と同じ符号になる（数学的剰余）。そのため(mod -1 6)は5になり、headが0のときにpush-frontしても正しくindex 5を返す。Cでは(-1 % 6)が-1になる処理系があり、(capacity + head – 1) % capacityと書く必要がある。
  13. Python3のcollections.dequeは両端O(1)の動的dequeで、内部はブロックリスト（doubly-linked list of fixed-size arrays）で実装されている。C++のstd::dequeも同様の構造で、ランダムアクセスもO(1)だが実際のキャッシュ効率は配列より低い。 – Python collections.deque documentation
  14. 0-1 BFSはDijkstra法の特殊ケースで、辺の重みが0か1に限定されるときdequeだけで最短路を求められる。重み0の辺はコストなしで進めるため先頭に置き（次に処理される）、重み1の辺は通常のBFSと同様に末尾に置く。計算量はO(V+E)でDijkstra法のO((V+E)log V)より速い。
  15. 単調キューはMonotonic Queueとも呼ばれ、競プロではLeetCode 239（Sliding Window Maximum）が典型問題として知られる。C++ではstd::dequeを使って実装するのが標準的。 – Introduction to Monotonic Queues – GeeksforGeeks
  16. O(n)の根拠：各要素はpush-backされる回数が最大1回、pop-backされる回数も最大1回なので、n要素の配列に対してdequeへの操作の合計回数は最大2n回。whileループが繰り返されても全体では2n回を超えないため、全体の計算量はO(n)になる。 – Sliding Window – USACO Guide
  17. 単調キューはDPの最適化にも使われる（Monotone Queue Optimization）。遷移式がdp[i] = max(dp[j]) + cost（jがスライドする範囲に限定される）の形を持つとき、O(nk)の遷移をO(n)に落とせる。競プロでは区間DPや分割DPで頻出のテクニック。 – DP optimization – Monotone-Queue Optimization
  18. 同優先度の要素が複数あるとき、どちらが先に取り出されるかは二分ヒープでは保証されない。挿入順を保持したい場合はタイムスタンプを優先度のセカンドキーとして付加する。Pythonのheapqはタプル比較を使って(priority, timestamp, item)の形で挿入順を保証する慣用句がある。
  19. Dijkstra法の計算量は優先度付きキューの実装によって変わる。二分ヒープではO((V+E)log V)。Fibonacci heapを使うとdecrease-keyがO(1)になりO(E + V log V)まで改善できるが、定数係数が大きく実用上は二分ヒープの方が速いことが多い。 – Dijkstra’s algorithm – Wikipedia
  20. 二分ヒープは1964年にJ.W.J. Williamsがヒープソートのアルゴリズムとして発表したデータ構造。配列で完全二分木を表現するという発想は当時画期的だった。優先度付きキューへの応用はその後広く普及した。 – Algorithm 232: Heapsort, J.W.J. Williams, Communications of the ACM, 1964
  21. 遅延削除（lazy deletion）パターンとは、優先度を更新したい要素を削除せず、新しい優先度で同じ要素を追加し、取り出したときに古いエントリかどうかチェックして捨てる手法。Dijkstra法では頂点ごとにdist配列で確定済みかを管理してこれを実現する。