NoSyu의 주저리주저리 :: SICP Exercise 연습문제 3.21

이 문제는 큐(queue)에 관한 얘기를 하고 있습니다.

Lisp으로 짠 Queue를 실행시켜 결과를 확인하니 이상한 결과가 나오는 것입니다.

그래서 왜 이런 일이 발생하는지 이를 해결하기 위한 print-queue를 만드는 문제입니다.

결과의 앞부분을 보시면 정말 이상하게 나옵니다.

먼저 이를 해결하기 위한 print-queue를 만들었습니다.

print-queue는 안에 반복 프로시저를 두어 각 pair를 추적하여 print하도록 하였습니다.

다음으로 왜 이런 일이 발생하는지 알아보았습니다.

(define q1 (make-queue))

처음으로 queue를 만들면 위처럼 하나의 pair를 만듭니다.

이들은 모두 null을 가리킵니다.

(insert-queue! q1 'a)

이제 queue에 a라는 값을 넣습니다.

위와 같은 그림 형태로 잡혀지기에 결과가 ((a) a)가 되는 것입니다.

(insert-queue! q1 'b)

이제 b를 넣습니다.

그럼 car이 a를 가리키는 pair의 cdr이 car이 b를 가리키는 pair를 가리킵니다.

여기서도 그대로 출력하면 q1의 car이 출력되고 q1의 cdr이 출력됩니다.

(delete-queue! q1)

이제 queue에 있는 값 하나를 지웠습니다.

이는 q1의 car을 하나 뒤로 미루는 것이니 위 그림처럼 됩니다.

따라서 ((b) b)가 출력됩니다.

이제 delete를 한번 더 실행시켜 queue를 비웁니다.

이는 front-ptr를 null로 만드는 작업을 합니다.

하지만 q1의 cdr은 여전히 b를 가리키는 pair를 가리키기에 (() b)라는 결과가 나옵니다.

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 344

;;;SECTION 3.3.2
(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))

(define (empty-queue? queue) (null? (front-ptr queue)))
(define (make-queue) (cons '() '()))

(define (front-queue queue)
(if (empty-queue? queue)
(error "FRONT called with an empty queue" queue)
(car (front-ptr queue))))

(define (insert-queue! queue item)
(let ((new-pair (cons item '())))
    (cond ((empty-queue? queue)
           (set-front-ptr! queue new-pair)
           (set-rear-ptr! queue new-pair)
           queue)
          (else
           (set-cdr! (rear-ptr queue) new-pair)
           (set-rear-ptr! queue new-pair)
           queue))))

(define (delete-queue! queue)
(cond ((empty-queue? queue)
         (error "DELETE! called with an empty queue" queue))
        (else
         (set-front-ptr! queue (cdr (front-ptr queue)))
         queue)))

;; EXERCISE 3.21
(define q1 (make-queue))
(insert-queue! q1 'a)
(insert-queue! q1 'b)
(delete-queue! q1)
(delete-queue! q1)
(newline)

; answer
(define (print-queue queue)
(define (print-iter q)
    (cond ((null? q) null)
          (else (display (car q))
                (display " ")
                (print-iter (cdr q)))))
(print-iter (front-ptr queue))
(newline))
; execute
(define q1 (make-queue))
(print-queue q1)
(insert-queue! q1 'a)
(print-queue q1)
(insert-queue! q1 'b)
(print-queue q1)
(delete-queue! q1)
(print-queue q1)
(delete-queue! q1)
(print-queue q1)