10.1 Stacks and queues
10.1-1
Using Figure 10.1 as a model, illustrate the result of each operation in the sequence $\text{PUSH}(S, 4)$, $\text{PUSH}(S, 1)$, $\text{PUSH}(S, 3)$, $\text{POP}(S)$, $\text{PUSH}(S, 8)$, and $\text{POP}(S)$ on an initially empty stack $S$ stored in array $S[1..6]$.
$$ \begin{array}{l|ccc} \text{PUSH($S, 4$)} & 4 & & \\ \text{PUSH($S, 1$)} & 4 & 1 & \\ \text{PUSH($S, 3$)} & 4 & 1 & 3 \\ \text{POP($S$)} & 4 & 1 & \\ \text{PUSH($S, 8$)} & 4 & 1 & 8 \\ \text{POP($S$)} & 4 & 1 & \end{array} $$
10.1-2
Explain how to implement two stacks in one array $A[1..n]$ in such a way that neither stack overflows unless the total number of elements in both stacks together is $n$. The $\text{PUSH}$ and $\text{POP}$ operations should run in $O(1)$ time.
The first stack starts at $1$ and grows up towards n, while the second starts form $n$ and grows down towards $1$. Stack overflow happens when an element is pushed when the two stack pointers are adjacent.
10.1-3
Using Figure 10.2 as a model, illustrate the result of each operation in the sequence $\text{ENQUEUE}(Q, 4)$, $\text{ENQUEUE}(Q ,1)$, $\text{ENQUEUE}(Q, 3)$, $\text{DEQUEUE}(Q)$, $\text{ENQUEUE}(Q, 8)$, and $\text{DEQUEUE}(Q)$ on an initially empty queue $Q$ stored in array $Q[1..6]$.
$$ \begin{array}{l|cccc} \text{ENQUEUE($Q, 4$)} & 4 & & & \\ \text{ENQUEUE($Q, 1$)} & 4 & 1 & & \\ \text{ENQUEUE($Q, 3$)} & 4 & 1 & 3 & \\ \text{DEQUEUE($Q$)} & & 1 & 3 & \\ \text{ENQUEUE($Q, 8$)} & & 1 & 3 & 8 \\ \text{DEQUEUE($Q$)} & & & 3 & 8 \end{array} $$
10.1-4
Rewrite $\text{ENQUEUE}$ and $\text{DEQUEUE}$ to detect underflow and overflow of a queue.
To detect underflow and overflow of a queue, we can implement $\text{QUEUE-EMPTY}$ and $\text{QUEUE-FULL}$ first.
QUEUE-FULL(Q)
if Q.head == Q.tail + 1 or (Q.head == 1 and Q.tail == Q.length)
return true
else return false
ENQUEUE(Q, x)
if QUEUE-FULL(Q)
error "overflow"
else
Q[Q.tail] = x
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail + 1
DEQUEUE(Q)
if QUEUE-EMPTY(Q)
error "underflow"
else
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else Q.head = Q.head + 1
return x
10.1-5
Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double-ended queue) allows insertion and deletion at both ends. Write four $O(1)$-time procedures to insert elements into and delete elements from both ends of a deque implemented by an array.
The procedures $\text{QUEUE-EMPTY}$ and $\text{QUEUE-FULL}$ are implemented in Exercise 10.1-4.
HEAD-ENQUEUE(Q, x)
if QUEUE-FULL(Q)
error "overflow"
else
if Q.head == 1
Q.head = Q.length
else Q.head = Q.head - 1
Q[Q.head] = x
TAIL-ENQUEUE(Q, x)
if QUEUE-FULL(Q)
error "overflow"
else
Q[Q.tail] = x
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail + 1
HEAD-DEQUEUE(Q)
if QUEUE-EMPTY(Q)
error "underflow"
else
x = Q[Q.head]
if Q.head == Q.length
Q.head = 1
else Q.head = Q.head + 1
return x
TAIL-DEQUEUE(Q)
if QUEUE-EMPTY(Q)
error "underflow"
else
if Q.tail == 1
Q.tail = Q.length
else Q.tail = Q.tail - 1
x = Q[Q.tail]
return x
10.1-6
Show how to implement a queue using two stacks. Analyze the running time of the queue operations.
- $\text{ENQUEUE}$: $\Theta(1)$.
- $\text{DEQUEUE}$: worst $O(n)$, amortized $\Theta(1)$.
Let the two stacks be $A$ and $B$.
$\text{ENQUEUE}$ pushes elements on $B$. $\text{DEQUEUE}$ pops elements from $A$. If $A$ is empty, the contents of $B$ are transfered to $A$ by popping them out of $B$ and pushing them to $A$. That way they appear in reverse order and are popped in the original.
A $\text{DEQUEUE}$ operation can perform in $\Theta(n)$ time, but that will happen only when $A$ is empty. If many $\text{ENQUEUE}$s and $\text{DEQUEUE}$s are performed, the total time will be linear to the number of elements, not to the largest length of the queue.
10.1-7
Show how to implement a stack using two queues. Analyze the running time of the stack operations.
- $\text{PUSH}$: $\Theta(1)$.
- $\text{POP}$: $\Theta(n)$.
We have two queues and mark one of them as active. $\text{PUSH}$ queues an element on the active queue. $\text{POP}$ should dequeue all but one element of the active queue and queue them on the inactive. The roles of the queues are then reversed, and the final element left in the (now) inactive queue is returned.
The $\text{PUSH}$ operation is $\Theta(1)$, but the $\text{POP}$ operation is $\Theta(n)$ where $n$ is the number of elements in the stack.