3

我正在使用循环数组实现一个队列,并且我有点卡在resize()方法实现中(当数组已满时)。

在该enqueue()方法中,我检查数组的大小是否等于它的长度,并获取它是否已满。现在,我没有抛出异常,而是尝试调整数组的大小。

问题是,我有两种情况要考虑

  1. 前 <= 后
  2. 后<前

将旧数组的元素复制到更大的新数组中的最佳方法是什么?

我认为它使用for循环,例如:

newArray = new Array[oldArray.length*2];

if (front <= rear) {
    for (int i = front; i < rear; i++) {
        newArray[i] = oldArray[i];
    } 
} else {
    for (int i = front; i < newArray.length; i++) {
        newArray[i] = oldArray[i];
    }

    for (int j = rear; j < front; j++) {
        // i'm using the variable i, the order is maintained
        newArray[i] = oldArray[j];
        i++;
    }
}

然后oldArray= newArray,返回newArray并调整它的大小

我不确定用于执行此操作的 for 数量,我担心我会失去价值。

有人可以告诉我是否有更好的方法来做到这一点?

4

4 回答 4

5

要复制具有多个元素的数组,请使用System.arraycopy(),因为它通常作为本机代码实现,例如 Sun 的 VM 使用手动编码的汇编程序。

前 > 后

由于数据是连续的,因此它可以保留在新数组中的相同位置。

System.arraycopy(oldArray, front, newArray, front, front-rear);

前 <= 后

数据是不连续的,因此将两个块复制到新数组的开头。

// copy [rear to end]
System.arraycopy(oldArray, rear, newArray, 0, oldArray.length-rear);
// copy [0 to front]
System.arraycopy(oldArray, 0, newArray, oldArray.length-rear, front);
front = oldArray.length-(rear-front);
rear = 0;
于 2011-04-17T17:27:34.570 回答
2

非常感谢您的回答和不同的解决方案!:)

尽管使用 System.arraycopy() 方法是最简单有效的解决方案,但我不得不避免使用它并自己实现一个解决方案。

因此,如果有人想在没有 System.arraycopy() 的情况下在队列实现中调整循环数组的大小(),这是我的最终解决方案:

private void resize() {

    E[] aux = (E[]) new Object[Q.length * 2]; // new array

    int i = 0; // use this to control new array positions
    int j = f; // use this to control old array positions

    boolean rearReached = false;

    while (!rearReached) {

        rearReached = j % Q.length == r; // is true if we've reached the rear

        aux[i] = Q[j % Q.length];

        i++;
        j++;

    }

    f = 0;
    r = Q.length - 1;
    Q = aux;

}

如您所见,我利用了“循环”的优势,并使用 % 运算符将旧数组的位置映射到新数组。

结果数组将具有双倍容量和所有元素(显然保持原始顺序)位于新数组的开头。

我已经对其进行了测试,并且工作正常。让我知道该代码是否有任何不便。

问候

于 2011-04-19T22:20:24.243 回答
0

如果您的数组已满,您要么有front == rear - 1,要么rear == 0front == length -1(或相反,我不知道你的命名法)。在第二种情况下,您可以一步复制整个数组,在(更一般的)第一种情况下,您有两个要复制的块(0 .. front 和 back .. length-1)。

于 2011-04-17T17:56:44.417 回答
0

想想你想要移动的数组元素块以及它们应该在新数组中的位置。然后使用 System.arraycopy 来做。如果前 < 后,你应该调用 arraycopy 一次,如果后 < 前,你应该调用两次。

于 2011-04-17T17:24:03.727 回答