使用循环数组实现队列:哪种方法可以调整圆形数组的大小？

Question

我正在使用一个循环数组实现一个队列,我有点陷入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并调整大小

我不确定用于做这件事的数量,我担心我会失去价值观.

有人能告诉我是否有更好的方法吗？

Answer 1

要复制具有多个元素的数组,请使用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;