练习3-23

原文

Exercise 3.23. A deque (“double-ended queue”) is a sequence in which items can be inserted and deleted at either the front or the rear. Operations on deques are the constructor make-deque, the predicate empty-deque?, selectors front-deque and rear-deque, and mutators front-insertdeque!, rear-insert-deque!, front-delete-deque!, and rear-delete-deque!. Show how to represent deques using pairs, and give implementations of the operations.23 All operations should be accomplished in (1) steps.

补充

双端队列（double-ended queue，简称为deque）表示可以在前面或后面进行增加或删除其在元素的抽象数据类型。它也被称为头-尾链表（head-tail linked list）。Deque也可以被写作dequeue，但在技术文献或技术写作时已不合时宜，因为dequeue也是一个表示”从队列中删除“的动词。它和只能在队列一端增加或删除元素的队列抽象数据类型或者先进先出（FIFO）不同。

（注：以上内容来自维基百科）

代码

 (define (make-deque) (cons ‘() ‘())) 
 (define (front-ptr deque) (car deque)) 
 (define (rear-ptr deque) (cdr deque)) 
 (define (empty-deque? deque) (null? (front-ptr deque))) 
 (define (set-front! deque item) (set-car! deque item)) 
 (define (set-rear! deque item) (set-cdr! deque item)) 

 (define (get-item deque end) 
   (if (empty-deque? deque) 
     (error "GET-ITEM -- Can‘t retrieve item from empty deque" deque) 
     (caar (end deque)))) 

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

 (define (front-delete-deque deque) 
   (cond ((empty-deque? deque) (error "FRONT-DELETE-DEQUE -- Can‘t delete from empty deque" deque)) 
         (else (set-front! deque (cdr (front-ptr deque))) 
               (or (empty-deque? deque) (set-cdr! (car (front-ptr deque)) nil))))) 

 (define (rear-delete-deque deque) 
   (cond ((empty-deque? deque) (error "REAR-DELETE-DEQUE -- Can‘t delete from empty deque" deque)) 
         (else (set-rear! deque (cdar (rear-ptr deque))) 
               (if (null? (rear-ptr deque)) (set-front! deque nil) 
                 (set-cdr! (rear-ptr deque) nil))))) 

 (define (front-insert-deque! deque item) (insert-deque! deque item ‘front)) 
 (define (rear-insert-deque! deque item) (insert-deque! deque item ‘rear)) 
 (define (front-deque deque) (get-item deque front-ptr)) 
 (define (rear-deque deque) (get-item deque rear-ptr)) 

 (define (print-deque deque) 
   (define (iter res dq) 
     (if (or (null? dq) (empty-deque? dq)) 
         (iter (append res (list (caaar dq)))
               (cons (cdar dq) (cdr deque))))) 
   (iter nil deque))