SICP問題3.23

デキュー(dequeu - double-ended queue)の実装。
全ての演算をΘ(1)ステップで実装すること。
front-insert-queue, rear-insert-queue, front-delete-queueは通常のqueueの手続きを修正すればΘ(1)ステップの手続きとなるが、rear-delete-queueは何も考えずに実装するとΘ(n)ステップの手続きとなる。どうやって実装するのか良く分からないのでググってみると双方向リストにすればヨサゲ。
ということでキューに格納する値を (値 前の値へのポインタ 後ろの値へのポインタ)というリスト構造とする。

(define (make-queue)
  (let ((front-ptr '())
        (rear-ptr '()))
    (define (make-item value) (list value '() '()))
    (define (item-value item) (car item))
    (define (prev-item item) (car (cdr item)))
    (define (next-item item) (car (cdr (cdr item))))
    (define (set-prev-item! item prev) (set! (car (cdr item)) prev))
    (define (set-next-item! item next) (set! (car (cdr (cdr item))) next))
    (define (set-front-ptr! item) (set! front-ptr item))
    (define (set-rear-ptr! item) (set! rear-ptr item))
    (define (empty-queue?) (null? front-ptr))
    (define (front-queue)
      (if (empty-queue?)
          (error "FRONT called with an empty queue")
          (print-queue)))
    (define (rear-queue)
      (if (empty-queue?)
          (error "REAR called with an empty queue")
          (item-value rear-ptr)))
    (define (front-insert-queue! value)
      (let ((new-item (make-item value)))
        (cond ((empty-queue?)
               (set-front-ptr! new-item)
               (set-rear-ptr! new-item)
               (print-queue))
              (else
               (set-next-item! new-item front-ptr)
               (set-prev-item! front-ptr new-item)
               (set-front-ptr! new-item)
               (print-queue)))))
    (define (rear-insert-queue! value)
      (let ((new-item (make-item value)))
        (cond ((empty-queue?)
               (set-front-ptr! new-item)
               (set-rear-ptr! new-item)
               (print-queue))
              (else
               (set-prev-item! new-item rear-ptr)
               (set-next-item! rear-ptr new-item)
               (set-rear-ptr! new-item)
               (print-queue)))))
    (define (front-delete-queue!)
      (cond ((empty-queue?)
             (error "DELETE! called with an empty queue"))
            (else
             (if (eq? front-ptr rear-ptr)
                 (begin (set-front-ptr! '())
                        (set-rear-ptr! '()))
                 (begin (set-front-ptr! (next-item front-ptr))
                        (set-prev-item! front-ptr '())))
             (print-queue))))
    (define (rear-delete-queue!)
      (cond ((empty-queue?)
             (error "DELETE! called with an empty queue"))
            (else
             (if (eq? front-ptr rear-ptr)
                 (begin (set-front-ptr! '())
                        (set-rear-ptr! '()))
                 (begin (set-rear-ptr! (prev-item rear-ptr))
                        (set-next-item! rear-ptr '())))
             (print-queue))))
    (define (print-queue)
      (define (iter item value-list)
        (if (null? (next-item item))
            (append value-list (list (item-value item)))
            (iter (next-item item) (append value-list (list (item-value item))))))
      (if (empty-queue?)
          '()
          (iter front-ptr '())))
    (define (dispatch m)
      (cond ((eq? m 'front-insert-queue!) front-insert-queue!)
            ((eq? m 'rear-insert-queue!) rear-insert-queue!)
            ((eq? m 'front-delete-queue!) front-delete-queue!)
            ((eq? m 'rear-delete-queue!) rear-delete-queue!)
            ((eq? m 'front-queue) front-queue)
            ((eq? m 'rear-queue) rear-queue)
            ((eq? m 'print-queue) print-queue)
            (else
             (error "Undefined operation -- MAKE-QUEUE" m))
      ))
    dispatch))

テスト

(define q1 (make-queue))
; q1
q1
; #<closure (make-queue dispatch)>
((q1 'front-queue))
; *** ERROR: FRONT called with an empty queue
; Stack Trace:
; _______________________________________
((q1 'print-queue))
; ()
((q1 'front-insert-queue!) 'a)
; (a)
((q1 'front-insert-queue!) 'b)
; (b a)
((q1 'rear-insert-queue!) 'c)
; (b a c)
((q1 'front-queue))
; (b a c)
((q1 'rear-queue))
; c
((q1 'front-delete-queue!))
; (a c)
((q1 'rear-delete-queue!))
; (a)
((q1 'rear-delete-queue!))
; ()
((q1 'rear-delete-queue!))
; *** ERROR: DELETE! called with an empty queue
; Stack Trace:
; _______________________________________

((q1 'front-delete-queue!))
; *** ERROR: DELETE! called with an empty queue
; Stack Trace:
; _______________________________________
((q1 'front-insert-queue!) 'a)
; (a)
((q1 'front-delete-queue!))
; ()

ということでキューの動作はOKな感じだが、キューの内容を表示するためのprint-queueの実装がΘ(n)な気が…。これで良いのかなぁ?