GATE 2016 CS (CS1) – 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
endThe maximum possible number of iterations of the while loop in the algorithm is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 256
Explanation
Each iteration of the loop either **moves** the head of the queue onto the stack (if the stack is empty or its top is $\le$ the head) or **returns** the top of the stack to the back of the queue. The loop ends when the queue is empty, i.e. when everything has been pushed onto the stack.
The worst case is when the numbers sit in the queue in **decreasing** order (head is the largest). Then each number is pushed and popped repeatedly: the stack can only take elements in non-decreasing order, so for every one of the 16 numbers the queue has to be cycled through about 16 times before it can be pushed for good.
A brute-force check over all arrangements for small sizes $n$ gives a maximum of exactly $n^2$ iterations (4, 9, 16, 25, 36, 49 for $n=2,\dots,7$), always attained by the decreasing order. For $n=16$:
$$16^2=\mathbf{256}.$$