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 | 2k views

Page 1

Page 2

[Please excuse for the poor handwriting ]

answered by Veteran (21.5k points)
edited by
this is so perfect (Y)
can't be better than this
Nice one
In the second case, why is the overall requirement of pop = 4 ?

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?
Ya, I also think the same!
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.7k 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...
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 (58.6k points)
edited by