GATE 2023 CS Q.59: solution and answer

GATE 2023 · CSQ.59 · 2 marks · NAT

Consider a sequence $a$ of elements $a_{0} = 1$ , $a_{1} = 5$ , $a_{2} = 7$ , $a_{3} = 8$ , $a_{4} = 9$ , and $a_{5} = 2$ . The following operations are performed on a stack $S$ and a queue $Q$ , both of which are initially empty.

I: push the elements of $a$ from $a_{0}$ to $a_{5}$ in that order into $S$ .

II: enqueue the elements of $a$ from $a_{0}$ to $a_{5}$ in that order into $Q$ .

III: pop an element from $S$ .

IV: dequeue an element from $Q$ .

V: pop an element from $S$ .

VI: dequeue an element from $Q$ .

VII: dequeue an element from $Q$ and push the same element into $S$ .

VIII: Repeat operation VII three times.

IX: pop an element from $S$ .

X: pop an element from $S$ .

The top element of $S$ after executing the above operations is ____ (answer as an integer).

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The top element of S after executing all operations is 8.

Official answer: 8Source: Official answer key, GATE 2023 CS (IIT Kanpur)

Push $a_{0} .. a_{5}$ into $S$ in order: $S$ (bottom→top) $= 1, 5, 7, 8, 9, 2$ .
Enqueue $a_{0} .. a_{5}$ into $Q$ in order: $Q$ (front→back) $= 1, 5, 7, 8, 9, 2$ .
III: pop $S$ removes $2$ ; $S = 1, 5, 7, 8, 9$ .
IV: dequeue $Q$ removes $1$ ; $Q = 5, 7, 8, 9, 2$ .
V: pop $S$ removes $9$ ; $S = 1, 5, 7, 8$ .
VI: dequeue $Q$ removes $5$ ; $Q = 7, 8, 9, 2$ .
VII: dequeue $Q$ removes $7$ , push $7$ onto $S$ ; $Q = 8, 9, 2$ ; $S = 1, 5, 7, 8, 7$ .
VIII (repeat VII three more times): dequeue $8$ → push $8$ ( $Q = 9, 2$ ; $S = 1, 5, 7, 8, 7, 8$ ); dequeue $9$ → push $9$ ( $Q = 2$ ; $S = 1, 5, 7, 8, 7, 8, 9$ ); dequeue $2$ → push $2$ ( $Q = empty$ ; $S = 1, 5, 7, 8, 7, 8, 9, 2$ ).
IX: pop $S$ removes $2$ ; $S = 1, 5, 7, 8, 7, 8, 9$ (top $= 9$ ).
X: pop $S$ removes $9$ ; $S = 1, 5, 7, 8, 7, 8$ (top $= 8$ ).

KEY IDEA

Simulate the stack and queue step by step exactly in the order the operations are listed, tracking the full contents (not just the top/front) so each subsequent pop/dequeue references the correct element.

WATCH OUT FOR

Losing track of the moving front of Q while three separate dequeue-and-push actions happen in operation VIII (mixing up which element is currently at the front of Q), or forgetting that operation III pops before operation IV dequeues, so mis-ordering the interleaving of pops/dequeues against pushes/enqueues.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 13 Linear structures questions, with notes

GATE 2023 CS Q.59: solution and answer

Answer and solution

More Linear structures questions