SICPを読む(105) 問題3.23 - デキュー

メモ化ユーティリティが欲しくなってきたので、メモ化までSICP読み。

問題 3.23

デキューを作れ。という問題。

末尾のdeleteをする為には、キューを双方向化する必要がある。

前 <- 今 -> 後

こうしておかないと、最後をdeleteするのにO(1)を達成できない。ちと面倒。

データ構造は(list 今 前 後)として実装していくことにする。

(define (make-deque)
  (let* ((front-ptr '())
         (rear-ptr '())

         (get-new-pair (lambda (v) (list v '() '())))
         (set-before! (lambda (p v) (set-car! (cdr p) v)))
         (set-after! (lambda (p v) (set-car! (cddr p) v)))
         (empty-queue? (lambda ()
                         (null? front-ptr)))
         (lookup (lambda ()
                   (letrec ((iter (lambda (l)
                                    (if (null? l)
                                        '()
                                        (cons (car l)
                                              (iter (caddr l)))))))
                     (iter front-ptr)))))
        (lambda (m)
          (case m
                ('empty-queue? (empty-queue?))
                ('front-queue (if (empty-queue?)
                                  (error "empty.")
                                  (car front-ptr)))
                ('rear-queqe (if (empty-queue?)
                                 (error "empty.")
                                 (car rear-ptr)))
                ('front-insert-queue! (lambda (v) ; N <-> F
                                        (let ((new-pair (get-new-pair v)))
                                          (if (empty-queue?)
                                              (set! rear-ptr new-pair)
                                              (begin
                                                (set-before! front-ptr new-pair)
                                                (set-after! new-pair front-ptr)))
                                          (set! front-ptr new-pair)
                                          (lookup))))
                ('rear-insert-queue! (lambda (v) ; R <-> N
                                        (let ((new-pair (get-new-pair v)))
                                          (if (empty-queue?)
                                              (set! front-ptr new-pair)
                                              (begin
                                                (set-before! new-pair rear-ptr)
                                                (set-after! rear-ptr new-pair)))
                                          (set! rear-ptr new-pair)
                                          (lookup))))
                ('front-delete-queue! (cond ((empty-queue?) (error "empty.")) ; X <-> F
                                            (else
                                              (set! front-ptr (caddr front-ptr))
                                              (if (empty-queue?)
                                                  (set! rear-ptr '())
                                                  (set-before! front-ptr '()))
                                              (lookup))))
                ('rear-delete-queue! (cond ((empty-queue?) (error "empty.")) ; R <-> X
                                           (else
                                             (set! rear-ptr (cadr rear-ptr))
                                             (if (null? rear-ptr)
                                                 (set! front-ptr '())
                                                 (set-after! rear-ptr '()))
                                             (lookup))))
                (else
                  (error "require method."))))))

(define dq (make-deque))

((dq 'front-insert-queue!) 1) ; (1)
((dq 'front-insert-queue!) 2) ; (2 1)
((dq 'front-insert-queue!) 3) ; (3 2 1)
((dq 'rear-insert-queue!) 4) ; (3 2 1 4)
((dq 'rear-insert-queue!) 5) ; (3 2 1 4 5)
((dq 'rear-insert-queue!) 6) ; (3 2 1 4 5 6)
(dq 'front-delete-queue!) ; (2 1 4 5 6)
(dq 'rear-delete-queue!) ; (2 1 4 5)

(dq 'front-queue) ; 2
(dq 'rear-queqe) ; 5

見難かったのでlookupで快適にキューが見れるように工夫した。

rear-delete-queue!が案外曲者。

キューの場合は後ろのポインタを追い抜いていくというテクニックが使えたけど、rear-delete-queue!しても、先頭ポインタは一番後ろのポインタを指したままになってしまうので、キューが空になったら、先頭ポインタを更新してやる必要がある。