キュー
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を返す