# What if I replace a stack with a queue?

Suppose I have a PDA $P$. What if I replace its First-In-Last-Out stack with a First-In-First-Out queue?

Is this new machine with a queue just as powerful as a PDA? Can it represent the same languages? I feel that it can because we can still count input with it. Does that make sense?

-
You get math.queueexchange.com. –  Asaf Karagila Oct 21 '12 at 10:41

Yes. No. With a FIFO you even get a much more powerful machine, equivalent to a Turing machine. Intuitively, you are able to use the FIFO to "rotate" the information in it, so you can reach every position. That means you have in fact a Turing tape.

-
It seems to me that the answer to the OP's question is 'Yes, and in fact it is much more powerful', rather than 'No' (but with the same explanation). –  Tara B Oct 19 '12 at 21:55
You are right, that seems better. I was a little overreacting to the "just as powerful". –  Hendrik Jan Oct 19 '12 at 23:06