Stacks and queues
Stacks and queues
Stacks and queues are dynamic sets in which the element removed from the set
by the DELETE operation is prespecified. In a stack, the element deleted from
the set is the one most recently inserted: the stack implements a last-in, first-out,
or LIFO, policy. Similarly, in a queue, the element deleted is always the one that
has been in the set for the longest time: the queue implements a first-in, first-out,
or FIFO, policy. There are several efficient ways to implement stacks and queues
on a computer. In this section, we show how to use a simple array to implement
each.
Stacks
The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP. These names
are allusions to physical stacks, such as the spring-loaded stacks of plates used
in cafeterias. The order in which plates are popped from the stack is the reverse
of the order in which they were pushed onto the stack, since only the top plate is
accessible.
 |
| fig. 10.1 |
As Figure 10.1 shows, we can implement a stack of at most n elements with
an array S(1..n). The array has an attribute S.top that indexes the most recently inserted element. The stack consists of elements S(1 .. S.top), where S(1) is the
element at the bottom of the stack and S(S.top) is the element at the top.
When S.top = 0, the stack contains no elements and is empty. We can test to
see whether the stack is empty by query operation STACK-EMPTY. If we attempt
to pop an empty stack, we say the stack underflows, which is normally an error.
If S.top exceeds n, the stack overflows. (In our pseudocode implementation, we
don’t worry about stack overflow.)
We can implement each of the stack operations with just a few lines of code:
Figure 10.1 shows the effects of the modifying operations PUSH and POP. Each of the three stack operations takes O(1) time.
Queues
We call the INSERT operation on a queue ENQUEUE, and we call the DELETE
operation DEQUEUE; like the stack operation POP, DEQUEUE takes no element argument. The FIFO property of a queue causes it to operate like a line of customers
waiting to pay a cashier. The queue has a head and a tail. When an element is enqueued, it takes its place at the tail of the queue, just as a newly arriving customer
takes a place at the end of the line. The element dequeued is always the one at
the head of the queue, like the customer at the head of the line who has waited the
longest.
 |
| fig 10.2 |
Figure 10.2 shows one way to implement a queue of at most n - 1 elements using an array Q(1 .. n). The queue has an attribute Q.head that indexes, or points to, its head. The attribute Q.tail indexes the next location at which a newly arriving element will be inserted into the queue. The elements in the queue reside in locations Q.head; Q.head + 1; . . . ; Q.tail - 1, where we “wrap around” in the sense that location 1 immediately follows location n in a circular order. When Q.head = Q.tail, the queue is empty. Initially, we have Q.head = Q.tail = 1. If we attempt to dequeue an element from an empty queue, the queue underflows. When Q.head = Q.tail + 1, the queue is full, and if we attempt to enqueue an element, then the queue overflows. In our procedures ENQUEUE and DEQUEUE, we have omitted the error checking for underflow and overflow. (Exercise 10.1-4 asks you to supply code that checks for these two error conditions.) The pseudocode assumes that n = Q.length.
Comments
Post a Comment