## Stack-and-Queue

Question 1 |

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?

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.