CSC 151-02, Fall 2006 : Schedule : Reading 39
Summary: We consider a new abstract data type, the queue. Queues provide a different order of access to data than do stacks.
Contents:
As you may recall, the stack is an abstract data type that
provides a few key operations: push something on to
the stack and pop the most recently pushed value.
Stacks have a host of applications, including mimicing the steps of
recursion, providing efficient computation in reverse-polish notation,
and matching tags in HTML. In all of these cases, it is important to
be able to deal with objects in a last in, first out
(LIFO) order.
However, there are also times we want a data type that provides access
to its elements on first-in, first-out
basis. For example,
you would consider it unfair if a clerk at a store handled customers
so that the one who had waited the least amount of time was
served first. Similarly, it might be prudent to treat that pile of
unpaid bills a little differently, adding new elements at the bottom
of the pile rather than the top. Paying off the most recent bill first,
as in a stack, can make one's other, older creditors a little testy.
A data structure that supports this pattern is called a queue. Like a line of people waiting for some service, a queue acquires new elements at one end (the rear of the queue) and releases old elements at the other (the front). Here is the abstract data type definition for queues, with the conventional names for the operations:
An obvious way to implement queues in Scheme is with a single list.
However since the first in is the first out, we cannot use the same end of
the list to both enqueue and dequeue
values. If we choose to represent the back of the queue as the
front of the list then we can implement enqueue
with cons, but then dequeue will be
more complex, and time consuming. Similarly, if we choose to represent
the front of the queue as the front of the list then we can implement
dequeue with car and cdr, but
then enqueue will be more complex, and time consuming.
A solution to this problem is to do both. We represent the rear
of the queue with a list, queue-rear, and the front
of the queue with a list, queue-front. For instance,
if the items in the queue were inserted in the order: a, b, c, d, the
a were dequeued, and then e and f were inserted,
then queue-front might be the list (b c d)
and queue-rear(f
e). If we want to enqueue an item, we simply cons
it onto queue-rear. If we want to dequeue an
item from the queue, and queue-front is not empty, then we
simply return the car of queue-front and set
queue-front equal to the cdr
For example,
| Command | queue-front | queue-rear | Returns |
|---|---|---|---|
| After some steps | (q r s) | (v u) | |
| enqueue 'w | (q r s) | (w v u) | |
| enqueue 'x | (q r s) | (x w v u) | |
| dequeue | (r s) | (x w v u) | q |
| dequeue | (s) | (x w v u) | r |
| dequeue | () | (x w v u) | s |
What if queue-front is empty and all the items in the
queue are in queue-rear? Notice that the item that we
want to dequeue is the first one enqueued, which is the last item in
queue-rear. So we want to set queue-front equal
to the reverse of queue-rear and then set
queue-rear to null. Then
we can return the car of queue-front and
set queue-front equal to the cdr
of queue-front.
Continuing our example above:
| Command | queue-front | queue-rear | Returns |
|---|---|---|---|
| After some steps | () | (x w v u) | |
| dequeue | (v w x) | () | u |
| enqueue y | (v w x) | (y) |
While this makes some calls of dequeue rather slow, in general it is fast since each item is only transfered from queue-rear to queue-front once.
In our implementation an extra field keeps track of the number of elements in the queue, the length of queue-front plus the length of queue-rear.
Here is the constructor for queue objects:
;;; Procedure:
;;; make-queue
;;; Parameters:
;;; (none)
;;; Produces:
;;; queue, a procedure
;;; Preconditions:
;;; (none)
;;; Postconditions:
;;; (1) queue initially represents the empty queue.
;;; (2) Whenever queue is invoked with the argument :empty?, it reports
;;; whether it is empty.
;;; (3) When queue has been invoked with the first argument :enqueue! and
;;; a second argument, say new-value, new-value is at the rear, and
;;; all other values in the queue are in front of it, in order by
;;; time of enqueuing.
;;; (4) When queue has been invoked with the argument :dequeue!, it
;;; returns the longest-enqueued value, the one at the front, and
;;; retains all other values, in order by time of enqueuing.
;;; (5) When queue is invoked with the argument :front, it returns the
;;; value at the front (available for dequeuing).
;;; (6) When queue is invoked with the argument :size, it returns the
;;; number of values in the queue.
;;; (7) It is an error to give queue any other argument when invoking it.
;;; (8) When queue is invoked with the first argument :empty?, :dequeue!,
;;; :front, or :size, it is an error to give it two or more arguments.
;;; (9) When queue is invoked with the first argument :enqueue!, it is an
;;; error to give it only one argument or three or more.
(define make-queue
(let ((set-field! (lambda (field val) (vector-set! field 0 val)))
(get-field (lambda (field) (vector-ref field 0))))
(lambda ()
(let ((front (vector null))
(rear (vector null))
(size (vector 0)))
(lambda (message . arguments)
(cond
((eq? message ':type)
'queue)
((eq? message ':->string)
"#<queue>()")
((eq? message ':empty?)
(if (null? arguments)
(zero? (vector-ref size 0))
(error 'queue:empty? "no arguments are permitted")))
((eq? message ':enqueue!)
(cond
((null? arguments)
(error "queue:enqueue!: an argument is required"))
((not (null? (cdr arguments)))
(error "queue:enqueue!: only one argument permitted"))
(else
; Place the new value on the rear of the queue.
(set-field! rear (cons (car arguments) (get-field rear)))
; Increment the size.
(set-field! size (+ 1 (get-field size))))))
((eq? message ':dequeue!)
(cond ((not (null? arguments))
(error "queue:dequeue!: no argument is permitted"))
((zero? (vector-ref size 0))
(error "queue:dequeue!: the queue is empty"))
(else
; Move stuff from rear to front if necessary.
(if (null? (get-field front))
(begin
(set-field! front (reverse (get-field rear)))
(set-field! rear null)))
; Recover the first element of the queue.
(let ((removed (car (get-field front))))
; Remove the element to be dequeued.
(set-field! front (cdr (get-field front)))
; Decrement size.
(set-field! size (- (get-field size) 1))
; Return that which we removed
removed))))
((eq? message ':front)
(cond ((not (null? arguments))
(error "queue:front: no argument is permitted"))
((zero? (get-field size))
(error "queue:front: the queue is empty"))
(else
; Copy stuff from rear to front if necessary.
(if (null? (get-field front))
(begin
(set-field! front (reverse (get-field rear)))
(set-field! rear null)))
; Return the appropriate element
(car (get-field front)))))
((eq? message ':size)
(if (null? arguments)
(get-field size)
(error "queue:size: no argument is permitted")))
(else (error 'queue "unrecognized message"))))))))
Janet Davis (davisjan@cs.grinnell.edu)
Created November 26, 2006 based on http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2006F/Readings/queues.html