The mutators set-car! set_head and set-cdr! set_tail enable us to use pairs to construct data structures that cannot be built with cons, pair, car, head, and cdr tail alone. This section shows how to use pairs to represent a data structure called a queue. Section 3.3.3 will show how to represent data structures called tables.
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). Figure 3.35 Figure 3.36 shows an initially empty queue in which the items a and b are inserted. Then a is removed, c and d are inserted, and b is removed. Because items are always removed in the order in which they are inserted, a queue is sometimes called a FIFO (first in, first out) buffer.
| Original | JavaScript | |||||||||||||||||
Figure 3.35 Queue operations. |
Figure 3.36 Queue operations. |
In terms of data abstraction, we can regard a queue as defined by the following set of operations:
-
a constructor:
(make-queue) make_queue()
returns an empty queue (a queue containing no items). -
a predicate:
(empty-queue? queue) is_empty_queue($queue$)
tests if the queue is empty. -
a selector:
(front-queue queue) 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. -
two mutators:
(insert-queue! queue item) insert_queue($queue$, $item$)
inserts the item at the rear of the queue and returns the modified queue as its value.
(delete-queue! queue) 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 sequence of items, we could certainly represent it as an ordinary list; the front of the queue would be the car head of the list, inserting an item in the queue would amount to appending a new element at the end of the list, and deleting an item from the queue would just be taking the cdr tail of the list. However, this representation is inefficient, because in order to insert an item we must scan the list until we reach the end. Since the only method we have for scanning a list is by successive cdr tail operations, this scanning requires $\Theta(n)$ steps for a list of $n$ items. A simple modification to the list representation overcomes this disadvantage by allowing the queue operations to be implemented so that they require $\Theta(1)$ steps; that is, so that the number of steps needed is independent of the length of the queue.
The difficulty with the list representation arises from the need to scan to find the end of the list. The reason we need to scan is that, although the standard way of representing a list as a chain of pairs readily provides us with a pointer to the beginning of the list, it gives us no easily accessible pointer to the end. The modification that avoids the drawback is to represent the queue as a list, together with an additional pointer that indicates the final pair in the list. That way, when we go to insert an item, we can consult the rear pointer and so avoid scanning the list.
A queue is represented, then, as a pair of pointers, front-ptr front_ptr and rear-ptr, rear_ptr, which indicate, respectively, the first and last pairs in an ordinary list. Since we would like the queue to be an identifiable object, we can use cons pair to combine the two pointers. Thus, the queue itself will be the cons pair of the two pointers. Figure 3.37 Figure 3.38 illustrates this representation.
| Original | JavaScript | |
Figure 3.37
Implementation of a queue as a list with front and rear pointers.
|
Figure 3.38
Implementation of a queue as a list with front and rear pointers.
|
To define the queue operations we use the following procedures,functions, which enable us to select and to modify the front and rear pointers of a queue:
| Original | JavaScript |
| (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)) | function front_ptr(queue) { return head(queue); } function rear_ptr(queue) { return tail(queue); } function set_front_ptr(queue, item) { set_head(queue, item); } function set_rear_ptr(queue, item) { set_tail(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:
| Original | JavaScript |
| (define (empty-queue? queue) (null? (front-ptr queue))) | function is_empty_queue(queue) { return is_null(front_ptr(queue)); } |
| Original | JavaScript |
| (define (make-queue) (cons '() '())) | function make_queue() { return pair(null, null); } |
| Original | JavaScript |
| (define (front-queue queue) (if (empty-queue? queue) (error "FRONT called with an empty queue" queue) (car (front-ptr queue)))) | function front_queue(queue) { return is_empty_queue(queue) ? error(queue, "front_queue called with an empty queue") : head(front_ptr(queue)); } |
To insert an item in a queue, we follow the method whose result is indicated in figure 3.40. figure 3.40. We first create a new pair whose car head is the item to be inserted and whose cdr tail is the empty list. If the queue was initially empty, we set the front and rear pointers of the queue to this new pair. Otherwise, we modify the final pair in the queue to point to the new pair, and also set the rear pointer to the new pair.
| Original | JavaScript | |
Figure 3.39
Result of using (insert-queue! q 'd) on
the queue of figure 3.37.
|
Figure 3.40
Result of using
insert_queue(q, "d") on the
queue of figure 3.38.
|
| Original | JavaScript |
| (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)))) | function insert_queue(queue, item) { const new_pair = pair(item, null); if (is_empty_queue(queue)) { set_front_ptr(queue, new_pair); set_rear_ptr(queue, new_pair); } else { set_tail(rear_ptr(queue), new_pair); set_rear_ptr(queue, new_pair); } return queue; } |
To delete the item at the front of the queue, we merely modify the front pointer so that it now points at the second item in the queue, which can be found by following the cdr tail pointer of the first item (see figure 3.41figure 3.42):[1]
| Original | JavaScript | |
Figure 3.41
Result of using (delete-queue! q) on the
queue of figure 3.39.
|
Figure 3.42
Result of using delete_queue(q)
on the queue of figure 3.40.
|
| Original | JavaScript |
| (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))) | function delete_queue(queue) { if (is_empty_queue(queue)) { error(queue, "delete_queue called with an empty queue"); } else { set_front_ptr(queue, tail(front_ptr(queue))); return queue; } } |
| Original | JavaScript |
| (define q1 (make-queue)) | const q1 = make_queue(); |
| Original | JavaScript |
| (insert-queue! q1 'a) ((a) a) | insert_queue(q1, "a"); [["a", null], ["a", null]] |
| Original | JavaScript |
| (insert-queue! q1 'b) ((a b) b) | insert_queue(q1, "b"); [["a", ["b", null]], ["b", null]] |
| Original | JavaScript |
| (delete-queue! q1) ((b) b) | delete_queue(q1); [["b", null], ["b", null]] |
| Original | JavaScript |
| (delete-queue! q1) (() b) | delete_queue(q1); [null, ["b", null]] |
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 JavaScript 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 function 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 function print-queue print_queue that takes a queue as input and prints the sequence of items in the queue.
| Original | JavaScript |
| (define (make-queue) (let ((front-ptr $\ldots$ ) (rear-ptr $\ldots$ )) definitions of internal procedures (define (dispatch m) $\ldots$) dispatch)) | function make_queue() { let front_ptr = $\ldots$; let rear_ptr = $\ldots$; $\langle{}$declarations of internal functions$\rangle$ function dispatch(m) {$\ldots$} return dispatch; } |
double-ended queue) is a sequence in which items can be inserted and deleted at either the front or either at the front or at the rear. Operations on deques are the constructor make-deque, make_deque, the predicate empty-deque, is_empty_deque, selectors front-deque front_deque and rear-deque, rear_deque, and mutators front-insert-deque!, front_insert_deque, front-delete-deque!, front_delete_deque, rear-insert-deque!, rear_insert_deque, and rear-delete-deque. rear_delete_deque. Show how to represent deques using pairs, and give implementations of the operations.[2] All operations should be accomplished in $\Theta(1)$ steps.