Java 中的循环队列实现

Question

我正在阅读我在 Github 中偶然发现的队列实现，并且很难理解为什么使用某些行为。（可以找到存储库的 link here）

代码将用户期望声明队列大小的初始容量加 1。所有者解释说这是因为初始最大大小为 data.length - 1，但没有解释原因。这是代码的那一部分：

public ArrayQueue(int capacity) {
  // ArrayQueue maximum size is data.length - 1.
  data = new Object[capacity + 1];
  front = 0;
  rear = 0;
}

我不确定为什么在项目已经插入队列后在报价函数中调整后索引，而在轮询中调整头部索引。有区别吗？

public void offer(T elem) {
    if (isFull()) {
      throw new RuntimeException("Queue is full");
    }
    data[rear++] = elem;
    rear = adjustIndex(rear, data.length);
 }

public T poll() {
    if (isEmpty()) {
      throw new RuntimeException("Queue is empty");
    }
    front = adjustIndex(front, data.length);
    return (T) data[front++];
}

为什么我们需要在(front - rear)中添加data.length来检查列表是否已满？

  public boolean isFull() {
    return (front + data.length - rear) % data.length == 1;
  }

谢谢

Answer 1

他上面已经提到了

ArrayQueue maximum size is data.length - 1. The place of the variable rear is always in front of the variable front logistically if regard the data array as circular. so the number of states of the combination of rear and front is the length of the data array. And one of the total states is used to be the judge if the queue is empty or full.

read 调整后，因为 rear 是应该添加新元素的地方。添加元素后，它会递增。 front 是应该弹出元素的索引，因为它已经有元素了。
请记住，项目的最大数量是 data.length - 1，因此如果队列应该已满，front - rear 必须等于 1。

我希望这能回答您的问题。欢迎在评论中提问。

Java 中的循环队列实现

Circular Queue Implementation in Java

java

algorithm

queue