test series(previous year)

Question

pls explain this;i never get its explanation on GO!

Comments

what are ur doubts in this question???

---

am not able to find the final equation!

see i know how to implement queue using 2 stacks, i am even getting the question but am never able to find the equation!

Answer 1

                                                                                                                                                             

Best Case[When top m element to be deleted]                                                                                          

 Push        n+m[ n Pushes in S1 and m pushes in S2]             Pop    m+m[m from each Stack]

 

Worst Case[When last m element to be deleted]          

Push            n+n[All element have to insert in each stack]    Pop    n+m[All from Stack1 ,m element from Stack2]                               

So,  n+m<=X<=2n and 2m<=Y<=n+m  hence Option (A) is answer.

Comments

@Gate Fever Suppose 5 insertion 2 deletion

eg elements are 1,2,3,4,5

Best case:when desired delete elements are 5,4

Step 1: Stack 1 element 1 2 3 4 5[top]

step 2: stack 2 element 5 4 [top]

so m+n pushes i.e 5+2=7

Worst case: we desired delete elements are 1,2 then

Step 1: Stack 1 element 1 2 3 4 5[top]

step 2:  Stack 2 element 5 4 3 2 1[top]

so 2n pushes.

Hope this eg cleared ur doubt.

---

Best case:when desired delete elements are 5,4

but we cant delete these in queue; thats my point;

i mean deletion in queue takes placs in fifo order; and u are doing lifo;

i dont know ; what i am thinking is correct or not! 

---

@Gate Fever

This is implementation of Queue using Two Stack i.e S1->S2->(Its should act as Queue and it does.) When i am performing Stack operation it is lifo but at end if u observe overall it worked as Queue FIFO after both stack operation.

Initial list 1,2,3,4,5

eg inserted in S1: 1 2 3 4 5 

Pop out from S1 and inserted in S2:   5 4 3 2 1

if u pop up all element from S2 it will be 1 2 3 4 5 i.e nothing but FIFO order of Initial List.