Warum Warteschlangen als kreisförmiges Array implementieren?

Question

Wenn ich einen FIFO wie Warteschlangen implementiere, rät mir mein Lehrer immer, es als eine kreisförmige Anordnung und nicht in einer regelmäßigen Anordnung darzustellen. Warum?

Liegt es daran, dass wir im letzten Fall Mülldaten im Array hätten?

Answer 1

Wenn Sie eine feste Anzahl von Array-Slots/Elementen verwenden, ist es einfacher, Ihre Slots in einer kreisförmigen Anordnung zu recyceln, da Sie Ihre Elemente nicht neu anordnen müssen. Immer wenn das erste Element in einer Array-ähnlichen Anordnung entfernt wird, müssen Sie Ihre verbleibenden Elemente eine Position nach vorne verschieben, sodass der Kopf nicht null ist. In Ihrer kreisförmigen Warteschlange erhöhen Sie einfach Ihren Zeiger auf die erste Position. Das sind weniger Vorgänge bei einem Update und Ihnen eine bessere Leistung.

Wenn Sie eine Warteschlange mit unbegrenzter/dynamischer Anzahl von Steckplätzen erstellen, spielt dies keine Rolle, da Sie den Speicher dynamisch freigeben und zuweisen können.

Answer 2

Stellen Sie sich eine Warteschlange vor, die von einem Array unterstützt wird, wobei Index 0 immer das erste Element ist und der Index n immer der letzte ist. Um ein Element aus der Warteschlange zu entfernen, müssen alle Elemente 1 bis n nach vorne verschoben werden, um das, was in Index 1 war, in Index 0 zu platzieren. Wie Sie sich vorstellen können, würde dieser Prozess bei großen Warteschlangen viel Zeit in Anspruch nehmen. oder häufige Operationen in der Warteschlange.

Wenn Sie das Array als Ringpuffer behandeln, wird der Kopf der Warteschlange beim Entfernen auf das nächste Element so einfach wie eine einzelne Zuweisung, die offensichtlich viel leistungsfähiger ist.

Answer 3

Es ist hauptsächlich eine Frage der Leistung und Einfachheit. In einem Standard-Array müssten Sie alle Elemente jedes Mal verschieben, wenn Sie ein Element aus der Warteschlange auswählen. Bei kreisförmigen Arrays müssen Sie nur den aktuellen Zeiger und die aktuelle Größe aktualisieren ... viel effizienter.

Answer 4

Ich gebe dir eine Analogie.

Stellen Sie sich eine Schlange am Straßenverkäufer vor, wo sich Leute am Ende der Linie treffen und von vorne bedient werden. Während jede Person bedient wird, schlurfen die verbleibenden Personen in der Warteschlange vorwärts (üblicherweise murmelnd, wie lange sie dauert), und am Ende kommen neue Leute hinzu. In diesem Beispiel müssen Benutzer sich vorwärts bewegen, um anderen zu ermöglichen, sich der Linie anzuschließen, andernfalls würde sich das Ende der Warteschlange immer weiter von dem Verkäufer entfernen. In diesem Beispiel bleibt der Server also an der Spitze der Warteschlange und kümmert sich um diejenigen, die an der Front oder an niemandem stehen.

Stellen Sie sich nun vor, die Leute hätten sich nicht bewegt, aber nachdem sie den Kopf der Warteschlange bedient hatten, bewegte sich der Verkäufer selbst weiter entlang der Warteschlange, um sich dorthin zu bewegen, wo der Kopf der Warteschlange ist. Irgendwann nach dem Servieren von 100 Leuten ist der Server auf halber Höhe der Straße und nach 500 ist der Server jetzt in der nächsten Straße usw. ... wo hört es auf?

Aus praktischen Gründen bildet der Verkäufer einen großen Circuit-Bereich ab, in dem sich die Leute immer am Ende der Schlange anmelden können und er immer zur nächsten Person geht, aber die Schlange bleibt an einem Ort. Er geht nur durch die Schlange, die den Leuten dient. Sicher, er kann nur den Leuten in der Schlange dienen, aber vorausgesetzt, er macht es groß genug, dann kann er mit der Nachfrage Schritt halten, und er muss nicht von seinem zugewiesenen Verkaufsbereich weggehen.

Nehmen wir diese Analogie zurück zu Computern ... im ersten Beispiel gibt es einen Warteschlangenmanager und wenn Artikel gewartet werden, mischt es Elemente entlang des Puffers. Im zweiten Beispiel wird das Programm ausgeführt, bis kein weiterer Speicher zum Array hinzugefügt werden kann = es hat eine feste Größe (entweder definiert oder begrenzt durch Leerzeichen).In dem Beispiel bewegt sich der Server zum Kopf der Warteschlange wie der zweite, aber das Array ist fest und nur so viele Elemente können der Warteschlange beitreten, aber sie erhalten weiterhin einen FIFO-Service.

tl; dr: Effizientes Management von Ressourcen.

Answer 5

Circular Array ist nichts anderes als normale Array; nur der Zeiger (vorne/hinten) wird auf die Startposition zurückgesetzt, wenn er das Ende erreicht. Wenn dies nicht der Fall ist und nur der Zeiger vorwärts bewegt werden kann, müssen die Array-Elemente nach oben getauscht werden.

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