Why implement Queues as Circular Array?

问题:

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?

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

回答1:

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.

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.

回答2:

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?

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 first example there is a queue manager and as items are serviced it shuffles items along the buffer. In the second example 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 third example 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.

tl;dr: Efficient management of resources.

回答3:

Imagine a Queue which is backed by an array where index 0 is always the first item and index n is 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.

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.

回答4:

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

回答5:

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.