edited by
32,648 views
88 votes
88 votes

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 $
edited by

8 Answers

Best answer
66 votes
66 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()$)$

edited by
76 votes
76 votes

Page 1

Page 2

[Please excuse for the poor handwriting ]

edited by
42 votes
42 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..
21 votes
21 votes

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.
 

Answer:

Related questions

22 votes
22 votes
7 answers
3
Kathleen asked Sep 14, 2014
24,126 views
What is the minimum number of stacks of size $n$ required to implement a queue of size $n$?OneTwoThreeFour