#lang racket ; The queue motivated by chapter 3 of SICP ; a queue is a mutable pair, where the mcar is a pointer to the ; front of the queue, and the mcdr is a pointer to the rear ; of the queue. You insert at the rear (on the right) and remove ; from the front (on the left). ; The actual queue is a mutable-list formed by chaining mutable ; pairs. (define (q-front-ptr queue) (mcar queue)) (define (q-rear-ptr queue) (mcdr queue)) (define (q-set-front-ptr! queue item) (set-mcar! queue item)) (define (q-set-rear-ptr! queue item) (set-mcdr! queue item)) (define (q-empty? queue) (null? (q-front-ptr queue))) (define (q-make) (mcons '() '()) ) (define (q-front queue) (if (q-empty? queue) (error "front-of-queue called with an empty queue" queue) (mcar (q-front-ptr queue)) ) ) (define (q-insert! queue item) (let ( (new-pair (mcons item '() ) ) ) (cond ( (q-empty? queue) (q-set-front-ptr! queue new-pair) (q-set-rear-ptr! queue new-pair) queue) (else (set-mcdr! (q-rear-ptr queue) new-pair) (q-set-rear-ptr! queue new-pair) queue) ) ) ) (define (q-remove! queue) (cond ( (q-empty? queue) (error "remove-queue! called with an empty queue" queue) ) (else (let ( (front (mcar (q-front-ptr queue))) ) (q-set-front-ptr! queue (mcdr (q-front-ptr queue))) front) ) ) ) (define q (q-make)) (q-insert! q 1) (q-front q) (q-insert! (q-insert! q 2) 3) (q-front q) (q-remove! q) (q-remove! q) ;(define (q-to-list q) ) ;(define (q-from-list l) )