## Stack And Queues

 Question 1
 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
Data Structures        Stack And Queues       Gate-2006
Question 1 Explanation:
Let's first consider for push, i.e., x.
Best case:
First push m elements in S1 then pop m elements from S1 and push them in S2 and then pop all m elements from S2. Now push remaining (n-m) elements to S1.
So total push operation
= m + m + (n-m)
= n+m
Worst Case:
First push all n elements in S1. Then pop n elements from S1 and push them into S2. Now pop m elements from S2.
So total push operation
= n+n
= 2n
Now lets consider for pop operation, i.e., y.
For best case:
First push m elements in S1, then pop m elements and push them in S2. Now pop that m elements from S2. Now push remaining (n-m) elements in S1.
So total pop operation
= m+m
= 2m
For worst case:
First push n elements in S1, then pop them from S1 and push them into S2. Now pop m elements fro m S2.
So total pop operation
= n+m
Therefore, option A is correct answer.
There is 1 question to complete.