GATE CSE
First time here? Checkout the FAQ!
x
+10 votes
1.2k views

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$?

  1. $ n+m\leq x<2n $ and $2m\leq y\leq n+m $
  2. $ n+m\leq x<2n $ and $2m\leq y\leq 2n $
  3. $ 2m\leq x<2n $ and $2m\leq y\leq n+m $
  4. $ 2m\leq x<2n $ and $2m\leq y\leq 2n $
asked in DS by Loyal (4k points)   | 1.2k views

4 Answers

+6 votes
Best answer

Page 1

Page 2

[Please excuse for the poor handwriting ]

answered by Veteran (20.2k points)  
edited by
this is so perfect (Y)
can't be better than this
Nice one
+20 votes

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())

answered by Loyal (3.2k points)  
I think x <= 2n instead of x < 2n. Am I correct?
+6 votes
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..
answered by Loyal (3.4k points)  
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...
+1 vote
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$

answered by Veteran (51.8k points)  
edited by
Answer:

Related questions

Top Users Feb 2017
  1. Arjun

    5410 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2240 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,864 questions
26,030 answers
59,704 comments
22,144 users