13
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ To clarify: by "the last element from either queue" are you referring to the element at the head of the queue? $\endgroup$
    – Peter Taylor
    Jan 14, 2011 at 21:47
  • $\begingroup$ @Peter: Yes, thanks for the clarification. I've edited the question. $\endgroup$
    – mjqxxxx
    Jan 14, 2011 at 21:58
  • $\begingroup$ 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. $\endgroup$
    – jbapple
    Jan 15, 2011 at 6:32
  • $\begingroup$ @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. $\endgroup$
    – mjqxxxx
    Jan 15, 2011 at 13:03

2 Answers 2

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
15
  • $\begingroup$ 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. $\endgroup$
    – jbapple
    Jan 15, 2011 at 2:57
  • $\begingroup$ 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? $\endgroup$
    – David Eppstein
    Jan 15, 2011 at 3:18
  • $\begingroup$ 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) : wolframalpha.com/input/?i=sum+(2^k)+log2+(2^k)+from+0+to+log2+n $\endgroup$
    – jbapple
    Jan 15, 2011 at 4:05
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Jan 15, 2011 at 4:25
  • $\begingroup$ The problem posits an "output list". Can we put them there? $\endgroup$
    – jbapple
    Jan 15, 2011 at 4:50
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You can use \$...\$ to insert LaTeX-ish code (minus the \). $\endgroup$
    – Mark Reitblatt
    Jan 14, 2011 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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