연습문제 3.23

Deque 문제는 양방향 링크 리스트로 푼다.

(define (make-deque) (cons '() '()))

(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 (front-deque deque)
  (if (empty-deque? deque)
      (error "Empty deque")
      (cadr (front-ptr deque))))
(define (rear-deque deque)
  (if (empty-deque? deque)
      (error "Empty deque")
      (cadr (rear-ptr deque))))

(define (front-insert-deque! deque item)
  (let ((ele (list '() item '())))
    (cond ((empty-deque? deque)
           (begin
             (set-front-ptr! deque ele)
             (set-rear-ptr! deque ele)))
          (else
           (begin
             (set-car! (cddr ele) (front-ptr deque))
             (set-car! (front-ptr deque) ele)
             (set-front-ptr! deque ele))))))
(define (rear-insert-deque! deque item)
  (let ((ele (list '() item '())))
    (cond ((empty-deque? deque)
           (begin
             (set-front-ptr! deque ele)
             (set-rear-ptr! deque ele)))
          (else
           (begin
             (set-car! ele (rear-ptr deque))
             (set-car! (cddr (rear-ptr deque)) ele)
             (set-rear-ptr! deque ele))))))

(define (front-delete-deque! deque)
    (cond ((empty-deque? deque)
           (error "Empty queue " deque))
          (else
           (begin
             (set-front-ptr! deque (caddr (front-ptr deque)))
             (set-car! (car (front-ptr deque)) '())))))

(define (rear-delete-deque! deque)
    (cond ((empty-deque? deque)
           (error "Empty queue " deque))
          (else
           (begin
             (set-rear-ptr! deque (car (rear-ptr deque)))
             (set-car! (cddr (rear-ptr deque)) '())))))


(define (print-deque deque)
  (define (print-dl double-list)
    (if (null? double-list)
        (display "")
        (begin
          (display (cadr double-list))
          (print-dl (caddr double-list)))))
  (cond ((empty-deque? deque) (display ""))
        (else
         (print-dl (front-ptr deque)))))