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)
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 (define (front-delete-deque! deque)
54   (set-car! deque (link-next (car deque)))
55   (if (null? (car deque))
56       (set-cdr! deque '())
57       (set-link-prev! (car deque) '())))
58 (define (rear-delete-deque! deque)
59   (set-cdr! deque (link-prev (cdr deque)))
60   (if (null? (cdr deque))
61       (set-car! deque '())
62       (set-link-next! (cdr deque) '())))
63 (define (deque->list deque)
64   (link->list (car deque)))
65 
66 (define (print-deque deque)
67   (newline)
68   (newline)
69   (display (deque->list deque))
70   (newline)
71   deque)
72 
73 (define la (make-link 'a '() '()))
74 (define lb (make-link 'b '() '()))
75 (define lc (make-link 'c '() '()))
76 (define ld (make-link 'd '() '()))
77 (set-link-next! la lb)
78 (set-link-prev! lb la)
79 (set-link-next! lb lc)
80 (set-link-prev! lc lb)
81 (set-link-next! lc ld)
82 (set-link-prev! ld lc)
83 (test-case (link->list la) '(a b c d))
84 
85 (define dq (make-deque))
86 (front-insert-deque! dq 'a)
87 (test-case (print-deque dq) '(a))
88 (front-insert-deque! dq 'b)
89 (test-case (print-deque dq) '(b a))
90 (rear-insert-deque! dq 'c)
91 (test-case (print-deque dq) '(b a c))
92 (rear-insert-deque! dq 'd)
93 (test-case (print-deque dq) '(b a c d))
94 (front-delete-deque! dq)
95 (test-case (print-deque dq) '(a c d))
96 (rear-delete-deque! dq)
97 (test-case (print-deque dq) '(a c))
98 (test-case (front-deque dq) 'a)
99 (test-case (rear-deque dq) 'c)