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

Question

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

Q1: A1 A2 A3
Q2: B1 B2 B3

如何将它们合并到第三个队列(也支持相同的操作)，获得:

Q3: A1 B1 A2 B2 A3 B3

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

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 移除队列中的下一个元素并返回它。

请注意，这不适用于堆栈。你最终会得到元素的倒退。如果您可以反转堆栈(例如，通过重复转移到另一个堆栈)，那么它就可以工作。