Реализация очереди с круговым массивом - PullRequest
Новая
       39

Реализация очереди с круговым массивом

2 голосов
/ 30 декабря 2011

Я читаю о реализации DynaArrayQueue (очереди, которая удваивается в размере, когда не хватает элементов)

У меня есть определенные вопросы относительно двух методов в нем.

Пусть емкость будет емкость очереди.

getQueueSize () Метод 

public int getQueueSize()
 {
if(front == -1) return 0;

//Here why can't the size by  simply [(rear -front +1) %capacity ]
int size = (capacity - front + rear +1) % capacity;

if(size == 0) return capacity;
else return size;
 }

При расчете размера, почему мы используем

размер= (емкость - спереди + сзади +1) % вместимости, вместо просто (сзади - спереди +1) % емкости.?

Вопрос 2:

resizeQueue ()

Этот метод изменяет размер очереди 

  private void resizeQueue()
 {
int initCapacity = capacity;
capacity *=2;

int[] oldArray = array;

array = new init[this.capacity];

//this is fine
for(int i=0; i<oldArray.length;i++)
{
    array[i] =oldArray[i];
}

//why do we need this ?
if(rear < front)
{
    for(int i =0 ; i<front ; i++)
    {
        array[i+initCapacity] = this.array[i];
        array[i]= null;

    }

    rear = rear + initCapacity;

}


  }

Первый цикл for в методе является прямым, но зачем нам второй цикл if для? .В каких условиях он заботится?

Ответы [ 3 ]

8 голосов
/ 30 декабря 2011

1.Причина заключается в том, что 

(rear - front)

может быть отрицательным, отрицательный модуль зависит от языковой реализации.

2.Причина, по которой у вас есть второй цикл, заключается в том, что

В этой ситуации 

[#####000000####]
     ^      ^
    rear   front

# is array item
0 is empty space

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

[#####000000####000000000000000]

второй цикл перемещается 

[#####000000####000000000000000]
 ^---^

в 

[00000000000#########0000000000]
                ^---^
1 голос
/ 30 декабря 2011

Второй цикл гарантирует, что элементы хранятся в правильном порядке в новом массиве. Представьте себе круговой буфер, где спереди (место, откуда вы берете) больше, чем сзади (там, где вы добавляете вещи). Таким образом, емкость равна 50, передняя часть равна 40, а задняя часть равна 10. Элементы будут удалены из очереди в порядке 40, 41, 42, 43 ... 0, 1, 2, ... 9.

Теперь, когда вы изменяете размер очереди, элементы копируются в новый массив в том же порядке. Но удаление элементов из очереди, которая теперь имеет емкость 100, будет 40, 41, 42, ... 49, 50, 51. Но в позиции 50 ничего нет!

Таким образом, эти 10 элементов перемещаются из позиций с 0 по 9 в позиции с 50 по 59. Вот что делает второй цикл.

0 голосов
/ 30 декабря 2011

Не знаком с этим классом, но я предполагаю, что если очередь обернута так, что новые элементы пишутся в начале массива, тогда «задний» может быть меньше, чем «передний». Этот вид отвечает на оба ваших вопроса, потому что в этом случае (rear - front +1) % capacity будет отрицательным, а это не то, что вы хотите (Q1), а также новая часть очереди должна быть трансплантирована до конца, что увеличение емкости (Q2).

...