Here is the solution for a queue that uses message passing.
Note that you do not pass a queue as an input to a queue object. It is already a queue!
(define (make-queue) (let ((front-ptr '()) (rear-ptr '())) ; empty-queue? is written to align with the way front-ptr ; and rear-ptr were given, above (define (empty-queue?) (null? front-ptr)) ; peek returns the datum at the front of the queue ; peek returns #f if the queue is empty (define (peek) (cond ((empty-queue?) (error "Empty queue. :-(")) (else (car front-ptr)))) ; insert-queue! plays out differently depending on whether the queue ; is currently empty or not (define (insert-queue! datum) (let ((new-node (cons datum '()))) (cond ((empty-queue?) (set! front-ptr new-node) (set! rear-ptr new-node)) (else (set-cdr! rear-ptr new-node) (set! rear-ptr new-node))))) ; delete-queue! has three possibilties: ; * empty queue ; * one element in queue ; * more than one element in queue (define (delete-queue!) (cond ((empty-queue?) (error "Empty queue. :-(")) (else ; store the datum at the head of the queue (let ((return-value (peek))) ; update the front pointer (set! front-ptr (cdr front-ptr)) ; If there was only one thing in the queue, then the ; rear-ptr will need to be set to nil (if (null? front-ptr) (set! rear-ptr '()) #f) ; Now return the element of the queue return-value)))) (define (dispatch message) (cond ((eq? message 'insert-queue!) insert-queue!) ((eq? message 'delete-queue!) delete-queue!) ((eq? message 'peek) peek) ((eq? message 'empty?) empty-queue?))) dispatch))
Here is a stack abstraction that is similar in approach:
(define (make-stack) (let ((top-ptr ())) (define (empty-stack?) (null? top-ptr)) (define (peek) (cond ((empty-stack?) #f) (else (car top-ptr)))) (define (push! datum) (let ((new-node (cons datum ()))) (cond ((empty-stack?) (set-top-ptr! new-node)) (else (set-cdr! new-node top-ptr) (set-top-ptr! new-node))))) (define (pop!) (let ((return-value (peek))) (if return-value (set-top-ptr! (cdr top-ptr))) return-value)) (define (set-top-ptr! node) (set! top-ptr node)) (define (dispatch msg) (cond ((eq? msg 'push!) push!) ((eq? msg 'pop!) pop!) ((eq? msg 'peek) peek) ((eq? msg 'empty?) empty-stack?))) dispatch))