java - CircularArrayQueue 类中的 Enqueue 方法

Question

我在CircularArrayQueue类中遇到了enqueue()方法:

public void enqueue (T element) {
if (size() == queue.length){
expandCapacity();
}
queue[rear] = element;
rear = (rear+1) % queue.length;
count++;
}

我不太明白代码中的rear = (rear+1) %queue.length;部分的作用，有人可以分解该行代码的步骤吗？

我确实明白，随着添加了新元素，它会增加 rear ，但我不确定 % 操作。

Answer 1

可视化所发生情况的一种方法是想象一个时钟(通常用作模算术的类比，这发生在您提到的使用 % 运算符的行中)。

例如，假设 CircularArrayQueue目前大小为 4，长度为 5(索引 0 - 4)。在下面的示例中，rear 的当前值为 4(索引 4)

内部数组中的项目可能如下所示:

INDEX | 0 | 1 | 2 | 3 | 4 |
VALUE |   | 8 | 9 | 2 | 1 |
                        ^
                        |
                       Rear 

现在假设您将值 7 插入到 CircularArrayQueue 中，然后是行

rear = (rear + 1) % queue.length;

将被执行。这有效地计算了以下内容:

add 1 to rear (4) -> 5
divide by queue.length (5) -> 5 / 5 = 1 (remainder of 0)
take the remainder of the previous division (0) and set it equal to rear

INDEX | 0 | 1 | 2 | 3 | 4 |
VALUE | 7 | 8 | 9 | 2 | 1 |
        ^
        |
       Rear 

所以在完成所有这些步骤之后，rear 现在等于 0 并指向 CircularArrayQueue 的内部数组中的第一个索引。 。当索引到达末尾时“环绕”数组的这种行为是循环行为，它是 CircularArrayQueue 的特征。 .

这与时钟的关系是，时钟上的分针在达到 60 时总是“绕回”，并“重置”回 0。

换句话来说，上面示例中使用的内部数组可以被认为是一个只有 5 分钟的时钟(索引 0 - 4)。您可以将 (rear + 1) 视为时钟前进一分钟。 “分针”(后)增加 4 次后，又从 0 开始。