An implementation of a queue Q, using two stacks S1 and S2, is given below:…
2006
An implementation of a queue Q, using two stacks S1 and S2, is given below:
void insert(Q, x) {
push (S1, x);
}
void delete(Q){
if(stack-empty(S2)) then
if(stack-empty(S1)) then {
print(“Q is empty”);
return;
}
else while (!(stack-empty(S1))){
x=pop(S1);
push(S2,x);
}
x=pop(S2);
}
Let n insert and m (<=n) delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?
- A.
n+m <= x < 2n and 2m <= y <= n+m
- B.
n+m <= x < 2n and 2m<= y <= 2n
- C.
2m <= x < 2n and 2m <= y <= n+m
- D.
2m <= x <2n and 2m <= y <= 2n
Attempted by 76 students.
Show answer & explanation
Correct answer: A
Key idea: each insert pushes once onto S1. When a delete finds S2 empty, all elements currently in S1 are moved to S2; each moved element causes one pop from S1 and one push onto S2. Each element can be moved at most once.
Counting pushes (x):
Every insert contributes one push onto S1, giving n pushes.
Each element moved from S1 to S2 contributes one additional push (onto S2). The number of moved elements equals the number of pops from S1 during transfers, which is at least m and at most n.
Therefore x = n + (number of moved elements), so n + m <= x <= n + n = 2n.
Counting pops (y):
Pops occur when transferring elements from S1 (at most n, at least m) and when deleting elements from S2 (one pop per successful delete, total m).
Thus y = (pops from S1 during transfers) + m, so 2m <= y <= n + m.
Example sequences achieving the bounds:
Lower bound for x and lower bound for y (x = n+m, y = 2m): Alternate insert and delete m times so each transfer moves exactly one element, giving minimal transfers.
Upper bound for x and upper bound for y (x = 2n, y = n+m): Perform all n inserts first, then perform the m deletes; this moves all n elements once onto S2.
Conclusion: The tight ranges for the numbers of push and pop operations are n + m <= x <= 2n and 2m <= y <= n + m. (Note: some answer choices that write a strict upper bound <2n should be corrected to <=2n because x can equal 2n.)
A video solution is available for this question — log in and enroll to watch it.