Permalink copied!
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.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.
|
Operation
|
Resulting Queue
|
| const q = make_queue(); | |
| insert_queue(q, "a"); | a |
| insert_queue(q, "b"); | a b |
| delete_queue(q); | b |
| insert_queue(q, "c"); | b c |
| insert_queue(q, "d"); | b c d |
| delete_queue(q); | c d |
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()
returns an empty queue (a queue containing no items). -
a predicate:
is_empty_queue($queue$)
tests if the queue is empty. -
a selector:
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$)
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 sequence of items, we could certainly represent
it as an ordinary list; the front of the queue would be the
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
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
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
and
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
pair
to combine the two pointers. Thus, the queue itself will be the
pair
of the two pointers.
Figure 3.38
illustrates this representation.
Figure 3.38
Implementation of a queue as a list with front and rear pointers.
To define the queue operations we use the following
functions,
which enable us to select and to modify the front and rear pointers of a
queue:
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:
function is_empty_queue(queue) { return is_null(front_ptr(queue)); }
The
make_queue
constructor returns, as an initially empty queue, a pair whose
head
and
tail
are both the empty list:
function make_queue() { return pair(null, null); }
To select the item at the front of the queue, we return the
head
of the pair indicated by the front pointer:
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.
We first create a new
pair whose
head
is the item to be inserted and whose
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.
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
tail
pointer of the first item (see
figure 3.42):
[1]
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;
}
}
Ben Bitdiddle decides to test the queue implementation described
above. He types in the
functions
to the
JavaScript
interpreter and proceeds to try them out:
const q1 = make_queue();
insert_queue(q1, "a");
[["a", null], ["a", null]]
insert_queue(q1, "b");
[["a", ["b", null]], ["b", null]]
delete_queue(q1);
[["b", null], ["b", null]]
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 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 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 function print_queue that takes a queue as input and prints the sequence of items in the queue.
function print_queue(q) {
return display(head(q));
}
Instead of representing a queue as a pair of pointers, we can build a
queue as a
function
with local state. The local state will consist of pointers to the
beginning and the end of an ordinary list. Thus, the
make_queue
function
will have the form
function make_queue() {
let front_ptr = $\ldots$;
let rear_ptr = $\ldots$;
$\langle{}$declarations of internal functions$\rangle$
function dispatch(m) {$\ldots$}
return dispatch;
}
Complete the definition of
make_queue
and provide implementations of the queue operations using this
representation.
// provided by GitHub user devinryu
function make_queue() {
let front_ptr = null;
let rear_ptr = null;
function is_empty_queue() {
return is_null(front_ptr);
}
function insert_queue(item) {
let new_pair = pair(item, null);
if (is_empty_queue()) {
front_ptr = new_pair;
rear_ptr = new_pair;
} else {
set_tail(rear_ptr, new_pair);
rear_ptr = new_pair;
}
}
function delete_queue() {
if (is_empty_queue()) {
error("FRONT called with an empty queue");
} else {
front_ptr = tail(front_ptr);
}
}
function print_queue() {
display(front_ptr);
}
function dispatch(m) {
return m === "insert_queue"
? insert_queue
: m === "delete_queue"
? delete_queue
: m === "is_empty_queue"
? is_empty_queue
: m === "print_queue"
? print_queue
: error(m, "Unknow operation -- DISPATCH");
}
return dispatch;
}
function insert_queue(queue, item) {
return queue("insert_queue")(item);
}
function delete_queue(queue) {
return queue("delete_queue")();
}
function print_queue(queue) {
return queue("print_queue")();
}
A deque
(
[2]
double-ended queue) is a sequence in which items can be inserted and deleted either at the front or at the rear. Operations on deques are the constructor make_deque, the predicate is_empty_deque, selectors front_deque and rear_deque, and mutators front_insert_deque, front_delete_deque, rear_insert_deque, and rear_delete_deque. Show how to represent deques using pairs, and give implementations of the operations.
All operations should be accomplished in
$\Theta(1)$ steps.
// solution provided by GitHub user clean99
function make_deque() {
return pair(null, null);
}
function front_ptr(deque) {
return head(deque);
}
function rear_ptr(deque) {
return tail(deque);
}
function set_front_ptr(deque, item) {
set_head(deque, item);
}
function set_rear_ptr(deque, item) {
set_tail(deque, item);
}
function is_empty_deque(deque) {
return is_null(front_ptr(deque))
? true
: is_null(rear_ptr(deque))
? true
: false;
}
function is_one_item_deque(deque) {
return front_ptr(deque) === rear_ptr(deque);
}
function front_insert_deque(deque, item) {
// use another pair to store a forward pointer
const new_pair = pair(pair(item, null), null);
if (is_empty_deque(deque)) {
set_front_ptr(deque, new_pair);
set_rear_ptr(deque, new_pair);
} else {
set_tail(new_pair, front_ptr(deque));
// set forward pointer to new_pair
set_tail(head(front_ptr(deque)), new_pair);
set_front_ptr(deque, new_pair);
}
}
function front_delete_deque(deque) {
if (is_empty_deque(deque)) {
error(deque, "front_delete_deque called with an empty deque");
} else if(is_one_item_deque(deque)) {
set_front_ptr(deque, null);
set_rear_ptr(deque, null);
return deque;
} else {
set_front_ptr(deque, tail(front_ptr(deque)));
return deque;
}
}
function rear_insert_deque(deque, item) {
if (is_empty_deque(deque)) {
const new_pair = pair(pair(item, null), null);
set_front_ptr(deque, new_pair);
set_rear_ptr(deque, new_pair);
} else {
// set new_pair forward pointer to last item
const new_pair = pair(pair(item, rear_ptr(deque)), null);
set_tail(rear_ptr(deque), new_pair);
set_rear_ptr(deque, new_pair);
}
}
function rear_delete_deque(deque) {
if (is_empty_deque(deque)) {
error(deque, "rear_delete_deque called with an empty deque");
} else if(is_one_item_deque(deque)) {
set_front_ptr(deque, null);
set_rear_ptr(deque, null);
return deque;
} else {
// update rear_ptr to last item's forward pointer
set_rear_ptr(deque, tail(head(rear_ptr(deque))));
return deque;
}
}
[1]
If the first item is
the final item in the queue, the front pointer will be the empty list after
the deletion, which will mark the queue as empty; we needn't worry
about updating the rear pointer, which will still point to the deleted
item, because
is_empty_queue
looks only at the front pointer.
3.3.2
Representing Queues