Recursive methods with stacks

I'm doing some practice papers for revision for my finals and I came across this question:


"This question is about recursion. A recursive method can always be implemented by an iterative method that uses a stack to keep track of intermediate values. Could the stack be replaced by, for example, a queue? Explain (no explanation means no marks)."

And their answer is:
"No, a stack is needed to reuse the results of the recursive calls, which means we need a LIFO (i.e., reversed) order. A stack is perfect since each call can be interpreted as a push and each return as a pop of the result."

Now this is sort of confusing me. Couldn't you also say that a queue is also okay because each call can be interpreted as an append and each return can be interpreted as a serve?

If you are allowed to use one extra variable, then a queue can simulate a stack, so in this model a queue plus a single extra storage location will suffice.

The idea is to represent a stack, say $[\ a\ b\ c\ $(top), as a queue, (tail) $\langle c\ b\ a\rangle$ (head). Then the operation $\mathtt{push(x)}$ would correspond to $\mathtt{enque(x)}$, so
$$
[\ a\ b\ c\quad \stackrel{\mathtt{push(x)}}{\longrightarrow}\quad[\ a\ b\ c\ x
$$
would be simulated as
$$
\langle\ c\ b\ a \rangle\quad \stackrel{\mathtt{enque(x)}}{\longrightarrow}\quad\langle\ x\ c\ b\ a\ \rangle
$$
The $\mathtt{pop()}$ operation is a bit more complicated. We first enqueue a marker, #, and then keep pulling elements off the head of the queue and placing them back on the tail until we come to the marker, indicating that the last element we pulled off corresponds to the top of the stack, so we don’t replace that element on the queue and we finish by removing the marker. In pseudocode, what we do is:

enque(#)
v = head()              ; save the head element
deque()                 ; remove it
while (head() != #)
   enque(v)             ; put the element back on the tail
   v = head()           ; save the next element
   deque()              ; remove it
deque()                 ; finally, remove the marker

For example, starting with $\langle c\ b\ a\rangle$, we'd have
$$\begin{align}
\langle\ c\ b\ a\ \rangle &\longrightarrow \langle\ \mathtt{\#}\ c\ b\ a\ \rangle \\
&\longrightarrow \langle\ a\ \mathtt{\#}\ c\ b\ \rangle \\
&\longrightarrow \langle\ b\ a\ \mathtt{\#}\ c\ \rangle \\
&\longrightarrow \langle\ b\ a\ \mathtt{\#}\ \rangle \\
&\longrightarrow \langle\ b\ a\ \rangle
\end{align}$$

StackExchange Computer Science Q#32510, answer score: 2