Reversing a list using two queues 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:


Enqueue the next element from the input list (to the tail of either queue).
Dequeue the element at the head of either queue and enqueue it again (to the tail of either queue).
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?
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.