Java添加到队列的前面-deque

Question

这是我的第一个问题，希望大家都好。我必须编写双端队列或双端队列的数组实现，但在理解前面方法的入队元素时遇到了一些麻烦，我通过摆弄了一下让它工作，但我仍然很难理解逻辑:

void addAtFront(E)
{
    if ( front == 0 )
        front = array.length - 1;
    else 
        front = ( front - 1 ) % array.length;

    array [front] = element;

    count++;
}

有人可以解释一下 if 语句中发生了什么吗？如果 front 为 0 那么我们要在数组末尾添加一个元素？这不是和在后面排队一样吗？

Answer 1

您正在使用所谓的循环数组来存储这个双端队列。本质上，您的逻辑以这样的方式工作:用于存储队列的数组在末尾循环并返回到开头，反之亦然。

当您需要将一个元素添加到队列的前面时，您需要将其向左扩展，但是当您处于实际数组实现的开头时(也称为前端索引为零时)，它已经尽可能地向左移动了。解决方案是循环到最后，假装数组是一个大圆圈。

从逻辑上讲，您可以这样做的原因是您的数组和队列实际上并不相同；该数组仅包含您的队列。您可以使用 front 和 back 变量来跟踪在数组中的何处可以找到队列元素。这意味着数组的最后一个元素不一定是队列中的最后一个元素。您的队列可以根据需要遍历数组并沿数组增长。数组对队列的唯一限制是大小；该数组显然无法容纳比它大的队列。

综上所述，您应该具有类似的循环逻辑来将元素添加到队列的末尾。我猜你已经这样做了::

else 
    front = ( front - 1 ) % array.length;

我假设您的 addAtBack 方法具有以下行:

back = (back + 1) % array.length;

该模数运算会为您处理循环。如果后面超出了数组的末尾(也称为后面是 array.length)，则模数会将后面索引设置为 0，将其循环到数组的开头。不幸的是，该模数运算反之则不然，因此您需要 if 语句仅用于添加到前面。您应该能够从 addAtFront 方法中删除该模数运算，并将该行替换为 front--;。