GATE CS 2023 Q.59: Stacks and Queues

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

Your answer

Official answer and solution

Official answer: 8
From: Official GATE 2023 answer key

Solution

Simulate step-by-step the stack $S$ and queue $Q$ operations.

Given sequence $a = [1, 5, 7, 8, 9, 2]$ :

I: Push $a_0 \dots a_5$ into $S$ : $S = [1, 5, 7, 8, 9, 2]$ (top is 2).
II: Enqueue $a_0 \dots a_5$ into $Q$ : $Q = [1, 5, 7, 8, 9, 2]$ (front is 1).
III: Pop from $S$ : pops 2 $\implies S = [1, 5, 7, 8, 9]$ .
IV: Dequeue from $Q$ : dequeues 1 $\implies Q = [5, 7, 8, 9, 2]$ .
V: Pop from $S$ : pops 9 $\implies S = [1, 5, 7, 8]$ .
VI: Dequeue from $Q$ : dequeues 5 $\implies Q = [7, 8, 9, 2]$ .
VII: Dequeue from $Q$ and push to $S$ : dequeues 7, pushes 7 $\implies S = [1, 5, 7, 8, 7], Q = [8, 9, 2]$ .
VIII: Repeat VII 3 times:
- Dequeue 8, push 8 $\implies S = [1, 5, 7, 8, 7, 8], Q = [9, 2]$ .
- Dequeue 9, push 9 $\implies S = [1, 5, 7, 8, 7, 8, 9], Q = [2]$ .
- Dequeue 2, push 2 $\implies S = [1, 5, 7, 8, 7, 8, 9, 2], Q = []$ .
IX: Pop from $S$ : pops 2 $\implies S = [1, 5, 7, 8, 7, 8, 9]$ .
X: Pop from $S$ : pops 9 $\implies S = [1, 5, 7, 8, 7, 8]$ .

The top element of $S$ is now 8.

Final answer

Common trap

Losing track of the repeated dequeue-and-push operations in step VIII.

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

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 59 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