循环数组的队列实现

Question

我正在阅读有关 DynaArrayQueue（当没有足够元素时大小加倍的队列）的实现的信息，

我对其中的两种方法有某些疑问。

令容量为队列的容量。

getQueueSize() 方法

public int getQueueSize()
 {
if(front == -1) return 0;

//Here why can't the size by  simply [(rear -front +1) %capacity ]
int size = (capacity - front + rear +1) % capacity;

if(size == 0) return capacity;
else return size;
 }

在计算大小时，为什么我们使用

size = (capacity - front + back +1 ) %capacity ，而不是简单地 (rear - front +1)%容量。 ？

问题2：

resizeQueue()

这是调整队列大小的方法

  private void resizeQueue()
 {
int initCapacity = capacity;
capacity *=2;

int[] oldArray = array;

array = new init[this.capacity];

//this is fine
for(int i=0; i<oldArray.length;i++)
{
    array[i] =oldArray[i];
}

//why do we need this ?
if(rear < front)
{
    for(int i =0 ; i<front ; i++)
    {
        array[i+initCapacity] = this.array[i];
        array[i]= null;

    }

    rear = rear + initCapacity;

}


  }

该方法中的第一个for循环很简单，但是为什么我们需要第二个if循环？。它照顾什么条件？

Answer 1

1. 容量存在的原因是因为

(rear - front) 

可以为负，负模数因语言实现而异。

2.你有第二个循环的原因是因为

在这种情况下

[#####000000####]
     ^      ^
    rear   front

# is array item
0 is empty space

当你复制到一个更大的数组时，你会得到一个不相交的数组

[#####000000####000000000000000]

第二个循环移动

[#####000000####000000000000000]
 ^---^

到

[00000000000#########0000000000]
                ^---^

Answer 2

第二个循环是确保项目以正确的顺序存储在新数组中。想象一个圆形缓冲区，其中前部（您从中获取的位置）大于后部（您添加内容的位置）。因此容量为 50，前端为 40，后端为 10。项目将从队列中按顺序删除：40, 41, 42, 43...0, 1, 2, ... 9。

现在，当您调整大小时队列中的项目以相同的顺序复制到新数组中。但是从现在容量为 100 的队列中删除项目将是 40, 41, 42, ... 49, 50, 51。但是位置 50 处没有任何内容！

因此，这 10 个项目从位置 0 到 9 移动到位置 50 到 59。这就是第二个循环的作用。

Answer 3

不熟悉这个类，但我想如果队列已经绕回，以便在数组的开头写入新项目，那么“后”可能小于“前”。这回答了你的两个问题，因为在这种情况下，(rear - front +1) %capacity将为负数，这不是你想要的（Q1），也是队列必须移植到容量增加的末尾（Q2）。