キュー

FIFOのキュー。
これもたまに使いたくなるので、実装(の一つ)をメモしておく。

(declaim (inline make-queue enqueue dequeue queue-empty-p queue-to-list))

(defun make-queue (&optional initial-contents)
  (declare (optimize (speed 3) (safety 0)))
  (let ((que (cons nil initial-contents)))  ; queue = (cons 要素リストの末尾への参照 要素リスト)
    (setf (car que) (last que))
    que))

(defun enqueue (x que)
  (declare (optimize (speed 3) (safety 0)))
  (setf (car que)                    ; 2] 要素リストの末尾への参照を更新する(新しい末尾=(list x)を参照するようにする)
        (setf (cdar que) (list x)))  ; 1] 末尾に要素を追加する
  que)

(defun dequeue (que)
  (declare (optimize (speed 3) (safety 0)))
  (prog1 (pop (cdr que))      ; 要素リストからpop
    (when (null (cdr que))     
      (setf (car que) que)))) ; 要素リストが空になった場合は、参照を貼り直す必要がある

(defun queue-empty-p (que)
  (declare (optimize (speed 3) (safety 0)))
  (eq (car que) que))

(defun queue-to-list (que)
  (declare (optimize (speed 3) (safety 0)))
  (cdr que))

使用例:

(defvar q (make-queue '(:a :b :c)))
--> Q

(setf *print-circle* t)  ; 循環参照(?)があるため、*print-circle*をtにしないと出力が終わらなくなる
--> T

q
--> (#1=(:C) :A :B . #1#)

(dequeue q)
--> :A

q
--> (#1=(:C) :B . #1#)

(enqueue 1 q)
--> (#1=(1) :B :C . #1#)

(dequeue q)
--> :B

(queue-to-list q)
--> (:C 1)

(dequeue q)
(dequeue q)
(queue-empty-p q)
--> T

(dequeue q)
--> NIL      ; 空の場合はnilを返す

追記

fifoという名前でgithubにソースを登録。
asdf-installでインストール可能に。

> (asdf-install:install "http://github.com/downloads/sile/fifo/fifo-0.0.1.tar.gz")