取消插入最后一个元素

Question

数据结构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

对insertRight()的第六次调用会触发resize()，但它能正确处理吗？例如，导致：

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

Answer 2

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

deque[++end] = item;