为什么执行队列为圆阵？(Why implement Queues as Circular Array

当实现像队列先进先出，我的老师总是提醒我们它表示为一个圆形阵列，而不是在规则阵列。为什么？

难道是因为在后者，我们最终会在阵列中有垃圾数据？

Answer 1:

如果您使用的是阵列的插槽/片固定数量，更容易回收的圆形布置的插槽，因为你并不需要重新排列元素。每当第一数组中的元素状排列被删除，你必须将你的其余元素一个位置前面，所以个头不null 。在你的循环队列，你只是增加你的指针到第一位置。这是上一个更新的操作较少，给你一个更好的性能。

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

Answer 2:

我给你打个比方。

想象一下，在摆地摊队列里的人在该行的末尾加入，并从前方服务。由于每个人送达，在队列洗牌转发其余的人（通常嘟囔多久其采取），和新人们在最后加入。在这个例子中人们不得不向前移动，以使他人加入行，否则队列的末尾将总是远离厂商获得。因此，在这个例子中，服务器停留在队列的前面，与谁在前面或无人涉及。

如果人们没有移动，但服务于队列的头后，而不是由卖方自行沿着队列进一步移动时，实际上移动到队列的头是现在想象。服务100人后，最终的服务器是中途在街上和500后，服务器现在是在一条街等等它在哪里停下来？

所以为了方便卖家映射大面积circuital，人们可以随时加入队列的末尾，他总是移动到下一人，但队列保持在一个地方。他只是去圆为人民服务的队列。当然他也只会在队列中的人，但前提是他使得它足够大，那么他就可以跟上需求，他没有从他的指定销售区域移开。

以这个比喻回电脑......在第一个例子中有一个队列管理器和为项目提供服务它慢腾腾沿缓冲项目。在第二示例中的程序运行，直到没有更多的内存添加到数组=它的固定大小（通过空间限定或限制）。在第三个例子中，服务器移动到像第二队列的头，但该阵列是固定的，只有这么多的项目可以加入队列，但他们仍然会得到服务FIFO。

TL;博士：资源的有效管理。

Answer 3:

想象这是由一个阵列，其中索引0始终是第一项和索引支持的队列n总是最后。为了从队列中删除一个项目，然后到n的所有项目1必须前移放置什么在索引1到索引0正如你可以想像，这个过程需要花费相当长的时间，大队列和/在队列或频繁操作。

通过处理该阵列作为循环缓冲器，指向队列的头部，以当一个被移除的下一个项目变成为单个分配，这显然是更高性能的那样简单。

Answer 4:

圆形阵列不过是正常阵列; 只有当它到达末端的指针（前/后）将复位到其起始位置。如果是这种情况并非如此，只有指针可以向前移动，然后我们需要交换数组元素的顶端。

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);
    }
}