Question

Consider a sequence $a$ of elements $a_0=1,\,a_1=5,\,a_2=7,\,a_3=8,\,a_4=9,\,a_5=2$. The following operations are performed on a stack $S$ and a queue $Q$, both 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$.

Hint:

Track stack (LIFO) and queue (FIFO) states explicitly after each step. For “dequeue and push” moves, the queue’s front element becomes the new stack top.

Answer 1

Step 1: Track elements removed so far

After the initial insertions, both structures contain the same elements:
Stack (bottom → top): [1, 5, 7, 8, 9, 2]
Queue (front → rear): [1, 5, 7, 8, 9, 2]

---

Step 2: Apply the first removals

Removing from the stack eliminates the most recent element:
Stack becomes [1, 5, 7, 8, 9]

Removing from the queue eliminates the earliest element:
Queue becomes [5, 7, 8, 9, 2]

---

Step 3: Apply the next pair of removals

Next stack removal deletes 9:
Stack → [1, 5, 7, 8]

Next queue removal deletes 5:
Queue → [7, 8, 9, 2]

---

Step 4: Transfer remaining queue elements to the stack

Each remaining queue element is moved to the stack in order:

• Move 7 → Stack becomes [1, 5, 7, 8, 7]
• Move 8 → Stack becomes [1, 5, 7, 8, 7, 8]
• Move 9 → Stack becomes [1, 5, 7, 8, 7, 8, 9]
• Move 2 → Stack becomes [1, 5, 7, 8, 7, 8, 9, 2]

Queue is now empty.

---

Step 5: Final removals from the stack

Removing the top element deletes 2:
Stack → [1, 5, 7, 8, 7, 8, 9]

Removing once more deletes 9:
Stack → [1, 5, 7, 8, 7, 8]

---

Final Answer:

Top element of the stack = 8