Dark Mode

23,997 views

117 votes

Let $Q$ denote a queue containing sixteen numbers and $S$ be an empty stack. $Head(Q)$ returns the element at the head of the queue $Q$ without removing it from $Q$. Similarly $Top(S)$ returns the element at the top of $S$ without removing it from $S$. Consider the algorithm given below.

while Q is not Empty do if S is Empty OR Top(S) ≤ Head (Q) then x:= Dequeue (Q); Push (S, x); else x:= Pop(S); Enqueue (Q, x); end end

The maximum possible number of iterations of the **while** loop in the algorithm is _______.

@Swati Rauniyar I think in order to find the worst or best cases for any algorithm we should think of inputs in terms of extreme. **The** **most** **extreme** **inputs** **may** **lead** **us** **to** **most** **extreme** **outputs.**

So we should check of 2 cases. One is all the elements in increasing order and the second is in decreasing order.

0

196 votes

Best answer

While loop will run for the maximum number of times when the Queue elements are sorted in descending order.

Let's suppose that initially, Queue elements are $16, 15, 14, 13,\ldots,2, 1$

Now, $16$ will be first pushed into the stack, So, now stack top is $16$ and $Head(Q)$ is $15$, So $16$ will be popped out of the stack ( since, "if S is Empty OR $Top(S)\leq Head (Q)$ "returns false, hence else part will be executed) and enqueued into the Queue.

So, after two iterations Queue elements will be $\rightarrow15, 14, 13, \ldots,2, 1, 16$ and stack will be empty.

Similarly, each of the elements $15,14,13,\ldots,2$ will be pushed into the stack and immediately popped out of the stack(when popped out of the stack then also enqueue into the queue).So after $30$ iterations stack will be empty and Queue contains will be like $\Rightarrow 1, 16, 15, 14, \ldots,2$.

Now $1$ will be Dequeued and pushed into the stack. Once $1$ is pushed into the stack, it will never be popped(or we can say never be enqueued into the Queue again) because in order to Pop $1$, there should be an element into the Queue which is less than $1$ and that element comes at the front of the queue, since there is no element currently present in the Queue which is less than $1$, there is no way to pop $1$.

So, after $31$ iterations Queue is $\Rightarrow 16, 15, 14, \ldots,2$ and stack contains $1$.

Now, the problem boils down to Queue with $15$ elements.

Using the similar logic we can say after another $29$ iterations (Total $=31+29$ )Queue will be like $\Rightarrow 16, 15, 14, \ldots,3$ and stack contains $1,2$ (stack top is $2$) and then $2$ will remain there in the stack forever.

Similar way if we go on then, after $31 + 29 + 27 + 25 + \ldots+1$ iterations Queue will be empty.

This is in A.P. series with $d=2$. Sum $= (16 *(1+31))/2= 16*32/2= 256$

Let's suppose that initially, Queue elements are $16, 15, 14, 13,\ldots,2, 1$

Now, $16$ will be first pushed into the stack, So, now stack top is $16$ and $Head(Q)$ is $15$, So $16$ will be popped out of the stack ( since, "if S is Empty OR $Top(S)\leq Head (Q)$ "returns false, hence else part will be executed) and enqueued into the Queue.

So, after two iterations Queue elements will be $\rightarrow15, 14, 13, \ldots,2, 1, 16$ and stack will be empty.

Similarly, each of the elements $15,14,13,\ldots,2$ will be pushed into the stack and immediately popped out of the stack(when popped out of the stack then also enqueue into the queue).So after $30$ iterations stack will be empty and Queue contains will be like $\Rightarrow 1, 16, 15, 14, \ldots,2$.

Now $1$ will be Dequeued and pushed into the stack. Once $1$ is pushed into the stack, it will never be popped(or we can say never be enqueued into the Queue again) because in order to Pop $1$, there should be an element into the Queue which is less than $1$ and that element comes at the front of the queue, since there is no element currently present in the Queue which is less than $1$, there is no way to pop $1$.

So, after $31$ iterations Queue is $\Rightarrow 16, 15, 14, \ldots,2$ and stack contains $1$.

Now, the problem boils down to Queue with $15$ elements.

Using the similar logic we can say after another $29$ iterations (Total $=31+29$ )Queue will be like $\Rightarrow 16, 15, 14, \ldots,3$ and stack contains $1,2$ (stack top is $2$) and then $2$ will remain there in the stack forever.

Similar way if we go on then, after $31 + 29 + 27 + 25 + \ldots+1$ iterations Queue will be empty.

This is in A.P. series with $d=2$. Sum $= (16 *(1+31))/2= 16*32/2= 256$

@vps123 I’m not sir. Just an aspirant like you :)

Thanks for pointing. There was a missing bracket after I converted the equation in Latex Form. I have edited it for better clarity. Hope it will help.

1

Best way to solve such a problem is just try it with 3 or 4 elements & take extreme sequences like increasing or decreasing order, within a minute you can be able to realize the pattern & after that for 16 elements it is just a cake walk i.e., summation. This way you will be to solve the above question within 2 to 3 minutes.

1

38 votes

256 when 16,15,14,...,1 are present in queue

alternately 15 dequeue & push,15 pop & enqueue followed by 1 dequeue & push i.e. 31 iterations

brings it to the state 16,15,...,2 in queue and 1 in stack

29 iterations to get to 16,15,...,3 in queue and 2,1 in stack and so on

31+29+27+...+1=16^2=256

@ Saurabh rai sir

Initially, the queue containing $3,2,1$as input, and first iteration when $3$ push into the stack and second iteration $3$ compare to with $2$ and remove $3$, how we can insert the $3$ back in the queue?? what is the size of the queue in this case?

please answer me sir

0

11 votes

Queue Q contains 16,15,14,13,.....,1 where front pointing to 16 and rear is pointing to 1, Let denote Top(S) as T(s) and Head(Q) as H(q)

Stack S is empty now.

Now See While loop condition, As T(s) is empty,we do Dequeue 16 and push 16 to S, So one DEQUEUE and one PUSH, now T(s)=16 and H(q)=15

...........................................................................................................................

As T(S)>H(Q) we do POP 16 and then do Enqueue 16, So one POP and one ENQUEUE , now T(s)=empty and H(q)=15

..........................................................................................................................

As T(s) is empty,we do Dequeue 15 and push 15 to S, So one DEQUEUE and one PUSH, now T(s)=15 and H(q)=14

.......................................................................................................................

As T(S)>H(Q) we do POP 15 and then do Enqueue 15, So one POP and one ENQUEUE , now T(s)=empty and H(q)=14

---------------------------------------------------------------------------------------

..........

...........

For each number upto 2, we dequeue and push once, then POP and enqueue once, for last number that is 1 we dequeue and push once but after that T(S)<H(Q) as then H(Q)=16 and T(S)=1

so it takes 15*2+1=31 iterations to place 1 in stack and make Q(16 to 2), then 29 iterations to place 1,2 in stack and make Q(16 to 3)..then 27 iterations to place 1,2,3 in stack and make Q(16 to 4)..so on....

so total iterations=31+29+27+....+1=256

Stack S is empty now.

Now See While loop condition, As T(s) is empty,we do Dequeue 16 and push 16 to S, So one DEQUEUE and one PUSH, now T(s)=16 and H(q)=15

...........................................................................................................................

As T(S)>H(Q) we do POP 16 and then do Enqueue 16, So one POP and one ENQUEUE , now T(s)=empty and H(q)=15

..........................................................................................................................

As T(s) is empty,we do Dequeue 15 and push 15 to S, So one DEQUEUE and one PUSH, now T(s)=15 and H(q)=14

.......................................................................................................................

As T(S)>H(Q) we do POP 15 and then do Enqueue 15, So one POP and one ENQUEUE , now T(s)=empty and H(q)=14

---------------------------------------------------------------------------------------

..........

...........

For each number upto 2, we dequeue and push once, then POP and enqueue once, for last number that is 1 we dequeue and push once but after that T(S)<H(Q) as then H(Q)=16 and T(S)=1

so it takes 15*2+1=31 iterations to place 1 in stack and make Q(16 to 2), then 29 iterations to place 1,2 in stack and make Q(16 to 3)..then 27 iterations to place 1,2,3 in stack and make Q(16 to 4)..so on....

so total iterations=31+29+27+....+1=256

3 votes

there can be 3 cases

case 1:

all elements in queue are arranged in ascending order,suppose 1,2,3......16

then it will take 16 iterations are there

but we are asked to compute max possible iterations so consider next case

case 2:

all elements are same , 16 loops are possible in this case

case 3:

it will take 31+29+27+25.......+1=256

which can be calculated as

15 15

⅀(2n+1)=2 ⅀n+15=2*120+15=256

n=0 n=0

so the answer is 256

case 1:

all elements in queue are arranged in ascending order,suppose 1,2,3......16

then it will take 16 iterations are there

but we are asked to compute max possible iterations so consider next case

case 2:

all elements are same , 16 loops are possible in this case

case 3:

it will take 31+29+27+25.......+1=256

which can be calculated as

15 15

⅀(2n+1)=2 ⅀n+15=2*120+15=256

n=0 n=0

so the answer is 256

**Ans:****256**

Worst case input: 16, 15, 14, .... 1

First 16 will get into stack(since **S is Empty**) then popped out to the end of the queue (since **Top(S)>Head(Q)**). This happens for all the 15 elements (from 16 to 2). i.e, 2 operations per item (one push to stack and one pop from stack since top(S)>Head(Q)).

After this element 1 gets pushed to stack.

Therefore, in total = 2 * 15 + 1 = 31 operations to insert just one element into stack.

Now the problem gets reduced to handling 15 numbers in the queue (16, 15, 14, .... 2).

Total number of operations = 31+29+27+...+1

a_{n} =31, a_{1}=1.

a_{n}=a_{1}+(n-1)*d ==> n=16

Total = n/2 * (a_{1}+a_{n}) = 16/2*(1+31) = 256

1