GATE CSE 2006 | Question: 49

Question

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(\leq 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\leq x<2n $ and $2m\leq y\leq n+m $
• B. $ n+m\leq x<2n $ and $2m\leq y\leq 2n $
• C. $ 2m\leq x<2n $ and $2m\leq y\leq n+m $
• D. $ 2m\leq x<2n $ and $2m\leq y\leq 2n $

Comments

@Ayush Upadhyaya agree!!!

---

@ Niraj Singh 2  

 

before inserting anything to stack S1, program should check whether the stack s2 is empty or not , if S2 is  not empty then it should first copy all contents of S2  to S1,  otherwise  queue can not be implemented .

No this is fine . try it on paper , you will understand that . Its actually optimized way of implementing queue using 2 stacks.

 

---

I guess there is some fault, isnt in the deq part the else while condition should 1^st check whether stack 2 is empty or not. if not empty then directly return top[s2]

Answer 1

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);
}

See PUSH  and POP operation in code.

Given : n=insert

m=delete

x=push

y=pop

Trywith some example.

Now, in given code 

Say S_2 already contains 1,2,3 // No PUSH operation here, no need to consider it

$S_{1}$ has to push 4,5 // So, 2 PUSH operation here.

Now, POP S_2 //3 POP operation Not considering here

Now, POP $S_1$// 2 POP operation

PUSH them in $S_2$//2 PUSH operation

Again POP $S_2$// 2 POP operation

-------------------------------------------------------------------------------------------------------------------------------

In PUSH 4,5 push to insert $S_1$ (Say, n push)

Now, we only POP 5 from stack (Say m) and PUSH in $S_2$.

So, Total PUSH n+m.

and maximum we can push 2n (when we POP 4,5 both from stack (Say n) and PUSH in $S_2$. )

So, for PUSH operation $n+m< x\leq 2n$

--------------------------------------------------------------------------------------------------------------------------------------------------------------

In POP operation say  5  POP from $S_1$.(say m)

Now,  5 PUSH in $S_2$.(Say m)

Now, we have to POP only 5 from $S_2$.

Otherwise in worst case

In POP operation say  4,5  POP from $S_1$.(say n)

Now, only 5 PUSH in $S_2$.(Say m)

Now, we have to POP only 5 from $S_2$.

n+m POP operation

So, total POP operation $2m< x\leq m+n$

Comments

@srestha

can you edit your answer, in the pop operation, are $'y'$ instead of $'x'$(last line)

Answer 2

Check for 1 insert and 1 delete

For 1 insert we need 1 push

For 1 delete we need 1 push and 2 pop

So total 2 push and 2 pop

Finally n=1,m=1,x=y=2 substitute the values in choices b,c,d goes wrong

Comments

How?? How does it make b,c and d as wrong.

If it is because of  X $<$ 2n part then even option A is incorrect.

Answer 3

Hence, option (A) seems to be the best answer.

Answer 4

For this question, if we consider the option, we can easily find the correct option.

the options are nothing but the relation between, the no. of push operation(x) and no. of pop operation (y).

so at last we have to find, 

min  no. of push operation < x < max  no. of the push operation

 

min. no  of pop operation < y < max  no.  of pop operation

The value for min and max could be easily determined by considering the cases as follows : 

1. For min. no of push operations:  we have to restrict the no. of the push operation inside the loop statement, so for that, insertion and deletion are performed alternatively. In this way we have

            (m + n ) push operation –  { n  for insertion  and m for at each alternative deletion  }

           min push operation = m + n

          also, total pop operations =  m + m ( m – for pop inside the loop, m – for last pop operation on S2  ) = 2m

2. For max no. of push operations:  The case when loop run over the fully filled stack 2. 

              here,  n – push operations during insert in one go. , n more push operations at first delete operation

             total push operation = n + n =  2n ( maximum push operations ) 

             also, total pop operation =  ( n+ 1 ) +  ( m – 1 ) = n + m

          (n + 1 → first deletion,  n’s pop at loop + 1’s last pop,   m – 1 → no. of   pop will happen on the S2)

                

So, by considering these cases, we can easily identify what are the min pop and max pop operations too.