Why implement Queues as Circular Array?

Question

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?

Solution 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.

Solution 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.

Solution 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.

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

Solution 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.

View more solutions

Comments

[Keith Randall]

I think even with unlimited slots it is still useful to reuse the ones you have in a circular manner.

[Simulant]

In a unlimited scenario, I would free the memory on a get() and alocate new memory on an add(). So i reuse the slots but not i a fixed order.

[Tim Bender]

I think Simulant is referring to a Queue backed by a dynamic data structure like a LinkedList. In those cases, it makes no sense to "reuse slots" because there are no slots, just "holder links" which can be cheaply created and discarded. Actually, generally speaking, trying to excessively reuse cheaply constructed objects can lead to performance problems by allowing objects to migrate into a classification of heap space where they do not belong.

[Sobiaholic]

Just more than I asked for. Too many excellent answers. Really hard to choose from. Thanks Sir!

[committedandroider]

Why do you have to shift everything to the left?

[Dev_Man]

This really helped me understand the real use as well. +1