Why do queues like a Circular Array?

Question

When implementing FIFO, such as Queues, my instructor always advises us to represent it as a round array, and not in a regular array. What for?

Is it because in the latter case we get garbage data in an array?

Answer 1

If you use a fixed amount of Array-Slots / Elements, it’s easier for you to recycle slots in a circular form because you don’t have to reorder the elements. Whenever the first element is removed in Array-Like, you have to move the remaining elements one position forward, so the head is not null . In your circular queue, you simply increase the pointer to the first position. It has fewer update operations and gives you better performance.

If you create a queue with an unlimited / dynamic number of slots, it does not matter, because you can freely and allocate memory dynamically.

Answer 2

I will give you an analogy.

Imagine a line at a street vendor where people join the end of the line and receive service from the front. When each person is served, the remaining people in the line are shuffled forward (usually muttering about how long they take him), and new people join in at the end. In this example, people have to move forward so that others can join this line, otherwise the end of the queue will always move away from the provider. Thus, in this example, the server remains at the front of the queue and deals with who is at the front or no one.

Now imagine that people did not move, but instead of serving the head of the line, the seller himself moved further in turn, actually moving to where the head of the line is. After all, after serving 100 people, the server is halfway down the street, and after 500 the server is now on the next street, etc .... where does it stop?

Thus, for convenience, the seller compares a large closed area where people can always join the end of the line, and he always moves on to the next person, but the line remains in one place. He simply bypasses the line, serving people. Of course, he can only serve people in line, but provided that he makes it big enough, and he can keep up with demand, and he does not need to move away from his designated trading zone.

Taking this analogy back to computers ... in the first example there is a queue manager, and as items are serviced, it moves items along the buffer. In the second example, the program runs until more memory is added to add the array = fixed size (defined or limited by a space). In the third example, the server moves to the main queue of the queue, like the second, but the array is fixed, and only the number of elements can join the queue, but they will still be served by FIFO.

tl; dr: efficient resource management.

Answer 3

Imagine a queue that is supported by an array, where index 0 is always the first element and index n always the last. To remove an item from the queue, all items 1 through n must be pushed forward to place what was in index 1 at index 0. As you can imagine, for large queues this process will take considerable time and / or frequent operations queue.

Referring to the array as a circular buffer, pointing the queue head to the next element upon removal becomes as simple as a single assignment, which is obviously much more efficient.

Answer 4

Circular Array is nothing more than a regular array; only the pointer (front / rear) will be reset to its original position when it reaches the end. If this is not the case, and only the pointer can move forward, then we need to swap the elements of the array 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); } } 

Answer 5

This is mainly a matter of performance and simplicity. In a standard array, you will have to move all the elements every time you select an element from the queue. With circular arrays, you just need to update the current pointer and size ... much more efficiently.