为什么将队列实现为循环数组？
当实现像队列这样的FIFO时，我的教师总是建议我们将它表示为圆形数组而不是常规数组。 为什么？
是因为在后者中，我们最终会在arrays中有垃圾数据吗？
如果您使用固定数量的arrays插槽/元素，则更容易以循环方式回收插槽，因为您无需重新排序元素。 每当第一个元素以类似数组的排列方式被移除时，您必须将剩余的元素移动到前面一个位置，因此头部不为null 。 在循环队列中，只需将指针增加到第一个位置即可。 这对更新的操作较少，并为您提供更好的性能。
如果您正在构建具有无限/动态插槽数的队列，这无关紧要，因为您可以动态释放和分配内存。
我会给你一个比喻。
想象一下在街头小贩的队列中，人们在线路末端加入并从前面获得服务。 当每个人都得到服务时，队列中的其余人员会向前推进（通常会嘀咕其服用多长时间），最后新人加入。 在此示例中，人们必须向前移动以使其他人加入该行，否则队列的末尾将始终远离供应商。 因此，在此示例中，服务器停留在队列的前端，并处理前方或任何人的任何人。
现在想象一下，如果人们没有移动，而是在服务队列的头部后，卖家自己沿着队列进一步移动，实际上移动到队列的头部。 最终服务100人之后，服务器就在街道的一半，500之后服务器现在在下一条街道等等……它在哪里停止？
因此，为了方便起见，卖方映射了一个大的电路区域，人们总是可以加入队列的末端，并且他总是移动到下一个人，但队列仍然在一个地方。 他只是为人们服务。 当然，他只能为队列中的人服务，但如果他足够大，那么他就能满足需求，而且他不必离开他指定的销售区域。
将这个类比带回计算机……在第一个例子中，有一个队列管理器，当项目被服务时，它会沿着缓冲区随机播放项目。 在第二个例子中，程序运行，直到没有更多的内存要添加到数组=它的固定大小（由空间定义或限制）。 在第三个例子中，服务器像第二个例子一样移动到队列的头部，但是数组是固定的，只有很多项可以加入队列，但它们仍然会得到服务FIFO。
tl; dr：有效的资源管理。
想象一个由数组支持的队列，其中索引0始终是第一个项目，索引n始终是最后一个。 为了从队列中删除项目，所有项目1到n必须向前移动以将索引1中的内容放入索引0.可以想象，此过程将花费大量时间用于大型队列和/或频繁操作队列。
通过将数组视为循环缓冲区，在删除一个队列时将队列的头部指向下一个项目变得像单个赋值一样简单，这显然更高效。
圆形arrays只是普通的arrays; 只有指针（前/后）到达终点时才会重置到其起始位置。 如果不是这种情况并且只有指针可以向前移动，那么我们需要将数组元素交换到顶部。
import java.lang.reflect.Array; /** * Based on * https://www.youtube.com/watch?v=z3R9-DkVtds * Data Structure & Alogorithm: Queue using Circular Array by Ripon Datta * * 1) When front and rear are equal there is no data. * 2) For each addition rear get incremented to new (empty) position, and for each removal * front get moved right to point to the next available element. * 3) Q Size (N - front + rear) % N :where N is total array size allocated * 4) Resize the array as part of adding new element and founding front and rear are equal * OR size is reached the MAX value. * 5) While resizing add the element from front to rear to the new array. * */ public class QueueUsingCircularArray { T[] array; int front = 0; int rear = 0; int N; Class clazz; public QueueUsingCircularArray(Class clazz, int size) { N = size; this.clazz = clazz; array = (T[]) Array.newInstance(clazz, N); } public int size() { return (N - front + rear) % N; } public void add(T data) { int size = size(); if (size == N - 1) { resize(); } array[rear++] = data; if (rear == N) { rear = 0; } } private void resize() { int size = size(); N = N * 2; T[] newArray = (T[]) Array.newInstance(clazz, N); int i = 0; while (size > 0) { size--; newArray[i++] = array[front++]; if (front == array.length) { front = 0; } } rear = i; front = 0; array = newArray; } public T remove() { if (size() == 0) { return null; } T data = array[front++]; array[front - 1] = null; if (front == N) { front = 0; } return data; } public static void main(String[] args) { QueueUsingCircularArray ca = new QueueUsingCircularArray(Integer.class, 5); ca.add(1); ca.add(2); ca.add(3); ca.remove(); ca.add(4); ca.add(5); ca.add(55); //RESIZE ca.remove(); ca.remove(); ca.add(6); ca.add(7); ca.add(8); ca.add(9); ca.add(10); } }
这主要是表演和简单的问题。 在标准数组中，每次从队列中选择元素时都必须移动所有元素。 使用循环数组，您只需要更新当前指针和大小……效率更高。