Question

An implementation of queue Q, using two stacks S1 and S2, is given below:

void insert(Q, x)
{
push(S1, x);
}
void delete (Q, x)
{
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\le n)$ delete operations be performed in an arbitary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the processes. Which one of the following is true for all m and n?

• A. $n+m\le x\le 2nand2m\le y\le n+m$
• B. $2m\le x<2nand2m\le y\le 2n$
• C. $n+m\le x\le 2nand2m\le y\le 2n$
• D. $2m\le x<2nand2m\le y\le n+m$

Answer 1

The correct option is A $n+m\le x\le 2nand2m\le y\le n+m$

Number of push operations
= n(insert) + m (delete)
= n+ m

So, $n+m\le x$ but there are maximum 2n insert operations

$So,n+m\le x\le 2n...\left(1\right)$

No. of pop operations = n + m

But there are 2m delete operations which are less than no. of pop operations, hence

$2m\le n+m...\left(2\right)$

$From\left(1\right)and\left(2\right):n+m\le x\le 2n\&$
$2m\le n+m$

$Form\left(1\right)and\left(2\right):n+m\le x\le 2n\&$
$2m\le n+m$