GATE CSE 2023 | Question: 49

Question

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.

1. $\textsf{push}$ the elements of $a$ from $a_{0}$ to $a_{5}$ in that order into $S$.
2. $\textsf{enqueue}$ the elements of $a$ from $a_{0}$ to $a_{5}$ in that order into $Q$.
3. $\textsf{pop}$ an element from $S$.
4. $\textsf{dequeue}$ an element from $Q$.
5. $\textsf{pop}$ an element from $S$.
6. $\textsf{dequeue}$ an element from $Q$.
7. $\textsf{dequeue}$ an element from $Q$ and push the same element into $S$.
8. Repeat operation $\text{VII}$ three times.
9. $\textsf{pop}$ an element from $S$.
10. $\textsf{pop}$ an element from $S$.

The top element of $S$ after executing the above operations is ______________.

Comments

the question said to repeat the steps 3 times does it mean that we should have done it in a total of 4 times ??

---

yes, after performing step 7 repeat this process 3 more times; total 4 times

---

but as far as I remember more word was not there in the GATE paper

Answer 1

Given initial elements: $a_0=1,a_1=5,a_2=7,a_3=8,a_4=9,a_5=2$

1)  Push all the elements into the stack $S$ in the same order:

2

9

8

7

5

1

2) Push all the elements into the queue $Q$ in the same order:

1

5

7

8

9

2

 

3) Pop(S):

9

8

7

5

1

 

4) Dequeue(Q):

5

7

8

9

2

 

5) Pop(S):

8

7

5

1

6) Dequeue (Q):

7

8

9

2

7)  Dequeue (Q) and push the same element into S:

8

9

2

 

7

8

7

5

1

 

8) repeat step 7  three times we get:

First time:

9

2

 

 

8

7

8

7

5

1

second time: 

2

 

9

8

7

8

7

5

1

third time:

2
9
8
7
8
7
5
1

9 ) pop (S):

9

8

7

8

7

5

1

 

10 ) pop(S):

8

7

8

7

5

1

from the resultant stack $S$ topmost element is $8$

The correct answer is $8$

Answer 2

Answer: 8

Answer 3

Given initial elements: $a_0=1,a_1=5,a_2=7,a_3=8,a_4=9,a_5=2$

1)  Push all the elements into the stack $S$ in same order:

2

9

8

7

5

1

2) Push all the elements into the queue $Q$ in the same order:

1

5

7

8

9

2

 

3) Pop(S):

9

8

7

5

1

 

4) Dequeue(Q):

5

7

8

9

2

 

5) Pop(S):

8

7

5

1

6) Dequeue (Q):

7

8

9

2

7)  Dequeue (Q) and push the same element into S:

8

9

2

 

7

8

7

5

1

 

8) repeat step 7  three times we get:

First time:

9

2

 

 

8

7

8

7

5

1

second time: 

2

 

9

8

7

8

7

5

1

third time:

2
9
8
7
8
7
5
1

9 ) pop (S):

9

8

7

8

7

5

1

 

10 ) pop(S):

8

7

8

7

5

1

from the resultant stack $S$ topmost element is $8$

The correct answer is $8$