The Gateway to Computer Science Excellence

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

- $ n+m\leq x<2n $ and $2m\leq y\leq n+m $
- $ n+m\leq x<2n $ and $2m\leq y\leq 2n $
- $ 2m\leq x<2n $ and $2m\leq y\leq n+m $
- $ 2m\leq x<2n $ and $2m\leq y\leq 2n $

+1

@ rahul sharma 5, **A** is more stronger option than **B**, i.e it is superset of option B. Options **C & D** are false because, It is mentioned that **there are n insert operations** due to which **n < x condition should hold always**.

+1

How did u prove c and d false?I did not get.I found all are true but a being the strongest answer as it gives exact answer but other are upper and lower bounds

0

What will happen if i try to delete and my stack S2 is not empty? Firstly S2 elements should be returned and then if S2 is empty,then S1 should be brought into S2

+10

I don't know whether anyone noticed or not,

but for all options for x,

the inequality for X, must have $\leq$ sign on the right part of inequality

that means x must be x$\leq$ 2n instead of x$<$2n

Since question says, for any arbitrary order of insert and delete operations,

consider below case

n=4(the total insertions)

m=3(the total deletions)

Take queue operations as

2 insert, 1 delete, 1 insert , 1 delete , 1 insert, 1 delete,

then x(total number of push) =8

y(total number of pop) = 7

now 2n=8 and x$\nless$8

Question clearly says

Let ninsertand m(≤n)m(≤n)deleteoperations be performed in an arbitrary order on an empty queue Q. Let x and y be the number ofpushandpopoperations performed respectively in the process. Which one of the following is true for all m and n?

I think options must be changed considering the inequality.

Let me know if anyone agrees.

+51 votes

Best answer

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

+58 votes

+27 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..

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..

+10 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.

+6 votes

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$

52,315 questions

60,436 answers

201,769 comments

95,247 users