java - Java 中的合并队列

Question

我想知道编写将 ArrayQueue 与另一个队列合并的方法的最佳方法是什么，而不从传递的 q 中删除任何元素。

eg. queue1 = [1,2,3,4] and queue2 = [5,6,7,8,9,10].

当调用 queue1.mergeQs(queue2) 时，它将创建 queue1 = [1,5,2,6,3,7,4,8,9,10] code> 而 queue2 将保留 [5,6,7,8,9,10]

    public void mergeQs(ArrayQmerge q){}

这种方式似乎比传递两个队列并返回一个新的合并队列更难实现。谢谢。

为了澄清，我正在寻找一种方法来交错两个队列中的元素。

Answer 1

一个可能对您有帮助的细节是，私有(private)字段在 Java 中同一类的不同对象之间是可见的。这意味着，只要您只想合并自己类的队列，您的代码就可以完全访问所有内部字段，例如用于存储元素的数组。

对于最简单的情况，所有元素都存储在线性数组中，队列头位于索引零，这样的情况可能是一个开始:

public void mergeQs(ArrayQmerge q) {
    Object[] array = new Object[this.size() + q.size()];

    int i;
    int o;

    // Interleave elements
    for (i = 0, o = 0; i < this.size() && i < q.size(); ++i) {
        array[o++] = this.array[i];
        array[o++] = q.array[i];
    }

    // Copy the remaining elements
    while (i < this.size()) {
        array[o++] = this.array[i++];
    }

    while (i < q.size()) {
        array[o++] = q.array[i++];
    }

    this.array = array;
}