双端队列最后一个元素插入。

Question

数据结构异常。

前面插入值的方法：

工作正常。

 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

deque.length - 1 返回最后一个变量的索引。你必须通过一个：

deque[++end] = item;

Answer 2

假设数组大小为 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

双端队列最后一个元素插入。

Deque last element insert.

java

algorithm

deque