Perché implementare le code come array circolare?

Question

Quando si implementa una coda FIFO, il mio istruttore ci consiglia sempre di rappresentarlo come una matrice circolare e non in una matrice normale. Perché?

È perché in quest'ultimo, avremmo finito con i dati inutili nell'array?

Answer 1

Se si utilizza un numero fisso di Array-Slot/Elementi, è più facile riciclare gli slot in una disposizione circolare, poiché non è necessario riordinare gli elementi. Ogni volta che il primo elemento viene rimosso in una disposizione Array-Like, è necessario spostare gli elementi rimanenti di una posizione in avanti, quindi la testa non è null. Nella tua coda circolare, puoi semplicemente aumentare il puntatore alla prima posizione. Si tratta di meno operazioni su un aggiornamento e offre prestazioni migliori.

Se si sta costruendo una coda con numero illimitato/dinamico di slot questo non ha importanza, perché è possibile liberare e allocare la memoria in modo dinamico.

Answer 2

Immaginate una coda supportata da un array in cui l'indice 0 è sempre il primo elemento e l'indice n è sempre l'ultimo. Per rimuovere un articolo dalla coda, tutti gli elementi da 1 a n devono essere spostati in avanti per posizionare l'indice 1 nell'indice 0. Come puoi immaginare, questo processo richiederebbe molto tempo per le code di grandi dimensioni e/o frequenti operazioni in coda.

Trattando l'array come un buffer circolare, puntando la testa della coda sull'elemento successivo quando uno viene rimosso diventa semplice come un singolo compito, che è ovviamente molto più performante.

Answer 3

È principalmente una questione di prestazioni e semplicità. In un array standard dovresti spostare tutti gli elementi ogni volta che scegli un elemento dalla coda. Con gli array circolari, è sufficiente aggiornare il puntatore e le dimensioni attuali ... molto più efficiente.

Answer 4

Ti darò un'analogia.

Immaginate una coda al venditore ambulante dove le persone si uniscono alla fine della fila e vengono servite dal fronte. Man mano che ogni persona viene servita, le persone rimanenti nella coda si spostano in avanti (di solito borbottano per quanto tempo sta prendendo) e alla fine si uniscono nuove persone. In questo esempio le persone devono spostarsi in avanti per consentire ad altre persone di unirsi alla linea, altrimenti la fine della coda si allontanerebbe sempre di più dal venditore. Quindi in questo esempio il server rimane in prima fila e si occupa di chiunque sia davanti o di nessuno.

Ora immagina se le persone non si muovono ma invece dopo aver servito il capo della coda il venditore si è spostato ulteriormente lungo la coda, spostandosi in effetti verso il punto in cui si trova il capo della coda. Alla fine, dopo aver servito 100 persone, il server è a metà strada e dopo il 500 il server si trova ora nella strada successiva ecc. Dove si ferma?

Quindi per comodità il venditore mappa una vasta area circuitale dove le persone possono sempre unirsi alla fine della coda e si sposta sempre verso la persona successiva, ma la coda rimane in un posto. Fa semplicemente la fila per servire le persone. Certo, può solo servire le persone in coda, ma a condizione di renderlo abbastanza grande da poter tenere il passo con la domanda, e non deve allontanarsi dalla sua area di vendita designata.

Riportare questa analogia ai computer ... nel prima esempio c'è un gestore code e man mano che gli articoli vengono revisionati rimescola gli elementi lungo il buffer. Nell'esempio secondo, il programma viene eseguito finché non vi è più memoria da aggiungere all'array = la sua dimensione fissa (definita o limitata dallo spazio).Nell'esempio terzo, il server si sposta in testa alla coda come il secondo, ma l'array è fisso e solo così tanti elementi possono unirsi alla coda, ma riceveranno comunque FIFO assistito.

tl; dr: Gestione efficiente delle risorse.

Answer 5

L'array circolare non è altro che una matrice normale; solo il puntatore (anteriore/posteriore) verrà riportato alla posizione iniziale quando raggiunge la fine. Se questo non è il caso e solo il puntatore può andare avanti, allora abbiamo bisogno di scambiare gli elementi dell'array in alto.

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