GATE CSE
First time here? Checkout the FAQ!
x
+10 votes
1.4k 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.4k views

4 Answers

+6 votes
Best answer

Page 1

Page 2

[Please excuse for the poor handwriting ]

answered by Veteran (20.3k 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.5k 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 (53.8k points)  
edited by
Answer:

Related questions



Top Users May 2017
  1. akash.dinkar12

    3568 Points

  2. pawan kumarln

    2206 Points

  3. Bikram

    1940 Points

  4. sh!va

    1682 Points

  5. Arjun

    1650 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1270 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1028 Points

  10. Arnab Bhadra

    904 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1026 Points

  2. pawan kumarln

    832 Points

  3. Arnab Bhadra

    818 Points

  4. akash.dinkar12

    448 Points

  5. Arjun

    378 Points


22,897 questions
29,213 answers
65,336 comments
27,713 users