13

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?

Community
  • 1
mjqxxxx
  • 1,468
  • 13
  • 21
  • To clarify: by "the last element from either queue" are you referring to the element at the head of the queue? – Peter Taylor Jan 14 '11 at 21:47
  • @Peter: Yes, thanks for the clarification. I've edited the question. – mjqxxxx Jan 14 '11 at 21:58
  • 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 Jan 15 '11 at 06:32
  • @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 Jan 15 '11 at 13:03

2 Answers2

11

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.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • 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 Jan 15 '11 at 02:57
  • 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 Jan 15 '11 at 03:18
  • 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 Jan 15 '11 at 04:05
  • 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 Jan 15 '11 at 04:25
  • The problem posits an "output list". Can we put them there? – jbapple Jan 15 '11 at 04:50
  • 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 Jan 15 '11 at 05:24
  • $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 Jan 15 '11 at 13:05
  • ... 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 Jan 15 '11 at 13:08
  • Assuming $O(1)$ storage space outside the queue to track how many elements are in the queues. – Peter Taylor Jan 15 '11 at 21:17
  • 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 Jan 15 '11 at 23:10
  • "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 Jan 16 '11 at 02:53
  • @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 Jan 16 '11 at 13:17
  • @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 Jan 16 '11 at 15:45
  • @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 Jan 16 '11 at 17:28
  • 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 Jan 16 '11 at 21:14
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.

Elalfer
  • 111
  • 3