TAOCP 2.2.1 Exercise 14

Section 2.2.1: Stacks, Queues, and Deques

Exercise 14. [26] Suppose you are allowed to use only stacks as data structures. How can you implement a queue efficiently with two stacks?

The simplest and most natural way to keep a linear list inside a computer is to put the list items in consecutive locations, one node after the other. Then we will have

$$ \operatorname{LOC}(X[j+1]) = \operatorname{LOC}(X[j]) + c, $$

where $c$ is the number of words per node. (Usually $c = 1$. When $c > 1$, it is sometimes more convenient to split a single list into $c$ "parallel" lists, so that the $k$th word of node $X[j]$ is stored a fixed distance from the location of the first word of $X[j]$, depending on $k$. We will continually assume, however, that adjacent groups of $c$ words form a single node.) In general,

$$ \operatorname{LOC}(X[j]) = L_0 + cj, \tag{1} $$

where $L_0$ is a constant called the base address, the location of an artificially assumed node $X[0]$.

This technique for representing a linear list is so obvious and well-known that there seems to be no need to dwell on it at any length. But we will be seeing many other "more sophisticated" methods of representation later on in this chapter, and it is a good idea to examine the simple case first to see just how far we can go with it. It is important to understand the limitations as well as the power of the use of sequential allocation.

Sequential allocation is quite convenient for dealing with a stack. We simply have a variable T called the stack pointer. When the stack is empty, we let T = 0. To place a new element Y on top of the stack, we set

$$ T \leftarrow T + 1;\qquad X[T] \leftarrow Y. \tag{2} $$

And when the stack is not empty, we can set Y equal to the top node and delete that node by reversing the actions of (2):

$$ Y \leftarrow X[T];\qquad T \leftarrow T - 1. \tag{3} $$

(Inside a computer it is usually most efficient to maintain the value $cT$ instead of $T$, because of (1). Such modifications are easily made, so we will continue our discussion as though $c = 1$.)

The representation of a queue or a more general deque is a little trickier. An obvious solution is to keep two pointers, say F and R (for the front and rear of the queue), with F = R = 0 when the queue is empty. Then inserting an element at the rear of the queue would be

$$ R \leftarrow R + 1;\qquad X[R] \leftarrow Y. \tag{4} $$

Removing the front node (F points just below the front) would be

$$ F \leftarrow F + 1;\qquad Y \leftarrow X[F];\qquad \text{if } F = R,\text{ then set } F \leftarrow R \leftarrow 0. \tag{5} $$

But note what can happen: If R always stays ahead of F (so that there is always at least one node in the queue) the table entries used are X[1], X[2], ..., X[1000], ..., ad infinitum, and this is terribly wasteful of storage space. The simple method of (4) and (5) should therefore be used only in the situation

Verified: no
Solve time: -

---

Setup

A queue permits insertion at the rear and deletion at the front. The problem asks for an implementation using only stacks as data structures. Let the two stacks be denoted by $A$ and $B$.

The objective is to realize the queue operations

$$ Q \Leftarrow x $$

and

$$ x \Leftarrow Q $$

using only stack operations of the forms

$$ A \Leftarrow x,\qquad x \Leftarrow A, $$

together with the analogous operations on $B$.

Solution

Maintain the following invariant:

The elements of the queue are represented by the contents of $A$ and $B$ so that the front element, if any, is at the top of $B$. If $B$ is empty, the queue elements appear in $A$ from bottom to top in the same order as they entered the queue.

To insert an element $x$ at the rear of the queue, perform

$$ A \Leftarrow x. $$

This operation requires one stack insertion.

To remove the front element, proceed as follows.

If $B$ is nonempty, execute

$$ x \Leftarrow B. $$

Since the top of $B$ is the front of the queue, this deletes the correct item.

If $B$ is empty, transfer every element of $A$ to $B$ by repeated stack deletions and insertions:

$$ \text{while $A$ is nonempty:}\qquad y \Leftarrow A;\qquad B \Leftarrow y. $$

After this transfer, execute

$$ x \Leftarrow B. $$

The transfer reverses the order of the elements in $A$. Suppose the queue contents from front to rear are

$$ a_1,a_2,\ldots,a_n. $$

When $B$ is empty, these elements appear in $A$ from bottom to top as

$$ a_1,a_2,\ldots,a_n. $$

Transferring them to $B$ yields

$$ a_n,a_{n-1},\ldots,a_1 $$

from bottom to top in $B$. Hence the top of $B$ becomes $a_1$, the front element of the queue. Each subsequent deletion from $B$ removes

$$ a_1,a_2,\ldots $$

in the correct FIFO order.

The implementation is efficient because an element is transferred from $A$ to $B$ at most once. Each element undergoes exactly one insertion into $A$, at most one deletion from $A$, at most one insertion into $B$, and exactly one deletion from $B$. Thus a sequence of $m$ queue operations requires $O(m)$ stack operations in total, giving $O(1)$ amortized time per queue operation.

Verification

Insertion preserves the invariant because a new element is placed on top of $A$, which corresponds to appending an item at the rear of the queue.

Deletion preserves the invariant in two cases. If $B$ is nonempty, the top of $B$ is removed, and by construction this element is the queue front. If $B$ is empty, all elements of $A$ are transferred to $B$, reversing their order so that the oldest element becomes accessible at the top of $B$. The subsequent deletion therefore removes the correct front element.

When both $A$ and $B$ are empty, the queue is empty, and the operation

$$ x \Leftarrow Q $$

is undefined, in agreement with the definition of a queue.

Notes

A direct implementation that transfers all elements between two stacks at every insertion or deletion would require $\Theta(n)$ stack operations per queue operation. The method above delays reversal until necessary, which yields constant amortized cost.