GATE 2023 CS – Question 59
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 ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 8
Explanation
Push $1,5,7,8,9,2$ onto $S$ (2 on top) and enqueue the same elements in $Q$ (1 at the head).
| Operation | $S$ (bottom → top) | $Q$ (head → tail) |
|---|---|---|
| After I and II | 1 5 7 8 9 2 | 1 5 7 8 9 2 |
| III: pop | 1 5 7 8 9 | |
| IV: dequeue | 5 7 8 9 2 | |
| V: pop | 1 5 7 8 | |
| VI: dequeue | 7 8 9 2 | |
| VII (dequeue 7, push 7) | 1 5 7 8 7 | 8 9 2 |
| VIII: repeat 3 times (8, 9, 2) | 1 5 7 8 7 8 9 2 | (empty) |
| IX: pop (2) | 1 5 7 8 7 8 9 | |
| X: pop (9) | 1 5 7 8 7 8 |
The top of $S$ is **8**.