<p>The best algorithm I can think of requires $\sum_{i=0}^{N/2-1}(N-2i-2)$ transfers from one queue to another.</p>

<p>Lets name two available queues as left and right. Here is the basic idea of this algorithm with the assumption that N is even:</p>

<ol>
<li>Read values from the initial list of elements and push all odd numbers into the left queue and even numbers into the right queue</li>
<li>One the fist step the fastest way to output the maximum value is to transfer N/2-1 elements from the right queue into the left one and pop the top value from the right queue into the output list</li>
<li>Now we have to do the same for another queue - transfer N/2-1 elements from the left queue into the right one and pop the top element from the left queue into the output list</li>
<li>Swap queues and repeat steps 2 and 3 for N = N-2</li>
</ol>

<p>It is easy to see how algorithm should work for odd N.</p>

CC BY-SA 2.5
2011-01-14T22:38:00.343Z
You can use \$...\$ to insert LaTeX-ish code (minus the \\).
Mark Reitblatt
CC BY-SA 2.5
2011-01-14T22:27:30.210Z
2011-01-14T23:17:22.380Z
2011-01-14T23:17:22.380Z
Elalfer
<p>If N is a power of two, I believe O(N log N) operations suffice, even for a somewhat more restricted problem in which all items start on one of the queues and must end up in reverse order on one of the queues (without the input and output lists).</p>

<p>In O(N) steps it is possible to start with all elements on one queue, play "one for you one for me" to split them into alternating subsets on the other queue, and then concatenate them all back into one queue. In terms of the binary representations of the positions of the items, this implements a rotate operation.</p>

<p>In O(N) steps it is also possible to pull off pairs of elements from one queue, swap them, then put them back, reversing all pairs. In terms of the binary representations of the positions of the items, this complements the low order bit of the position.</p>

<p>By repeating O(log N) times an unshuffle and a pairwise swap, we can complement all the bits of the binary representations of the positions — which is the same thing as reversing the list.</p>

CC BY-SA 2.5
2011-01-15T02:57:09.560Z
Then you can break the list down into a binary representation and reverse piece-by-piece for an O(n lg n) algorithm, I think.
jbapple
CC BY-SA 2.5
2011-01-15T03:18:31.457Z
I was thinking one could extend to all N by using a 2-3 tree instead of binary, but maybe your idea is simpler. But how do you reverse each of the O(log n) pieces in O(n log n) total steps?
David Eppstein
CC BY-SA 2.5
2011-01-15T04:05:58.823Z
The time is O(sum (2^i) lg (2^i)) for i from 0 to [lg n], which Wolfram alpha says is O(n lg n) : http://www.wolframalpha.com/input/?i=sum+(2^k)+log2+(2^k)+from+0+to+log2+n
jbapple
CC BY-SA 2.5
2011-01-15T04:25:47.730Z
Sure, if you can reverse each of the pieces in time proportional to its length times its log, you're done. But you have to put the pieces somewhere once you've reversed them, and that might make it more difficult to reverse the remaining pieces.
David Eppstein
CC BY-SA 2.5
2011-01-15T04:50:20.597Z
The problem posits an "output list". Can we put them there?
jbapple
CC BY-SA 2.5
2011-01-15T05:24:42.110Z
Well, no, because if you take the pieces from the input list in some order then you have to put the reversed pieces into the output list in the opposite order. So we can't put the first piece into the output until the last piece is reversed. But maybe it will work to reverse the power-of-two pieces in order from smallest to largest, so that while you're reversing any one of the pieces, the other pieces only add up to at most the length of the piece you're reversing, and don't slow you down too much.
David Eppstein
CC BY-SA 2.5
2011-01-15T13:05:46.710Z
$O(N \log N)$ moves always suffice.  When one queue is empty, a single pass with $O(N)$ moves can be used to change a configuration $A_1 B_1 A_2 B_2 ... A_n B_n$ of the other queue into $B_1 A_1 B_2 A_2 ... B_n A_n$, where the $A_i$ and $B_i$ are arbitrary blocks of elements.  Just move each pair of blocks $AB$ to the empty queue, spin that queue to swap their locations, and move the reversed pair $BA$ back to the tail of the full queue.  This takes $O(|AB|)$ operations, so the full pass takes $O(N)$. ...
mjqxxxx
CC BY-SA 2.5
2011-01-15T13:08:06.553Z
... You can use this to double the length of the largest properly ordered segment with each pass, such that all segments except the last will always have the same length.  E.g., 7.6.5.4.3.2.1 to 67.45.23.1 to 4567.123 to 1234567.  So $O(\log N)$ passes with $O(N)$ operations each are enough to reverse the whole queue.
mjqxxxx
CC BY-SA 2.5
2011-01-15T21:17:27.357Z
Assuming $O(1)$ storage space outside the queue to track how many elements are in the queues.
Peter Taylor
CC BY-SA 2.5
2011-01-15T23:10:26.200Z
The model I'm using for the problem is that the computation and storage needed to count elements and determine how to move them is irrelevant: the elements we're reversing need to stay on the queues and be moved around using queue operations, under some exterior control, and all we're counting is those queue operations.
David Eppstein
CC BY-SA 2.5
2011-01-16T02:53:22.777Z
"By repeating O(log N) times an unshuffle and a pairwise swap, we can complement all the bits of the binary representations of the positions — which is the same thing as reversing the list."

If you changed the predicate in this step, doesn't this just become mergesort?  In which case there can't be a better algorithm, since we can sort using the same algorithm?
Ritwik Bose
CC BY-SA 2.5
2011-01-16T13:17:44.120Z
@Mechko: You can certainly sort a list in $O(N)$ moves... the usual $O(N\log N)$ complexity of sorting refers to the number of comparisons required.  Moreover, in this case we know the initial order of the list.  So I don't see a proof of optimality in the analogy with mergesort.
mjqxxxx
CC BY-SA 2.5
2011-01-16T15:45:33.673Z
@mjqxxxx What is the distinction between a 'move' and a 'comparison'?  the result of each comparison 'moves' an element from one queue to another.  In any of the standard sorting algorithm, each comparison determines whether our array will look like: [A, x, A', y, A''] or [A, y, A', x, A''] for fixed segments A, A', A'' and x, and y.  I agree that I am very possibly wrong...
Ritwik Bose
CC BY-SA 2.5
2011-01-16T17:28:18.650Z
@Mechko: I believe that this method can be generalized to allow a sequence to be permuted arbitrarily, in O(n log n) moves. Since each move is a binary choice, there would be a matching Ω(n log n) bound for permuting arbitrary permutations, very similar to the sorting lower bound. But reversal is a very specific permutation, not an arbitrary one, so that lower bound technique does not apply to list reversal.
David Eppstein
CC BY-SA 2.5
2011-01-16T21:14:03.830Z
Fair enough.  On the other hand, reversal, while being a specific permutation, is also the permutation that intuitively has the greatest 'distance' from the original.  Reversing the list via queues has the effect of causing the elements to 'trickle' into position, which is where the similarity to sorting comes up.
Ritwik Bose
CC BY-SA 2.5
2011-01-15T00:07:18.127Z
2011-01-15T00:07:18.127Z
David Eppstein
<p>This question is inspired by an <a href="https://cstheory.stackexchange.com/questions/2562/one-stack-two-queues" title="existing question">existing question</a> about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation.  The answer seems to be unknown.  Here is a more specific question, corresponding to the special case in which all PUSH operations are performed first, followed by all POP operations.  How efficiently can a list of $N$ elements be reversed using two initially empty queues?  The legal operations are:</p>

<ol>
<li>Enqueue the next element from the input list (to the tail of either queue).</li>
<li>Dequeue the element at the head of either queue and enqueue it again (to the tail of either queue).</li>
<li>Dequeue the element at the head of either queue and add it to the output list.</li>
</ol>

<p>If the input list consists of elements $[1,2,...,N-1,N]$, how does the minimum number of operations required to generate the reversed output list $[N,N-1,...,2,1]$ behave?  A proof that it grows faster than $O(N)$ would be especially interesting, since it would resolve the original question in the negative.</p>

<hr>

<p>Update (15 Jan 2011): The problem can be solved in $O(N \log N)$, as shown in the submitted answers and their comments; and a lower bound of $\Omega(N)$ is trivial.  Can either of these bounds be improved?</p>

CC BY-SA 2.5
2011-01-14T21:47:35.530Z
To clarify: by "the last element from either queue" are you referring to the element at the head of the queue?
Peter Taylor
CC BY-SA 2.5
2011-01-14T21:58:20.753Z
@Peter: Yes, thanks for the clarification.  I've edited the question.
mjqxxxx
CC BY-SA 2.5
2011-01-15T06:32:01.657Z
Are both the input and output lists stacks? If so, n op1s (to the same queue) followed by n op3s does the reverse, right? I think I must be missing something important.
jbapple
CC BY-SA 2.5
2011-01-15T13:03:20.897Z
@jbapple: No, they aren't stacks.  You need to write elements to the output list in the opposite order they were read from the input list.
mjqxxxx
<ds.algorithms><ds.data-structures><lower-bounds><time-complexity><sorting>
Reversing a list using two queues
mjqxxxx
# Reversing a list using two queues

(Asked by: username_0 on 2011-01-14)

This question is inspired by an [existing question](https://cstheory.stackexchange.com/questions/2562/one-stack-two-queues "existing question") about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation. The answer seems to be unknown. Here is a more specific question, corresponding to the special case in which all PUSH operations are performed first, followed by all POP operations. How efficiently can a list of $N$ elements be reversed using two initially empty queues? The legal operations are:

1. Enqueue the next element from the input list (to the tail of either queue).
2. Dequeue the element at the head of either queue and enqueue it again (to the tail of either queue).
3. Dequeue the element at the head of either queue and add it to the output list.

If the input list consists of elements $[1,2,...,N-1,N]$, how does the minimum number of operations required to generate the reversed output list $[N,N-1,...,2,1]$ behave? A proof that it grows faster than $O(N)$ would be especially interesting, since it would resolve the original question in the negative.

---

Update (15 Jan 2011): The problem can be solved in $O(N \log N)$, as shown in the submitted answers and their comments; and a lower bound of $\Omega(N)$ is trivial. Can either of these bounds be improved?

**Tags:** ds.algorithms, ds.data-structures, lower-bounds, time-complexity, sorting

> **Comments:**
> **username_1**: To clarify: by "the last element from either queue" are you referring to the element at the head of the queue?  
> **username_0**: @Peter: Yes, thanks for the clarification.  I've edited the question.  
> **username_2**: Are both the input and output lists stacks? If so, n op1s (to the same queue) followed by n op3s does the reverse, right? I think I must be missing something important.  
> **username_0**: @username_2: No, they aren't stacks.  You need to write elements to the output list in the opposite order they were read from the input list.  

---

## 2 answers

### Answer by username_5 on 2011-01-15. Score: 11 | Accepted answer

If N is a power of two, I believe O(N log N) operations suffice, even for a somewhat more restricted problem in which all items start on one of the queues and must end up in reverse order on one of the queues (without the input and output lists).

In O(N) steps it is possible to start with all elements on one queue, play "one for you one for me" to split them into alternating subsets on the other queue, and then concatenate them all back into one queue. In terms of the binary representations of the positions of the items, this implements a rotate operation.

In O(N) steps it is also possible to pull off pairs of elements from one queue, swap them, then put them back, reversing all pairs. In terms of the binary representations of the positions of the items, this complements the low order bit of the position.

By repeating O(log N) times an unshuffle and a pairwise swap, we can complement all the bits of the binary representations of the positions — which is the same thing as reversing the list.

> **Comments:**
> **username_2**: Then you can break the list down into a binary representation and reverse piece-by-piece for an O(n lg n) algorithm, I think.  
> **username_5**: I was thinking one could extend to all N by using a 2-3 tree instead of binary, but maybe your idea is simpler. But how do you reverse each of the O(log n) pieces in O(n log n) total steps?  
> **username_2**: The time is O(sum (2^i) lg (2^i)) for i from 0 to [lg n], which Wolfram alpha says is O(n lg n) : http://www.wolframalpha.com/input/?i=sum+(2^k)+log2+(2^k)+from+0+to+log2+n  
> **username_5**: Sure, if you can reverse each of the pieces in time proportional to its length times its log, you're done. But you have to put the pieces somewhere once you've reversed them, and that might make it more difficult to reverse the remaining pieces.  
> **username_2**: The problem posits an "output list". Can we put them there?  
> **username_5**: Well, no, because if you take the pieces from the input list in some order then you have to put the reversed pieces into the output list in the opposite order. So we can't put the first piece into the output until the last piece is reversed. But maybe it will work to reverse the power-of-two pieces in order from smallest to largest, so that while you're reversing any one of the pieces, the other pieces only add up to at most the length of the piece you're reversing, and don't slow you down too much.  
> **username_0**: $O(N \log N)$ moves always suffice.  When one queue is empty, a single pass with $O(N)$ moves can be used to change a configuration $A_1 B_1 A_2 B_2 ... A_n B_n$ of the other queue into $B_1 A_1 B_2 A_2 ... B_n A_n$, where the $A_i$ and $B_i$ are arbitrary blocks of elements.  Just move each pair of blocks $AB$ to the empty queue, spin that queue to swap their locations, and move the reversed pair $BA$ back to the tail of the full queue.  This takes $O(|AB|)$ operations, so the full pass takes $O(N)$. ...  
> **username_0**: ... You can use this to double the length of the largest properly ordered segment with each pass, such that all segments except the last will always have the same length.  E.g., 7.6.5.4.3.2.1 to 67.45.23.1 to 4567.123 to 1234567.  So $O(\log N)$ passes with $O(N)$ operations each are enough to reverse the whole queue.  
> **username_1**: Assuming $O(1)$ storage space outside the queue to track how many elements are in the queues.  
> **username_5**: The model I'm using for the problem is that the computation and storage needed to count elements and determine how to move them is irrelevant: the elements we're reversing need to stay on the queues and be moved around using queue operations, under some exterior control, and all we're counting is those queue operations.  
> **username_6**: "By repeating O(log N) times an unshuffle and a pairwise swap, we can complement all the bits of the binary representations of the positions — which is the same thing as reversing the list."  If you changed the predicate in this step, doesn't this just become mergesort?  In which case there can't be a better algorithm, since we can sort using the same algorithm?  
> **username_0**: @Mechko: You can certainly sort a list in $O(N)$ moves... the usual $O(N\log N)$ complexity of sorting refers to the number of comparisons required.  Moreover, in this case we know the initial order of the list.  So I don't see a proof of optimality in the analogy with mergesort.  
> **username_6**: @username_0 What is the distinction between a 'move' and a 'comparison'?  the result of each comparison 'moves' an element from one queue to another.  In any of the standard sorting algorithm, each comparison determines whether our array will look like: [A, x, A', y, A''] or [A, y, A', x, A''] for fixed segments A, A', A'' and x, and y.  I agree that I am very possibly wrong...  
> **username_5**: @Mechko: I believe that this method can be generalized to allow a sequence to be permuted arbitrarily, in O(n log n) moves. Since each move is a binary choice, there would be a matching Ω(n log n) bound for permuting arbitrary permutations, very similar to the sorting lower bound. But reversal is a very specific permutation, not an arbitrary one, so that lower bound technique does not apply to list reversal.  
> **username_6**: Fair enough.  On the other hand, reversal, while being a specific permutation, is also the permutation that intuitively has the greatest 'distance' from the original.  Reversing the list via queues has the effect of causing the elements to 'trickle' into position, which is where the similarity to sorting comes up.  

---

### Answer by username_3 on 2011-01-14. Score: 1

The best algorithm I can think of requires $\sum\_{i=0}^{N/2-1}(N-2i-2)$ transfers from one queue to another.

Lets name two available queues as left and right. Here is the basic idea of this algorithm with the assumption that N is even:

1. Read values from the initial list of elements and push all odd numbers into the left queue and even numbers into the right queue
2. One the fist step the fastest way to output the maximum value is to transfer N/2-1 elements from the right queue into the left one and pop the top value from the right queue into the output list
3. Now we have to do the same for another queue - transfer N/2-1 elements from the left queue into the right one and pop the top element from the left queue into the output list
4. Swap queues and repeat steps 2 and 3 for N = N-2

It is easy to see how algorithm should work for odd N.

> **Comments:**
> **username_4**: You can use \$...\$ to insert LaTeX-ish code (minus the \\).  

---

