이 문제는 데크(deque, double-ended queue)라는 데이터 구조를 만드는 문제입니다.

자료구조를 아직 제대로 공부하지 못해 정확한 것은 잘 모르지만,

여기서 나오는 설명대로 프로시저를 만들었습니다.

처음에는 queue처럼 각자가 뒤의 것을 가리키도록 만들었으나

rear-delete를 구현하기 어렵다는 것을 알았습니다.

정확하게는 문제에 나오는 조건에 따라

모든 연산이 Θ(1)이 나오는 것에 맞춰야하기 때문입니다.

rear-delete는 제일 뒤에 있는 원소를 제거합니다.

그럼 rear-ptr을 그 앞에 있는 것을 가리키도록 하면 됩니다.

하지만 그 어디에도 rear-ptr이 가리키는 대상 앞에 있는 것에 대한 정보가 없습니다.

front-delete의 경우 front-ptr이 가리키는 대상이

그 다음 것에 대한 정보를 가지고 있습니다.

하지만 rear-delete의 경우 그러한 정보가 없으니 난감합니다.

따라서 전에 어설프게 자료구조를 공부한터라 이름은 정확하게 모르지만,

해당 원소가 자신의 앞의 것과 뒤의 것의 포인터를 저장하는 구조로 만들었습니다.

즉, 해당 원소의 car은 그 원소의 값(item)을

해당 원소의 cdr은 또 하나의 cons로

car은 앞의 것을 cdr은 뒤의 것을 가리키도록 하였습니다.

그렇게 하여 rear-delete의 문제를 해결하였습니다.

이렇게 데이터 구조를 바꾸었기에 나머지 것들도 전부 바꿨습니다.

실행은 잘 되네요.^^

참조

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

; exercise 3.23
(define (front-ptr deque) (car deque))
(define (rear-ptr deque) (cdr deque))
(define (set-front-ptr! deque item) (set-car! deque item))
(define (set-rear-ptr! deque item) (set-cdr! deque item))

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

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

(define (rear-deque deque)
  (if (empty-deque? deque)
      (error "REAR called with an empty deque" deque)
      (car (rear-ptr deque))))

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

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

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

(define (rear-delete-deque! deque)
  (cond ((empty-deque? deque)
         (error "DELETE! called with an empty deque" deque))
        (else
         (set-rear-ptr! deque (car (cdr (rear-ptr deque))))
         (set-cdr! (cdr (rear-ptr deque)) '()) ; rear가 된 것에 cdr을 null로 맞춤.
         deque)))

; exercise 3.21
(define (print-deque deque)
  (define (print-iter q)
    (cond ((null? q) null)
          (else (display (car q))
                (display " ")
                (print-iter (cdr (cdr q))))))
  (print-iter (front-ptr deque))
  (newline))

; execute
(define q1 (make-deque))
(print-deque q1) ; null
(front-insert-deque! q1 'a)
(print-deque q1) ; a
(rear-insert-deque! q1 'b)
(print-deque q1) ; a b
(front-insert-deque! q1 'c)
(print-deque q1) ; c a b
(rear-insert-deque! q1 'd)
(print-deque q1) ; c a b d
(rear-delete-deque! q1)
(print-deque q1) ; c a b
(front-delete-deque! q1)
(print-deque q1) ; a b
(rear-delete-deque! q1)
(print-deque q1) ; a
(front-delete-deque! q1)
(print-deque q1) ; null

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.