0

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

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]而queue2将保持[5,6,7,8,9,10]

    public void mergeQs(ArrayQmerge q){}

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

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

4

3 回答 3

1

可能对您有所帮助的一个细节是，私有字段在 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;
}
于 2012-11-21T21:38:31.063 回答
0

你可以在merge方法中在本地新建一个Queue，然后将你的类的队列分配给本地版本。

于 2012-11-21T20:36:29.023 回答
0

由于您使用的是自己的自制软件ArrayQueue，因此这是猜想。

创建一个新队列并返回正如我认为您已经说过的那样更容易，更有效，因为将元素插入到支持数组的结构中将涉及为每个插入操作将其余元素向下移动一个位置。

An alternative is to implement public void mergeQs(ArrayQmerge q) by swapping out the underlying array you have backing it. So you get the same easy implementation as returning a new Queue but with the same in place side effect.

于 2012-11-21T21:39:42.933 回答