Reversing a list using two queues

Question

This question is inspired by an 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?

Answer 1

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.

Answer 2

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.