# Queue, moving the element at the tail to the head

Suppose I have a queue where I pull from left and push to the right, and suppose I have the contents in the queue as $a b c @ d e$ (from left to right, left is head, right is tail).

Is there a simple algorithm that doesn't require extra structures that makes $e$ at the head? meaning to get us to the queue $eabc@d$?

P.S.: I need an algorithm like that for the purpose of a queue automaton.

• What exactly do you want to accomplish? What exactly are the restrictions? Can I propose an alternate data structure? If so, what operations do you want the data structure to support? (push, pop, and reverse?) Do I have to use an existing queue using only its defined operations (push and pop)? Are there any side restrictions, like prohibitions on the amount of space I can use on the side? Please edit your question to be a lot more careful about specifying the problem and requirements. – D.W. Jan 3 '14 at 8:16

• In principle OK, but note that we do not know when to stop moving the elements, unless we recognize the last element $e$. To solve this we have to add a special "fresh" symbol $\Box$ that marks the initial position and move until we reach $\Box$ again. That in fact means we are one symbol too far, we just moved past $e$, so we have to delay pushing by one symbol (keeping it in memory) so we push only when the next symbol is seen. See How can one simulate a PDA with a FIFO queue PDA? – Hendrik Jan Jan 3 '14 at 0:27
• @HendrikJan, are you assuming we're limited to using the queue through its defined API (only push and pop) and we're limited on using at most $O(1)$ space apart from the queue and one additional queue, or something like that? None of those restrictions were stated in the question, so how can you know that this answer is not OK? I would hesitate to critique an answer for failure to comply with assumed requirements that weren't stated explicitly in the question. – D.W. Jan 3 '14 at 8:19
• I merely converted everything in the queue to doubles, for example $ab@d$, we push $\#$, then convert to doubles as in $(a,b)(b,@)(@,d)(d,\#)$ then do the appropriate algorithm. – TheNotMe Jan 3 '14 at 9:22
• @D.W. My interpretation was: "given a queue how do I 'rotate' one symbol from right to left if we are allowed only to move symbols the opposite direction?" For arbitrary input we need to know when to stop. This interpretation is prompted by the P.S. which seems to ask "how do I simulate a deque by a queue?" in the context of automata. For automata indeed the $O(1)$ space and specific abstract model (API) are important: if we use any additional data structure we easily end up with a Turing Machine. Indeed not everything was explicit: I merely added a comment rather than starting a new answer. – Hendrik Jan Jan 3 '14 at 11:17