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