GATE CS 2016 Set 1 Q.51 (CS Q.41): Stacks and Queues

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

Your answer

Official answer and solution

Official answer: 256
From: Official GATE 2016 answer key

Solution

Model the algorithm as an insertion process that maintains elements sorted on the stack, and identify the worst-case initial order of the queue.

The algorithm processes elements using a queue $Q$ and stack $S$ :

If $S$ is empty or $\text{Top}(S) \le \text{Head}(Q)$ , the front element of $Q$ is dequeued and pushed onto $S$ .
If $\text{Top}(S) > \text{Head}(Q)$ , the top element of $S$ is popped and appended back to the tail of $Q$ .

This mechanism simulates sorting: elements on stack $S$ are kept in non-decreasing order from bottom to top. When a new element from $Q$ is smaller than $\text{Top}(S)$ , all elements on $S$ that are strictly greater than that element must be popped back into $Q$ before the smaller element can be placed on $S$ .

The worst case occurs when the queue initially contains elements in strictly decreasing order: $x_1 > x_2 > \dots > x_n$ , where $n = 16$ .

For the first element $x_1$ : $S$ is empty, so $x_1$ is dequeued and pushed to $S$ ( $1$ iteration). $S = [x_1]$ .
For the second element $x_2$ $x_{2}$ ( $x_2 < x_1$ $x_{2} < x_{1}$ ):
1. $\text{Top}(S) = x_1 > \text{Head}(Q) = x_2 \implies x_1$ is popped from $S$ and enqueued to $Q$ ( $1$ iteration).
2. $S$ is now empty $\implies x_2$ is dequeued from $Q$ and pushed to $S$ ( $1$ iteration).
3. Now $\text{Head}(Q) = x_1 \ge \text{Top}(S) = x_2 \implies x_1$ is dequeued and pushed to $S$ ( $1$ iteration).
  Total iterations to insert $x_2$ when 1 element was on the stack: $1 + 1 + 1 = 3$ iterations. Cumulative iterations for 2 elements: $1 + 3 = 4 = 2^2$ .

In general, when $k$ elements are already sorted on $S$ and the next element at the front of $Q$ is smaller than all of them:

It takes $k$ iterations to pop all $k$ elements from $S$ into $Q$ .
It takes $1$ iteration to dequeue the new element and push it onto the empty stack $S$ .
It takes $k$ iterations to dequeue each of the $k$ elements back from $Q$ and push them onto $S$ .
Thus, placing the $(k+1)$ -th element takes $k + 1 + k = 2k + 1$ iterations.

Summing over all $n$ elements from $k = 0$ to $n - 1$ :

\sum_{k=0}^{n-1} (2k + 1) = n^2

For $n = 16$ elements:

\text{Total iterations} = 16^2 = 256

Final answer

256

Common trap

Miscounting the loop iterations by considering only the push operations ( $16$ ) or neglecting that popped elements must be re-dequeued back into the stack.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 51 of 65, printed as CS Q.41
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source