An implementation of a queue Q, using two stacks S1 and S2, is given below:
C
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
Answer: (A)
Explanation:
The order in which insert and delete operations are performed matters here. The best case: Insert and delete operations are performed alternatively. In every delete operation, 2 pop and 1 push operations are performed. So, total m+ n push (n push for insert() and m push for delete()) operations and 2m pop operations are performed. The worst case: First n elements are inserted and then m elements are deleted. In first delete operation, n + 1 pop operations and n push operation are performed. Other than first, in all delete operations, 1 pop operation is performed. So, total m + n pop operations and 2n push operations are performed (n push for insert() and n push for delete())
Hence Option (A) is the correct answer.
Quiz of this Question
Please comment below if you find anything wrong in the above post
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
