GATE 2016 CS – Question 51

Let $Q$ denote a queue containing sixteen numbers and $S$ be an empty stack. $\texttt{Head}(Q)$ returns the element at the head of the queue $Q$ without removing it from $Q$. Similarly $\texttt{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 ________.