Using setcar!
and setcdr!
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 makequeue
, which returns a new queue, insertqueue!
, which adds a new element to a queue, and deletequeue!
, which removes an element in a queue (we are going to implement them soon!). Lets examine the mechanisms of a queue.
Operation  Resulting Queue 

(define q (makequeue)) 

(insertqueue! q 'a) 
a 
(insertqueue! q 'b) 
a b 
(deletequeue! q) 
b 
(insertqueue! q 'c) 
b c 
(insertqueue! q 'd) 
b c d 
(deletequeue! q) 
c d 
In terms of data abstraction, we can regard a queue as defined by the following set of operations:
(makequeue)
returns an empty queue (a queue containing no items).(emptyqueue? <_queue_>)
tests if the queue is empty.(frontqueue <_queue_>)
returns the object at the front of the queue, signaling an error if the queue is empty. It does not modify the queue.(insertqueue! <_queue_> <_item_>)
inserts the item at the rear of the queue and returns the modified queue as its value.(deletequeue! <_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 cdr
s. 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)
, where 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 (frontptr queue)
(car queue))
(define (rearptr queue)
(cdr queue))
(define (setfrontptr! queue item)
(setcar! queue item))
(define (setrearptr! queue item)
(setcdr! 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 (emptyqueue? queue)
(null? (frontptr queue)))
The makequeue
constructor returns, as an initially empty queue, a pair whose car
and cdr
are both the empty list:
(define (makequeue)
(cons '() '()))
To select the item at the front of the queue, we return the car
of the pair indicated by the front pointer:
(define (frontqueue queue)
(if (emptyqueue? queue)
(error "FRONT called with an empty queue" queue)
(car (frontptr queue))))
We will follow the general algorithm outlined before:
cons
a new pair containing the new itemfrontptr
and rearptr
to this new pairIf the queue isn't empty, we find the final pair, change its cdr
to the newly made pair and update the rearptr
.
(define (insertqueue! queue item) (let ((newpair (cons item '()))) (cond ((emptyqueue? queue) (setfrontptr! queue newpair) (setrearptr! queue newpair) queue) (else (setcdr! (rearptr queue) newpair) (setrearptr! queue newpair) queue))))
To delete from a queue, we can simply change the frontptr
to point to the
next pair.
(define (deletequeue! queue)
(cond ((emptyqueue? queue)
(error "DELETE! called with an empty queue" queue))
(else
(setfrontptr! queue (cdr (frontptr queue)))
queue)))
If starting from the queue above we decide to delete the first time, the change will only be where the frontptr
points to:
setcar!
and setcdr!
allows us to implement a new data structure (the queue) much more efficiently than what cons
, car
, and cdr
alone can build.