12
$\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?

$\endgroup$
  • $\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 '11 at 21:47
  • $\begingroup$ @Peter: Yes, thanks for the clarification. I've edited the question. $\endgroup$ – mjqxxxx Jan 14 '11 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 '11 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 '11 at 13:03
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.

$\endgroup$
  • $\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 '11 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 '11 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 '11 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 '11 at 4:25
  • $\begingroup$ The problem posits an "output list". Can we put them there? $\endgroup$ – jbapple Jan 15 '11 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.

$\endgroup$
  • $\begingroup$ You can use \$...\$ to insert LaTeX-ish code (minus the \). $\endgroup$ – Mark Reitblatt Jan 14 '11 at 22:38

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.