How do I merge two queues into one queue?

Question

Given two queues supporting the operations enqueue/push_back, dequeue/pop_front, and size

Q1: A1 A2 A3
Q2: B1 B2 B3

how do I merge them into a third queue (also supporting the same operations), obtaining:

Q3: A1 B1 A2 B2 A3 B3

I am more interested in an algorithm to use, rather than any specific language implementations.

Solution 1

Here's some pseudocode:

Queue mergeQueues(Queue A, Queue B)
{
    Queue newQ;
    while(A.nonempty() OR B.nonempty())
    {
        if (A.nonempty())
            newQ.push(A.pop());
        if (B.nonempty())
            newQ.push(B.pop());
    }
    return newQ;
}

Where push inserts an element into a queue and pop removes the next element in the queue and returns it.

Note that, this doesn't work for a stack. You will end up with the elements backwards. If you could reverse the stack (for instance, by repeatedly transferring to another stack), then it would work.

Solution 2

While both queues aren't empty, dequeue an item from A and enqueue it to newQ. Then dequeue an item off of queue B. If either of the queues (A or B) are empty, dequeue the rest of the other queue and enqueue each element onto newQ.

Solution 3

It seems quite amenable to a recursive implementation:

mergeQueues :: Queue a -> Queue a -> Queue a
mergeQueues qa qb =
    merge qa qb emptyQueue
    where
        merge qa qb qr
            | isEmpty qa = append qb qr
            | otherwise  = move (merge qb) qa qr
        append q qr
            | isEmpty q  = qr
            | otherwise  = move append q qr
        move f q qr =
            let (val,q') = pop q
             in f q' (push val qr)

Note that we just flip the queues back and forth as we recurse in order to alternate between them, until one is empty, at which point we just append from the one to the other.

Note that, though this is longer than the imperative version given by ribond, this does a minimal number of isEmpty checks. If you don't mind doing as many checks as his does in a slightly more optimized version (assiging the isEmpty values to variables for re-use below), you can remove the append function and just keep calling merge instead, after adding an initial test to merge that tests for both queues being empty and terminating the recursion if so.

For those not familiar with Haskell, we pass in to move the next function to call (this is higher-order functional programming); in the append case, that's just append, in the move case that's a "partially applied" move function: it gets the first parameter, qb applied before we call move, and then move applies the other two parameters.

This sounds like a reasonable task one might encounter in day-to-day business programming. However, if this is a homework function, I suggest you study carefully how the above code works, and I think you'll learn something.

Also, there's a possibility that there's an error in the above code; proving that it works (or finding the bug) would be an excellent exercise.