使用循环数组的队列实现：调整循环数组大小的最佳方法是哪一种？

| 我正在使用圆形数组来实现队列，并且我有点陷入resize()方法的实现中（当数组已满时）。在enqueue()方法内部，我检查数组的大小是否等于其长度，并获取数组是否已满。现在，我没有引发异常，而是尝试调整数组的大小。事情是，我有两种情况要考虑前<=后后<前将旧数组的元素复制到更大的新数组中的最佳方法是什么？我认为它使用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 个回复

甲车劲

如果要复制包含多个元素的数组，请使用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;

惭法搽

非常感谢您的答案和不同的解决方案！ :) 尽管使用System.arraycopy（）方法是最简单，最有效的解决方案，但我不得不避免使用它，而是自己实现一个解决方案。因此，如果有人想在没有System.arraycopy（）的队列实现中调整size（）圆形数组，这是我的最终解决方案：

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;

}

如您所见，我利用了“ circular \”的优势，并使用％运算符将旧数组的位置映射到了新数组。生成的数组将具有两倍的容量，并且所有元素（显然要保持原始顺序）都位于新数组的开头。我已经对其进行了测试，并且工作正常。 Lemme知道该代码是否有任何不便之处。问候

诉嘎归亮

考虑一下要移动的数组元素的块以及它们在新数组中的位置。然后，使用System.arraycopy进行操作。如果front

慷祈霖黑

如果数组已满，则可能有have9ѭ，rear == 0和front == length -1（或者反之，我不知道您的命名法）。在第二种情况下，您可以一步来复制整个数组，在（更一般的）第一种情况下，您有两个块（0 ..前面和后面.. length-1）要复制。

要回复问题请先登录或注册

使用循环数组的队列实现：调整循环数组大小的最佳方法是哪一种？

4 个回复

发起人

queue

circular_buffer

arrays

resize

java

问题状态

使用循环数组的队列实现：调整循环数组大小的最佳方法是哪一种？

与内容相关的链接

4 个回复

发起人

queue

circular_buffer

arrays

resize

java

问题状态