SICP Exercise 3.22

sicp

Question

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.

Answer

(define (make-queue)
  (let ((front-ptr '())
        (rear-ptr '()))
    (define (empty-queue?)
      (null? front-ptr))
    (define (front-queue)
      (if (empty-queue?)
          (error "FRONT called with an empty queue")
          (car front-ptr)))
    (define (set-front-ptr! i)
      (set! front-ptr i))
    (define (set-rear-ptr! i)
      (set! rear-ptr i))
    (define (insert-queue! i)
      (define new-pair (cons i '()))
      (cond ((empty-queue?)
             (set-front-ptr! new-pair)
             (set-rear-ptr! new-pair)
             (cons front-ptr rear-ptr))
            (else
             (set-cdr! rear-ptr new-pair)
             (set-rear-ptr! new-pair)
             (cons front-ptr rear-ptr))))
    (define (delete-queue!)
      (cond ((empty-queue?)
             (error "DELETE! called with an empty queue"))
            (else
             (set-front-ptr! (cdr front-ptr))
             (cons front-ptr rear-ptr))))
    (define (dispatch m)
      (cond ((eq? m 'insert-queue!) insert-queue!)
            ((eq? m 'delete-queue!) delete-queue!)
            (else
             (error "UNKNOWN METHOD -- make-queue"))))
    dispatch))

(define (insert-queue! q i) ((q 'insert-queue!) i))
(define (delete-queue! q) ((q 'delete-queue!)))

Test:

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

Results:

((a) a)
((a b) b)
((a b c) c)
((b c) c)
((c) c)
(() c)