GATE CS 2026 Set 2 Q.50: Stacks and Queues

Consider a stack $S$ and a queue $Q$ . Both of them are initially empty and have the capacity to store ten elements each. The elements 1, 2, 3, 4, and 5 arrive one by one, in that order. When an element arrives, it is assigned either to $S$ (pushed on $S$ ) or to $Q$ (enqueued to $Q$ ). Once all the five elements are stored, the output is generated in two steps. First, stack $S$ is emptied by popping all elements. Then queue $Q$ is emptied by dequeueing all elements. The output obtained by following this process is 4 3 1 2 5.

Given the output, the objective is to predict whether an element was assigned to $S$ or $Q$ .

Which of the following options is/are possible valid assignment(s) of the elements?

Note: In the options, the notation $xS$ denotes that element $x$ was assigned to $S$ and $yQ$ denotes that element $y$ was assigned to $Q$ .

$1S, 2Q, 3S, 4S, 5Q$

$1Q, 2Q, 3S, 4S, 5Q$

$1Q, 2Q, 3Q, 4S, 5S$

$1S, 2S, 3S, 4Q, 5Q$

Official answer and solution

Official answer: A and B
From: Official GATE 2026 answer key

Solution

Note that elements in $S$ are output in decreasing order (LIFO) followed by elements in $Q$ in increasing order (FIFO).

Since the arrival order is $1, 2, 3, 4, 5$ :

All elements assigned to stack $S$ are popped in strictly decreasing order.
All elements assigned to queue $Q$ are dequeued in strictly increasing order.

In the output 4 3 1 2 5, the split point between $S$ and $Q$ can occur either:

After 4 3 1: $S$ gets $\{1, 3, 4\}$ (popped as 4 3 1) and $Q$ gets $\{2, 5\}$ (dequeued as 2 5). This corresponds to $1S, 2Q, 3S, 4S, 5Q$ (Option A).
After 4 3: $S$ gets $\{3, 4\}$ (popped as 4 3) and $Q$ gets $\{1, 2, 5\}$ (dequeued as 1 2 5). This corresponds to $1Q, 2Q, 3S, 4S, 5Q$ (Option B).

Element 1 can either be at the bottom of stack $S$ or at the front of queue $Q$ , so both (A) and (B) produce 4 3 1 2 5.

Final answer

Options (A), (B)

Common trap

Overlooking that element 1 sits at the boundary between the decreasing prefix 4 3 1 and the increasing suffix 1 2 5.

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

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 50 of 65
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