Реализация очереди с круговыми массивами: каков наилучший способ изменить размер кругового массива?

Question

Я реализую очередь , используя круговой массив , и я застрял в реализации метода resize() (когда массив заполнен).

Внутри метода enqueue() я проверяю, равен ли размер массива его длине, и получаю, если он заполнен. Теперь вместо исключения я пытаюсь изменить размер массива.

Дело в том, что у меня есть два случая для рассмотрения

1. спереди <= сзади </li>
2. сзади <спереди </li>

Каков лучший способ скопировать элементы старого массива в новый, больший?

Я думал, что это с помощью цикла 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, использованном для этого, и боюсь, что потерял значения.

Может кто-нибудь сказать мне, есть ли лучший способ сделать это?

Answer 1

Для копирования массивов с более чем несколькими элементами используйте System.arraycopy () , так как обычно он реализован как собственный код, например, Виртуальная машина Sun использует ручной ассемблер.

спереди> сзади

Поскольку данные являются смежными, они могут оставаться в том же месте в новом массиве.

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

спереди <= сзади </strong>

Данные несмежные, поэтому скопируйте оба блока в начало нового массива.

// 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;

Answer 2

Большое спасибо за ваши ответы и различные решения!:)

Хотя использование метода System.arraycopy () является наиболее простым и эффективным решением, мне пришлось отказаться от его использования и самостоятельно реализовать решение.

Итак, если кто-то захочетresize () круговой массив в реализации очереди без 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;

}

Как вы можете видеть, я воспользовался «круглой» вещью и отобразил позициистарого массива в новый массив с использованием оператора%.

Результирующий массив будет иметь двойную емкость и все элементы (сохраняя первоначальный порядок, очевидно) в начале нового массива.

Я проверил это, и он работал правильно.Позвольте мне знать, есть ли какие-либо неудобства с этим кодом.

С уважением

Answer 3

Если ваш массив заполнен, у вас либо front == rear - 1, либо rear == 0 и front == length -1 (или наоборот, я не знаю вашу номенклатуру).Во втором случае вы можете скопировать весь массив за один шаг, в (более общем) первом случае у вас есть два блока (0 .. передний и задний .. длина-1), которые нужно скопировать.

Answer 4

Подумайте о блоках элементов массива, которые вы хотите переместить, и о том, куда они должны перейти в новом массиве. Затем и используйте System.arraycopy, чтобы сделать это. Вы должны вызывать arraycopy один раз, если спереди <тыл, и дважды, если сзади <спереди. </p>