## Stack And Queues

Question 1 |

n+m ≤ x < 2n and 2m ≤ y ≤ n+m
| |

n+m ≤ x< 2n and 2m ≤y ≤ 2n | |

2m ≤ x< 2n and 2m ≤ y ≤ n+m
| |

2m ≤ x < 2n and 2m ≤ y ≤ 2n |

Question 1 Explanation:

Let's first consider for push, i.e., x.

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

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.

__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.