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 in letzterem Mülldaten im Array haben würden?
Wenn Sie eine bestimmte 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 um 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 Operationen bei einem Update und gibt Ihnen eine bessere Leistung.
Wenn Sie eine Warteschlange mit unbegrenzter / dynamischer Anzahl von Slots erstellen, spielt dies keine Rolle, da Sie den Speicher dynamisch freigeben und zuweisen können.
Ich gebe dir eine Analogie.
Stellen Sie sich eine Schlange beim Straßenverkäufer vor, wo sich Leute am Ende der Linie treffen und von vorne bedient werden. Während jede Person bedient wird, mischen sich die verbleibenden Personen in der Warteschlange vorwärts (normalerweise murmeln sie, wie lange sie dauern), 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 den, der vorne ist oder niemand.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 in der Warteschlange und bewegte sich tatsächlich dorthin, wo der Kopf der Schlange steht. Irgendwann nach dem Servieren von 100 Personen ist der Server auf halbem Weg die Straße runter und nach 500 ist der Server jetzt in der nächsten Straße usw. ... wo hört es auf?
Der Einfachheit halber ordnet der Verkäufer also einen großen Circuit-Bereich zu, in dem die Leute immer am Ende der Schlange stehen 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 Elemente gewartet werden, mischt er Elemente entlang des Puffers. Im zweiten -Beispiel wird das Programm ausgeführt, bis dem Array kein Speicher mehr hinzugefügt werden kann = es hat eine feste Größe (entweder definiert oder begrenzt durch Leerzeichen). Im dritten Beispiel bewegt sich der Server zum Kopf der Warteschlange wie der zweite, aber das Array ist fest und es können nur so viele Elemente der Warteschlange beitreten, aber sie erhalten weiterhin den FIFO Service.
>tl; dr: Effizientes Ressourcenmanagement.
Stellen Sie sich eine Warteschlange vor, die von einem Array unterstützt wird, wobei Index 0 immer der erste Eintrag und 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 viel Zeit für große Warteschlangen und / benötigen. 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.
Circular Array ist nichts anderes als normales 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 gehen kann, müssen wir die Array-Elemente nach oben verschieben.
%Vor%Es ist hauptsächlich eine Frage von 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.
Tags und Links java queue data-structures fifo