11

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

是因为在后者中，我们最终会在数组中拥有垃圾数据吗？

4

5 回答 5

9

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

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

于 2012-10-05T23:11:14.150 回答
7

我给你打个比方。

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

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

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

将此类比回计算机……在第一个示例中，有一个队列管理器，并且在为项目提供服务时，它沿缓冲区对项目进行洗牌。在第二个示例中，程序运行直到没有更多的内存可以添加到数组中 = 它的大小是固定的（由空间定义或限制）。在第三个示例中，服务器像第二个示例一样移动到队列的头部，但数组是固定的，只有这么多的项目可以加入队列，但它们仍将获得服务 FIFO。

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

于 2012-10-05T23:24:35.963 回答
3

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

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

于 2012-10-05T23:18:06.873 回答
2

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

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);
    }
}
于 2016-04-23T06:10:44.727 回答
1

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

于 2012-10-05T23:18:26.673 回答