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

Question

给定两个队列，支持enqueue/push_back、dequeue/pop_front和size操作

Q1: A1 A2 A3
Q2: B1 B2 B3

如何将它们合并成第三个队列（也支持相同的操作），得到：

Q3: A1 B1 A2 B2 A3 B3

我更关心使用算法，而不是任何特定语言的实现。

- graffil

---

当一个队列比另一个队列更快地耗尽时，您想要做什么？停止？继续进行，忽略短队列中缺失的任何元素？继续进行，将 null 元素放在缺失元素的位置？ - C. K. Young

Answer 1

以下是一些伪代码：

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;
}

push命令将元素插入队列，而pop命令则移除队列中的下一个元素并返回它。

请注意，这种方法不适用于栈。你最终会得到反向的元素顺序。如果你可以反转栈（例如，通过重复转移到另一个栈），那么它就会起作用。

- rlbond

Answer 2

当A和B队列都不为空时，从队列A中出列一个项目并将其排入newQ。然后从队列B中出列一个项目。如果A或B队列中有任何一个为空，则出列其他队列中的所有元素，并将每个元素排队到newQ中。

- Evan Meagher

Answer 3

这似乎非常适合使用递归实现：

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)

请注意，我们在递归时只是在队列之间来回翻转以交替使用它们，直到其中一个为空，在这种情况下，我们只需从一个队列追加到另一个队列。

请注意，尽管这比ribond给出的命令版本要长，但这样做会最小化isEmpty检查的数量。如果您不介意在稍微优化的版本中执行与他相同数量的检查（将isEmpty值分配给变量以在下面重复使用），则可以删除append函数并继续调用merge，之前需要在merge中添加一个初始测试，用于测试两个队列是否都为空，并在这种情况下终止递归。

对于那些不熟悉Haskell的人，我们将下一个要调用的函数（这是高阶函数式编程）传递给move；在append的情况下，只是追加，在move的情况下，则是一个“部分应用”的move函数：在我们调用move之前，它获取第一个参数qb，然后move应用其他两个参数。

这听起来像是日常业务编程中可能遇到的合理任务。然而，如果这是一项作业函数，我建议您仔细研究上述代码的工作原理，相信您会学到一些东西。

此外，上述代码可能存在错误；证明它的有效性（或找到错误）将是一项极好的练习。

- cjs