Deque последний элемент вставки.

Question

Datastructure Degue.

Метод для вставки значения впереди:

Отлично работает

 public void insertLeft(Item item) {       
       if (size == deque.length){
          resize(2 * deque.length);
      }
      deque[start] = item;
      start++;
      size++;
}

Метод для вставки значения в хвост - перезаписать последний элемент из-за этой строки //end = deque.length - 1;

public void insertRight(Item item) {
    if (size == deque.length){
        resize(2 * deque.length);
    }
    end = deque.length - 1;
    deque[end++] = item;
    end %= deque.length;
    size++;
}

Как я могу это исправить?

Answer 1

Скажем, массив имеет размер 10 и в настоящее время имеет 3 значения:

_ _ _ 1 2 3 _ _ _ _
      ^     ^
  start     end

Как видите, ваш insertLeft метод неверен:

• Это заменит существующее значение
• Он перемещает указатель в неправильном направлении
• Это не обрабатывает обтекание

И ваш insertRight метод неверен:

• Выбрасывает end значение

Переосмыслите то, что вы делаете, например, resize() метод обрабатывает условие, где массив обернут?

Пример:

3 4 5 _ _ _ _ _ 1 2
      ^         ^
    end         start

Если вы позвоните insertRight() 5 раз, вы получите:

3 4 5 X X X X X 1 2
                ^
                start
                end

6-й звонок insertRight() вызовет resize(), но правильно ли это с этим справиться? Например, в результате:

3 4 5 X X X X X Y _ _ _ _ _ _ _ _ _ 1 2
                  ^                 ^
                  end               start

Answer 2

deque.length - 1 возвращает индекс последней переменной. Вы должны пройти мимо этого:

deque[++end] = item;