# How can one simulate a PDA with a FIFO queue PDA?

I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most element which can be popped. When we push something, it goes to the top of the stack.

In a queue, as I understand, elements get "pushed" to the top, but pop from the bottom. Thus, first in first out.

In a stack (LIFO) PDA, let's say we push 'a'. It's at the top of the stack, and when we pop, we pop 'a' since it is at the top.

In a queue (FIFO) PDA, when we push 'a', it is at the top, but when we pop, it will be from the bottom of the queue and thus it will not be 'a' (assuming the size is greater than 2).

So how can we simulate a regular PDA which uses a stack, with a FIFO (queue) PDA?

-
Are you limited to one queue? It's relatively easy with two. – Luke Mathieson Nov 29 '12 at 1:01
Not limited to one queue. – San Nov 29 '12 at 1:03
You may be interested in our thoughts on heap automata. – Raphael Nov 29 '12 at 16:47
@Raphael: interesting. I added a reaction to follow-up question 5 "Does adding heaps increase power for type-1?" in the linked page. – Hendrik Jan Dec 4 '12 at 0:31

Consider the stack like (bottom) ABCD (top). stack-pop is from top, queue-pop is from bottom (this is directed to myself, I am easily confused). Pushes are from top.
Now, if we want to stack-pop, we push a marker # (to top) then repeatedly queue-pop and push, essentially moving everything from bottom to top. If we delay the pushes by one, we are able to stack-pop, just not pushing the last symbol before the #.