set-cdr! allows us to create a data structure that we
could not have implemented efficiently before: a queue. A queue is a sequence in which items are inserted at one end (called the rear of the queue) and deleted from the other end (the front). Because items are always removed in the order in which they are inserted, a queue is sometimes called a FIFO (first in, first out).
Assume we have the functions
make-queue, which returns a new queue,
insert-queue!, which adds a new element to a queue, and
delete-queue!, which removes an element in a queue (we are going to implement them soon!). Lets examine the mechanisms of a queue.
In terms of data abstraction, we can regard a queue as defined by the following set of operations:
(make-queue)returns an empty queue (a queue containing no items).
(empty-queue? <_queue_>)tests if the queue is empty.
(front-queue <_queue_>)returns the object at the front of the queue, signaling an error if the queue is empty. It does not modify the queue.
(insert-queue! <_queue_> <_item_>)inserts the item at the rear of the queue and returns the modified queue as its value.
(delete-queue! <_queue_>)removes the item at the front of the queue and returns the modified queue as its value, signaling an error if the queue is empty before the deletion.
Because a queue is a list of items, we can technically represent it with an ordinary list. The front of the queue will be the
car of the list, inserting a new element will be equivalent to appending a new pair at the end. Deleting an item will just be the
cdr. Why don't we go with this implementation? The problem is the run time. To add an item to the back of a list, we have to go through a series of
cdrs. If the list is really long, it will take us a really long time to find the last pair. The run time for this is
n is the length of the list.
A list allows us access to the first item in constant time, but when you need to find the last pair, it takes a long time. We can solve this by storing and updating the pointer to the backmost pair.
Looking at the queue above, we see that we store two pointers: one that points to the front of the list and one to the back. If we try to add a new item,
'd, to the queue, the structure will be changed into the following:
When we want to find the last pair of
q, we can follow the
(cdr q) pointer.
To define the queue operations, we use the following procedures, which enable us to select and modify the front and rear pointers of a queue:
(define (front-ptr queue) (car queue)) (define (rear-ptr queue) (cdr queue)) (define (set-front-ptr! queue item) (set-car! queue item)) (define (set-rear-ptr! queue item) (set-cdr! queue item))
Now we can implement the actual queue operations. We will consider a queue to be empty if its front pointer is the empty list:
(define (empty-queue? queue) (null? (front-ptr queue)))
make-queue constructor returns, as an initially empty queue, a pair whose
cdr are both the empty list:
(define (make-queue) (cons '() '()))
To select the item at the front of the queue, we return the
car of the pair indicated by the front pointer:
(define (front-queue queue) (if (empty-queue? queue) (error "FRONT called with an empty queue" queue) (car (front-ptr queue))))
We will follow the general algorithm outlined before:
consa new pair containing the new item
rear-ptrto this new pair
If the queue isn't empty, we find the final pair, change its
cdr to the newly made pair and update the
(define (insert-queue! queue item) (let ((new-pair (cons item '()))) (cond ((empty-queue? queue) (set-front-ptr! queue new-pair) (set-rear-ptr! queue new-pair) queue) (else (set-cdr! (rear-ptr queue) new-pair) (set-rear-ptr! queue new-pair) queue))))
To delete from a queue, we can simply change the
front-ptr to point to the
(define (delete-queue! queue) (cond ((empty-queue? queue) (error "DELETE! called with an empty queue" queue)) (else (set-front-ptr! queue (cdr (front-ptr queue))) queue)))
If starting from the queue above we decide to delete the first time, the change will only be where the
front-ptr points to:
set-cdr! allows us to implement a new data structure (the queue) much more efficiently than what
cdr alone can build.