Print-queue procedure

Ben Bitdiddle decides to test the queue implementation described above. He types in the procedures to the Lisp interpreter and proceeds to try them out:

(define q1 (make-queue))

(insert-queue! q1 'a)
((a) a)

(insert-queue! q1 'b)
((a b) b)

(delete-queue! q1)
((b) b)

(delete-queue! q1)
(() b)

''It's all wrong!'' he complains. ''The interpreter's response shows that the last item is inserted into the queue twice. And when I delete both items, the second b is still there, so the queue isn't empty, even though it's supposed to be.'' Eva Lu Ator suggests that Ben has misunderstood what is happening. ''It's not that the items are going into the queue twice,'' she explains. ''It's just that the standard Lisp printer doesn't know how to make sense of the queue representation. If you want to see the queue printed correctly, you'll have to define your own print procedure for queues.'' Explain what Eva Lu is talking about. In particular, show why Ben's examples produce the printed results that they do. Define a procedure print-queue that takes a queue as input and prints the sequence of items in the queue.


There are no comments yet.

Authentication required

You must log in to post a comment.

Login
(define (front-ptr queue) (mcar queue))
(define (rear-ptr queue) (mcdr queue))

(define (set-front-ptr! queue item) (set-mcar! queue item))
(define (set-rear-ptr! queue item) (set-mcdr! queue item))

(define (empty-queue? queue) (null? (front-ptr queue)))

(define (make-queue) (mcons '() '()))

(define (insert-queue! queue item)
  (let ((new-pair (mcons item '())))
    (cond ((empty-queue? queue)
           (set-front-ptr! queue new-pair)
           (set-rear-ptr! queue new-pair)
           queue)
          (else
           (set-mcdr! (rear-ptr queue) new-pair)
           (set-rear-ptr! queue new-pair)
           queue))))

(define (delete-queue! queue)
  (cond ((empty-queue? queue)
         (error "DELETE! called with an empty queue" queue))
        (else
         (set-front-ptr! queue (mcdr (front-ptr queue)))
         queue))) 

(define q1 (make-queue))


(define op1 (open-output-string))
(print-queue q1 op1)
(define display-result (get-output-string op1))
(check-equal? display-result "()")
(close-output-port op1)


(define op2 (open-output-string))
(print-queue (insert-queue! q1 'a) op2)
(define display-result-2 (get-output-string op2))
(check-equal? display-result-2 "{a}")
(close-output-port op2)


(define op3 (open-output-string))
(print-queue (insert-queue! q1 'b) op3)
(define display-result-3 (get-output-string op3))
(check-equal? display-result-3 "{a b}")
(close-output-port op3)


(define op4 (open-output-string))
(print-queue (delete-queue! q1) op4)
(define display-result-4 (get-output-string op4))
(check-equal? display-result-4 "{b}")
(close-output-port op4)


(define op5 (open-output-string))
(print-queue (delete-queue! q1) op5)
(define display-result-5 (get-output-string op5))
(check-equal? display-result-5 "()")
(close-output-port op5)