1 ;; Exercise 3.22.  Instead of representing a queue as a pair of pointers, we can build a queue as a procedure with local state. The local state will consist of pointers to the beginning and the end of an ordinary list. Thus, the make-queue procedure will have the form
2 
3 (define (make-queue)
4   (let ((front-ptr '())
5 	(rear-ptr '()))
6     (define (set-front-ptr! item)
7       (set! front-ptr item))
8     (define (set-rear-ptr! item)
9       (set! rear-ptr item))
10     (define (dispatch m)
11       (cond ((eq? m 'front-ptr) front-ptr)
12 	    ((eq? m 'rear-ptr) rear-ptr)
13 	    ((eq? m 'set-front-ptr!) set-front-ptr!)
14 	    ((eq? m 'set-rear-ptr!) set-rear-ptr!)))
15     dispatch))
16 
17 ;; Complete the definition of make-queue andprovide implementations of the queue operations using this representation. 
18 
19 
20 (define (test-case actual expected)
21   (newline)
22   (display "Actual:   ")
23   (display actual)
24   (newline)
25   (display "Expected: ")
26   (display expected)
27   (newline))
28 
29 ;; the four basic accessor/setter methods
30 
31 (define (front-ptr queue) (queue 'front-ptr))
32 (define (rear-ptr queue) (queue 'rear-ptr))
33 (define (set-front-ptr! queue item)
34   ((queue 'set-front-ptr!) item))
35 (define (set-rear-ptr! queue item)
36   ((queue 'set-rear-ptr!) item))
37 
38 ;; the rest remain untouched
39 
40 (define (empty-queue? queue) (null? (front-ptr queue)))
41 (define (front-queue queue)
42   (if (empty-queue? queue)
43       (error "FRONT called with an empty queue" queue)
44       (car (front-ptr queue))))
45 (define (insert-queue! queue item)
46   (let ((new-pair (cons item '())))
47     (cond ((empty-queue? queue)
48 	   (set-front-ptr! queue new-pair)
49 	   (set-rear-ptr! queue new-pair)
50 	   queue)
51 	  (else
52 	   (set-cdr! (rear-ptr queue) new-pair)
53 	   (set-rear-ptr! queue new-pair)
54 	   queue))))
55 (define (delete-queue! queue)
56   (cond ((empty-queue? queue)
57 	 (error "DELETE! called with an empty queue" queue))
58 	(else
59 	 (set-front-ptr! queue (cdr (front-ptr queue)))
60 	 queue)))
61 
62 ;; Exercise 3.21
63 
64 ;; Define a procedure print-queue that takes a queue as input and prints the sequence of items in the queue. 
65 
66 (define (print-queue queue)
67   (newline)
68   (newline)
69   (display (front-ptr queue))
70   (newline)
71   (front-ptr queue))
72 
73 (define q (make-queue))
74 (insert-queue! q 'a)
75 (test-case (print-queue q) '(a))
76 (insert-queue! q 'b)
77 (test-case (print-queue q) '(a b))
78 (insert-queue! q 'c)
79 (test-case (print-queue q) '(a b c))
80 (insert-queue! q 'd)
81 (test-case (print-queue q) '(a b c d))
82 (insert-queue! q 'e)
83 (test-case (print-queue q) '(a b c d e))
84 (delete-queue! q)
85 (test-case (print-queue q) '(b c d e))
86 (delete-queue! q)
87 (test-case (print-queue q) '(c d e))
88 
89 
90     ;; (define (empty-queue?)
91     ;;   (null? front-ptr))
92     ;; (define (set-front-ptr! item)
93     ;;   (cond ((empty-queue?) 
94     ;; 	     (set! front-ptr item)
95     ;; 	     (set! rear-ptr item))
96     ;; 	    (else 
97     ;; 	     (set-cdr! rear-ptr
98     ;; 	  ...))))