# Cormen Edition 3 Exercise 10.1 Question 4 (Page No. 235)

91 views
Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue.

## Related questions

1
127 views
ENQUEUE(Q, x) 1 Q[Q.tail] = x 2 if Q.tail == Q.length 3 Q.tail = 1 4 else Q.tail = Q.tail + 1 DEQUEUE(Q) 1 x = Q[Q.head] 2 if Q.head == Q.length 3 Q.head = 1 4 else Q.head = Q.head + 1 5 return x illustrate the result of each operation in the sequence ENQUEUE(Q,4),ENQUEUE(Q,1),ENQUEUE(Q,3),DEQUEUE(Q),ENQUEUE(Q,8),DEQUEUE(Q) on an initially empty queue $Q$ stored in array $Q[1...6]$.
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.
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 $PUSH$ and $POP$ operations should run in $O(1)$ time.