GATE CS 2016 Set 1 Q41 — Arrays, Stacks and Queues

The given algorithm sorts the elements of the queue $Q$ into the stack $S$ in ascending order (with the largest element at the top of $S$). To find the maximum possible number of iterations of the while loop, we consider the worst-case input, which occurs when the queue $Q$ is initially sorted in descending order: $Q = [n, n-1, ext{…}, 1]$.

Let $k$ be the number of elements currently sorted in the stack $S$. When we want to insert the next element from $Q$ (which is smaller than all elements currently in $S$):

1. We must pop all $k$ elements from $S$ and enqueue them back to $Q$ to reach the bottom of the stack. This takes $k$ iterations (each performing a Pop and Enqueue).
2. We then dequeue the new smallest element from $Q$ and push it onto the empty stack $S$. This takes $1$ iteration.
3. Finally, we must move the $k$ elements back from $Q$ to $S$. Since they are already sorted and larger than the top of $S$, they are pushed directly. This takes $k$ iterations (each performing a Dequeue and Push).

Thus, the number of iterations required to insert the $(k+1)$-th element is: $$T(k+1) = k + 1 + k = 2k + 1$$

Summing this cost for all $n$ elements (from $k = 0$ to $n-1$): $$\text{Total Iterations} = \sum_{k=0}^{n-1} (2k + 1) = n^2$$

For $n = 16$ elements, the maximum possible number of iterations is: $$16^2 = 256$$