1 ;; 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-insert-deque!, 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. 
2 
3 (define (test-case actual expected)
4   (newline)
5   (display "Actual:   ")
6   (display actual)
7   (newline)
8   (display "Expected: ")
9   (display expected)
10   (newline))
11 
12 (define (make-link val prev next)
13   (cons (cons val prev) next))
14 (define (link-value l)
15   (caar l))
16 (define (link-prev l)
17   (cdar l))
18 (define (link-next l)
19   (cdr l))
20 (define (set-link-prev! link prev)
21   (set-cdr! (car link) prev))
22 (define (set-link-next! link next)
23   (set-cdr! link next))
24 (define (link->list l)
25   (map car l))
26 
27 (define (make-deque)
28   (cons '() '()))
29 (define (empty-deque? deque)
30   (null? (car deque)))
31 (define (front-deque deque)
32   (link-value (car deque)))
33 (define (rear-deque deque)
34   (link-value (cdr deque)))
35 (define (front-insert-deque! deque item)
36   (let ((new-link (make-link item '() (car deque))))
37     (cond ((empty-deque? deque)
38 	   (set-car! deque new-link)
39 	   (set-cdr! deque new-link))
40 	  (else 
41 	   (set-link-prev! (car deque) new-link)
42 	   (set-car! deque new-link))))
43   deque)
44 (define (rear-insert-deque! deque item)
45   (let ((new-link (make-link item (cdr deque) '())))
46     (cond ((empty-deque? deque)
47 	   (set-car! deque new-link)
48 	   (set-cdr! deque new-link))
49 	  (else
50 	   (set-link-next! (cdr deque) new-link)
51 	   (set-cdr! deque new-link))))
52   deque)
53 
54 (define (front-delete-deque! deque) 
55   (if (empty-deque? deque)
56       (error "FRONT-DELETE-DEQUE! on empty deque"))
57   (set-car! deque (link-next (car deque)))
58   (if (null? (car deque))
59       (set-cdr! deque '())
60       (set-link-prev! (car deque) '())))
61 (define (rear-delete-deque! deque)
62   (if (empty-deque? deque)
63       (error "REAR-DELETE-DEQUE! on empty deque"))
64   (set-cdr! deque (link-prev (cdr deque)))
65   (if (null? (cdr deque))
66       (set-car! deque '())
67       (set-link-next! (cdr deque) '())))
68 (define (deque->list deque)
69   (link->list (car deque)))
70 
71 (define (print-deque deque)
72   (newline)
73   (newline)
74   (display (deque->list deque))
75   (newline)
76   (deque->list deque))
77 
78 (define la (make-link 'a '() '()))
79 (define lb (make-link 'b '() '()))
80 (define lc (make-link 'c '() '()))
81 (define ld (make-link 'd '() '()))
82 (set-link-next! la lb)
83 (set-link-prev! lb la)
84 (set-link-next! lb lc)
85 (set-link-prev! lc lb)
86 (set-link-next! lc ld)
87 (set-link-prev! ld lc)
88 (test-case (link->list la) '(a b c d))
89 
90 (define dq (make-deque))
91 (front-insert-deque! dq 'a)
92 (test-case (print-deque dq) '(a))
93 (front-insert-deque! dq 'b)
94 (test-case (print-deque dq) '(b a))
95 (rear-insert-deque! dq 'c)
96 (test-case (print-deque dq) '(b a c))
97 (rear-insert-deque! dq 'd)
98 (test-case (print-deque dq) '(b a c d))
99 (front-delete-deque! dq)
100 (test-case (print-deque dq) '(a c d))
101 (rear-delete-deque! dq)
102 (test-case (print-deque dq) '(a c))
103 (test-case (front-deque dq) 'a)
104 (test-case (rear-deque dq) 'c)