0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Jan 3 '14 at 8:16
4
$\begingroup$

If you can only push (enqueue) or pull (dequeue) from the queue, then your only option is to pull all the elements and re-enter them.

If you need such an operation, you can use deque (double-ended queue). See: http://en.wikipedia.org/wiki/Double-ended_queue .

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Hendrik Jan Jan 3 '14 at 0:27
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W.♦ Jan 3 '14 at 8:19
  • $\begingroup$ @HendrikJan that's how I solved it afterall. $\endgroup$ – TheNotMe Jan 3 '14 at 9:21
  • $\begingroup$ 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. $\endgroup$ – TheNotMe Jan 3 '14 at 9:22
  • $\begingroup$ @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. $\endgroup$ – Hendrik Jan Jan 3 '14 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.