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

Answer is (A).

The order in which insert and delete operations are performed matters here.

The best case: Insert and delete operations are performed alternatively. In every delete operation, $2$ pop and $1$ push operations are performed. So, total $m+ n$ push $(n$ push for insert() and $m$ push for delete()$)$ operations and $2m$ pop operations are performed.

The worst case: First $n$ elements are inserted and then m elements are deleted. In first delete operation, $n + 1$ pop operations and $n$ push operation are performed. Other than first, in all delete operations, $1$ pop operation is performed. So, total $m + n$ pop operations and $2n$ push operations are performed $(n$ push for insert() and $m$ push for delete()$)$

Comments

Consider this sequence: delete(Q) ; insert(Q, a)

Here $n = 1$ and $m = 1$. No push and pop operations for delete because queue is empty. Only 1 push operation for insert. So $x=1$ and $y=0$. But in all 4 options, the LHS of inequality for $x$ is larger than $x$

Option 1: $n + m  \leq x < 2n$

Substituting values, we get $2 \leq 1 < 2$. Same story for all other options

I think all options are false. Please correct me if I am wrong.

---

One small observation: the best case can be

1. doing PUSH() and POP() alternatively
2. inserting m elements first in stack S1. Transferring m elements to stack S2 and popping all m elements from S2. Then inserting n-m elements to S1. Bcz, we need to delete only m elements. Hence, we are reducing the operatons of transferring that extra n-m elements to S2.

---

yes @baral_abhishek, the best case involves “transfer of only m elements from stack s1 to s2” so that there is no extra push and pop
and the worst case involves, transfer of all (n-m) ele from s1 to s2 , besides the req m elements.
remember 1 ele transfer from s1->s2 involves 1 pop and 1 push ops

So,                                                                                      $push$                                                        $pop$

$best case$ (only m ele transferred                          $m+m+(n-m)=n+m$                                       $m+m=2m$
from s1->s2)                

 
$worst case$(transfer of all (n-m) ele                         $n+m+$($n$-$m$) = $2$$n$                                            $2m+$($n$-$m$) = $n+m$
from s1 to s2 , besides the req m elements.)

Answer 2

Page 1

Page 2

[Please excuse for the poor handwriting ]

Comments

@rahul But y can never be equal to 2n. So y≤2n is not correct.

---

In page 2

what do you mean by for m elements to come out = 2pushes

remaining elements = n-m

---

Please explain page no 3.

Answer 3

the order in which we insert and delete is what matters here.We will have to find the best and the worst cases possible:--

1.WORST CASE-- The worst case happens when we first insert n elements into say STACK 1. Now this n insertions needs n PUSH operations on STACK 1.Now to delete m elements from this n elements we will have to first POP out this n elements from STACK 1.This takes n POP operations.NOW, again we have to PUSH these n elements in STACK 2 in reverse order(as QUEUE follows FIFO property).thus because of this we get n more PUSH operations in STACK 2.Now,finally we POP m elements from STACK 2 to delete m elements.Thus, total PUSH operations becomes 2n and total POP operations becomes n+m.

2.BEST CASE--The best case occurs when we first insert those elements which are to be deleted in STACK 1.Thus, this takes m PUSH operations.Now to delete these m elements we have to first POP these from STACK 1, which takes m POP operations. Now PUSH these m elements in STACK 2 in reverse order as before.This takes m PUSH operations more.Now again POP these m elements to delete it.But now in the question it says that the number of insertions should be n. But we have only inserted m of it.SO, now insert more n-m elements in STACK 1. Thus the total PUSH operations becomes m+m+n-m=n+m and the total POP operations becomes 2m.

Thus, option A is the answer..

Comments

I understood the first part but not the second one , so can u clarify it again please why did u consider initially m push operations and m pop operations when we have n insertions to take place.

---

so that the best case occurs..you may check that if the order of insertion and deletion is in this sequence then the best case occurs...

---

because in this case the no of push operations reduced .

Answer 4

Elements to be pushed = $n$
Elements to be popped = $m$

$m < n$
 x = number of PUSH operations
 y = number of POP operations

case 1: range of y 
lower bound:
1. push m elements to stack S1
2. Pop m elements from stack s1.
3. push m elements on stack s2.
4. pop all m elements from stack s2.

Total pop operations happened here are $m+m = 2m$, hence $2m\leq y$

Upper Bound:
1. Push all n elements onto stack s1.
2. pop all n elements from stack s1.
3. push all elements on stack s2.
4. pop m elements from stack s2.

Total pop operations happened here are n+m, hence $y\leq m+n$

So far so good to eliminate the options (B) and (D).

Range of x:

lower bound:
1. push m elements to stack S1
2. Pop m elements from stack s1.
3. push m elements on stack s2.
4. pop all m elements from stack s2.
5. push remaining n-m elements on stack s2.

total push operations = $m + m + n - m = n+m$, hence $m+n \leq x$

So far so good to eliminate the option (C).

Upper Bound:
1. Push all n elements onto stack s1.
2. pop all n elements from stack s1.
3. push all n elements on stack s2.
4. pop m elements from stack s2.

Total PUSH operations = n+n, hence $x \leq 2n$ 

Hence, (A) is the correct choice.

PS: Don't know why is equal operator not given in any option.
 

Comments

Why is worst case of pop: y<=2n as m<=n

---

So far so good to eliminate the options (B) and (D).

How can u eliminate options B and D?

If ($y$ $\leq$ $m+n$)

         then $y$ will also be less than $2n$ because $m$ $\leq$ $n$ always.

So you cannot eliminate B and D option with that approach.