The informal answer is that you can treat two stacks like one tape. The top of the first stack is the current location on the tape. You can move the tape head to the left by popping from Stack 1 and pushing that value onto Stack 2. Pop from Stack 2 and push on Stack 1 to move to the right.

What's really funky is that a DFA with a queue is a Turing machine. You can show this by putting a sentinel value in the queue that separates two stacks and having some crazy loop structures that allow you to push and pop from the two stacks it represents.

See Ullman's book [1] for more details on formal proofs.

Basically you can emulate the Turing machine's tape on the left side of the head with one stack and on the right side with the second stack.

An important question to now ask would be what happens if the tape in the machine has more than two directions; say for example it has a two-dimensional tape. The head may move left, right, but also up and down. It can be proven that such a machine would not be any more capable than the Turing machine with a 1D tape. Again see Ullman's book for details.

[1] http://www.amazon.com/Introduction-Automata-Theory-Languages...

split the tape into 2 halves; the tape to the left of the head is one stack, the tape to the right of the head is the other stack.

Head moving long the tape is just popping from one stack and pushing onto the other. The head state (and other bookkeeping) can be encoded in the DFA.