Suppose you implement two stacks in a single array of size n = 20 to simulate…
Suppose you implement two stacks in a single array of size n = 20 to simulate a double-ended queue (deque). Stack1 grows from the left end and Stack2 grows from the right end. Which condition indicates queue overflow?
Answer: B. top1 + 1 = top2 — In two-stack implementation of deque, overflow occurs when top1 and top2 cross each other. So if top1 + 1 = top2, there is no space left. Setup: Use a single…
- A.
top1 = top2
- B.
top1 + 1 = top2
- C.
top1 = n/2 and top2 = n/2
- D.
top1 > top2
Attempted by 501 students.
Show answer & explanation
Correct answer: B
In two-stack implementation of deque, overflow occurs when top1 and top2 cross each other. So if top1 + 1 = top2, there is no space left.
Setup: Use a single array of size n. Initialize the left stack top as top1 = -1 (empty) and the right stack top as top2 = n (empty). Pushing to the left increments top1; pushing to the right decrements top2.
Overflow condition: Before performing a push on either stack, check whether top1 + 1 = top2. If this equality holds, there is no free index between the two stacks and any further push would cause them to overlap. If the check is missed, you may observe top1 > top2, which means the stacks have already crossed and an invalid state has occurred.
Example (n = 20): Array indices run from 0 to 19. Starting from top1 = -1 and top2 = 20, if pushes fill the array so that top1 = 9 and top2 = 10, then top1 + 1 = top2 and the array is full. Any further push would cause overflow.
Conclusion: The correct and standard condition to detect overflow is that top1 + 1 = top2.