# Representing a queue as a procedure with local state

From SICP:

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

(define (make-queue)
(let ((front-ptr ...)
(rear-ptr ...))
<definitions of internal procedures>
(define (dispatch m) ...)
dispatch))


Complete the definition of make-queue and provide implementations of the queue operations using this representation.

I wrote the following solution:

(define (make-queue)
(let ((front-ptr '())
(rear-ptr '()))
(define (set-front-ptr! ptr) (set! front-ptr ptr))
(define (set-rear-ptr! ptr) (set! rear-ptr ptr))
(define (empty?) (null? front-ptr))
(define (front-queue)
(if (empty?)
(error "FRONT called with an empty queue" front-ptr)
(car front-ptr)))
(define (insert! item)
(let ((new-pair (cons item '())))
(cond ((empty?)
(set-front-ptr! new-pair)
(set-rear-ptr! new-pair)
dispatch)
(else
(set-cdr! rear-ptr new-pair)
(set-rear-ptr! new-pair)
dispatch))))
(define (delete!)
(cond ((empty?)
(error "DELETE! called with an empty queue" first-ptr))
(else
(set-front-ptr! (cdr front-ptr))))
dispatch)
(define (print) front-ptr)
(define (dispatch m)
(cond ((eq? m 'insert!) insert!)
((eq? m 'front-ptr) front-ptr)
((eq? m 'rear-ptr) rear-ptr)
((eq? m 'empty?) empty?)
((eq? m 'delete!) delete!)
((eq? m 'print) print)
(else (error "No such procedure: dispatch" m))))
dispatch))

(define q1 (make-queue))
((((q1 'insert!) 'a) 'print))
((((q1 'insert!) 'b) 'print))
((((q1 'delete!)) 'print))
((((q1 'delete!)) 'print))


How can it be improved?

• Looking through your questions, you have a lot of titles that unnecessarily contain tags. You should only use titles to briefly describe what your program/method does. Commented Jan 17, 2014 at 4:48

(define (queue-insert! q item)