edited by
34,477 views
143 votes
143 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 _______.

edited by

12 Answers

0 votes
0 votes
Whenever values are big always take examples,

 

Try with n=2 , n=3 n=4

You will get ans as 4,9,16

 

So only possible relation is n^2, cant relate both in any other way.

So ans is (16)^2
0 votes
0 votes

If the input is in descending order then the loop will execute n^2 times.

For n = 16 , loop will execute 256 times

Here’s small code depicting this,

Q = [16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]    // considering index 0 as head of Q
S =[]
i=0
while(Q.length){
 
   if ( !S.length || S[S.length-1]<=Q[0] ) {  
        x = Q.splice(0,1);
        S.push(x[0]);
   }

  else{

      x = S.splice(S.length-1,1);

      Q.push(x[0]);
  }
  i++;  
  console.log(i +"|" + Q+ "|"+S) //will give iteration no. And elements in Q & S
}

 

 

P.S. The code is written in JS, If u wanna run it just copy the code , Right click on the web browser(CHROME) any page select Inspect And in the console tab just paste the code And hit enter 

0 votes
0 votes

A “rough” Python implementation closer to pseudo-code.

 

I made this program because i thought the program would run to infinite. I pushed the top of stack to the top of the queue which gave an infinite while loop. Coding it in python helped me realize the mistake.

–2 votes
–2 votes

Maximum no of iterations of the while loop is n2 (in worst case , when (n-1) are in ascending order and nth element is in min of all the element)

I try for n=3 (2 3 1) got 9 iteration of while loop

for base case , it will be n iteration ( no are in ascending order)

and for descending order it will infinite time

edited by
Answer:

Related questions