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: After I and II
$S$ (bottom$\to$top): $[1,5,7,8,9,2]$; $Q$ (front$\to$rear): $[1,5,7,8,9,2]$.
Step 2: III and IV
III: pop $2 \Rightarrow S=[1,5,7,8,9]$.
IV: dequeue $1 \Rightarrow Q=[5,7,8,9,2]$. Step 3: V and VI
V: pop $9 \Rightarrow S=[1,5,7,8]$.
VI: dequeue $5 \Rightarrow Q=[7,8,9,2]$. Step 4: VII once, then VIII three times
VII: dequeue $7$, push to $S \Rightarrow S=[1,5,7,8,7],\; Q=[8,9,2]$.
VIII-1: dequeue $8$, push $\Rightarrow S=[1,5,7,8,7,8],\; Q=[9,2]$.
VIII-2: dequeue $9$, push $\Rightarrow S=[1,5,7,8,7,8,9],\; Q=[2]$.
VIII-3: dequeue $2$, push $\Rightarrow S=[1,5,7,8,7,8,9,2],\; Q=[\,]$. Step 5: IX and X
IX: pop $2 \Rightarrow S=[1,5,7,8,7,8,9]$.
X: pop $9 \Rightarrow S=[1,5,7,8,7,8]$ with top \(=8\). \[ \boxed{8} \]