如何将两个队列合并为一个队列？

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

给定两个队列支持操作enqueue / push_back,dequeue / pop_front和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.

我对使用的算法更感兴趣,而不是任何特定的语言实现。

3 个解决方案

#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.

push将元素插入队列并弹出删除队列中的下一个元素并返回它。

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.

请注意,这不适用于堆栈。你将最终向后回到元素。如果你可以反转堆栈(例如,通过重复转移到另一个堆栈),那么它将起作用。

#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.

当两个队列都不为空时,将项目从A出列并将其排入newQ。然后将一个项目从队列B中取出。如果队列中的任何一个(A或B)为空,则将其他队列的其余部分出列,并将每个元素排入newQ。

#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.

请注意,虽然这比ribond给出的命令式版本更长,但这会进行最少量的isEmpty检查。如果您不介意在稍微更优化的版本中执行尽可能多的检查(将isEmpty值分配给变量以便在下面重复使用),则可以删除append函数并在添加初始值后继续调用merge测试合并两个队列为空的测试,如果是,则终止递归。

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.

对于那些不熟悉Haskell的人,我们传入下一个函数来调用(这是高阶函数式编程);在附加的情况下,这只是附加,在移动情况下是“部分应用”移动函数:它获取第一个参数,在我们调用move之前应用qb,然后移动应用其他两个参数。

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.

此外,上述代码中可能存在错误;证明它有效(或找到错误)将是一个很好的练习。

#1