java 为什么将队列实现为循环数组？

Why implement Queues as Circular Array?

提问by Sobiaholic

When implementing a FIFO like Queues, my instructor always advise us to represent it as a circular array and not in a regular array. Why?

在实现像队列这样的 FIFO 时，我的导师总是建议我们将其表示为圆形数组而不是常规数组。为什么？

Is it because in the latter, we would end up having garbage data in the array?

是不是因为在后者中，我们最终会在数组中包含垃圾数据？

采纳答案by Simulant

If your are using a fixed number of Array-Slots/Elements, it is easier to recycle your slots in a circular arrangement, because you do not need to reorder your Elements. Whenever the first Element gets removed in an Array-Like arrangement, you must move your remaining Elements one position to the front, so the head is not null. In your circular Queue, you just increase your pointer to the first Position. That are less operations on an update and gives you a better performance.

如果您使用固定数量的阵列插槽/元素，则以圆形排列回收插槽会更容易，因为您不需要重新排序元素。每当第一个 Element 在 Array-Like 排列中被移除时，您必须将剩余的 Elements 移动一个位置到前面，因此头部不是null。在您的循环队列中，您只需将指针增加到第一个位置。这减少了更新操作，并为您提供更好的性能。

If your are constructing a Queue with unlimited/dynamic number of slots this does not matter, because you can free and allocate the memory dynamically.

如果您正在构建一个具有无限/动态数量插槽的队列，这无关紧要，因为您可以动态地释放和分配内存。

回答by Preet Sangha

I'll give you an analogy.

我给你打个比方。

Imagine a queue at street vendor where people join at the end of the line and get served from the front. As each person is served, the remaining people in the queue shuffle forwards (usually muttering about how long its taking), and new people join at the end. In this example people have to move forwards to enable others to join the line, otherwise the end of the queue would always be getting further away from the vendor. So in this example the server stays at the front of the queue and deals with whoever is at the front or no one.

想象一下街头小贩的队列，人们在队伍的末端加入并从前面获得服务。当每个人都得到服务时，队列中剩余的人会向前移动（通常会嘟囔着需要多长时间），最后有新人加入。在这个例子中，人们必须向前移动才能让其他人加入队伍，否则队列的末端总是离供应商越来越远。所以在这个例子中，服务器停留在队列的前面，并处理任何在前面或没有人的人。

Now imagine if the people didn't move but instead after serving the head of the queue the seller themselves moved further along the queue, in effect move to where the head of the queue is. Eventually after serving 100 people the server is halfway down the street and after 500 the server is now in the next street etc... where does it stop?

现在想象一下，如果人们没有移动，而是在为队列的头部服务后，卖方自己沿着队列进一步移动，实际上移动到队列头部的位置。最终在为 100 人服务后，服务器在街道的一半，500 人之后，服务器现在在下一条街等等......它在哪里停止？

So for convenience the seller maps a large circuital area where people can always join the end of the queue and he always moves to the next person, but the queue remains in one place. He just goes round the queue serving people. Sure he can only serve the people in the queue, but provided he makes it big enough then he can keep up with demand, and he doesn't have to move away from his designated sales area.

因此，为方便起见，卖家绘制了一个大的环形区域，人们总是可以在该区域加入队列的末尾，并且他总是移动到下一个人，但队列保持在一个地方。他只是绕着队列为人们服务。当然他只能为排队的人服务，但只要他做得足够大，他就可以跟上需求，而且他不必离开他指定的销售区域。

Taking this analogy back to computers... in the firstexample there is a queue manager and as items are serviced it shuffles items along the buffer. In the secondexample the program runs until there is no more memory to add to the array = it's fixed size (either defined or limited by space). In the thirdexample the the server moves to the head of the queue like the second but the array is fixed and only so many items can join the queue, but they will still get serviced FIFO.

把这个比喻回到计算机......在第一个例子中，有一个队列管理器，当项目被服务时，它会沿着缓冲区对项目进行洗牌。在第二个例子中，程序运行直到没有更多的内存可以添加到数组中=它是固定大小（定义或受空间限制）。在第三个例子中，服务器像第二个例子一样移动到队列的头部，但数组是固定的，只有这么多项目可以加入队列，但它们仍然会得到服务 FIFO。

tl;dr: Efficient management of resources.

tl;dr：资源的有效管理。

回答by Tim Bender

Imagine a Queue which is backed by an array where index 0 is always the first item and index nis always the last. In order to remove an item from the Queue, then all items 1 to n must be shifted forward to place what was in index 1 into index 0. As you can imagine, this process would take a considerable amount of time for large queues and/or frequent operations on the queue.

想象一个由数组支持的队列，其中索引 0 始终是第一项，索引n始终是最后一项。为了从队列中删除一个项目，必须将所有项目 1 到 n 向前移动以将索引 1 中的内容放入索引 0。正如您想象的那样，对于大队列和/，此过程将花费大量时间或频繁的队列操作。

By treating the array as a circular buffer, pointing the head of the queue to the next item when one is removed becomes as simple as a single assignment, which is obviously much more performant.

通过将数组视为循环缓冲区，在删除一项时将队列的头部指向下一项变得像单个赋值一样简单，这显然性能更高。

回答by Kanagavelu Sugumar

Circular Array is nothing but normal array; only the pointer (front/rear) will be reset to its start position when it reaches the end. If this is not the case and only pointer can moves forward then we need to swap the array elements to the top.

圆形数组不过是普通数组；只有指针（前/后）到达终点时才会重置到其起始位置。如果不是这种情况并且只有指针可以向前移动，那么我们需要将数组元素交换到顶部。

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> {
    T[] array;
    int front = 0;
    int rear = 0;
    int N;
    Class<T> clazz;

    public QueueUsingCircularArray(Class<T> 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);
    }
}

回答by Mario

It's a mainly a matter of performances and simplicity. In a standard array you would have to shift all the elements every time you pick an element from the queue. With circular arrays, you just need to update the current pointer and size...far more efficient.

这主要是性能和简单性的问题。在标准数组中，每次从队列中选取一个元素时，您都必须移动所有元素。使用圆形数组，您只需要更新当前指针和大小……效率更高。