The GATE Grind

GATE 2023 CS – Question 59

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

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 II1 5 7 8 9 21 5 7 8 9 2
III: pop1 5 7 8 9
IV: dequeue5 7 8 9 2
V: pop1 5 7 8
VI: dequeue7 8 9 2
VII (dequeue 7, push 7)1 5 7 8 78 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**.

More Stacks and Queues questions

All Stacks and Queues questions →