The GATE Grind

GATE 2016 CS (CS1) – Question 51

Programming and Data Structures · Stacks and Queues · 2 marks · Numerical answer

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 ________.

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}.$$

More Stacks and Queues questions

All Stacks and Queues questions →