Java 添加到队列的前面 - 双端队列

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

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

当你需要将一个元素添加到队列的前面时，你需要将它扩展到左侧，但是当你在实际数组实现的开始时（a.k.a当前面index 为零），它已经是最左边了。解决办法就是一直循环到最后，假装数组是一个大圆

你之所以可以这样做是因为你的数组和你的队列实际上并不相同；该数组仅包含您的队列。您使用 front 和 back 变量来跟踪可以在数组中找到队列元素的位置。这意味着数组的最后一个元素不一定是队列中的最后一个元素。您的队列可以根据需要遍历并沿着数组增长。数组对队列的唯一限制是大小；该数组显然不能容纳比它更大的队列。

综上所述，您应该有类似的循环逻辑来将元素添加到队列的后面。我猜你已经基于这个做了::

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

我假设您的 addAtBack 方法有这一行：

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

该模数运算会为您处理循环。如果后面超过数组的末尾（a.k.a。后面是array.length），模数会将后面的索引设置为 0，循环到数组的开头。不幸的是，该模数运算不能以相反的方式有效地工作，因此为什么您需要该 if 语句仅用于添加到前面。您应该能够从 addAtFront 方法中删除该模数运算并将该行替换为 front--;.

Java 添加到队列的前面 - 双端队列

Java adding to the front of queue - deque

java

queue

deque