Implementierungsprinzip der Java -Warteschlange
Das Wort "Warteschlange" nennt der britische "Warteschlangen". "Decke in Linie" in Großbritannien bedeutet, in einer Reihe zu stehen. In der Informatik ist eine Warteschlange eine Datenstruktur, die ein bisschen wie ein Stapel ähnelt, außer dass das erste in der Warteschlange eingefügte Datenelement zuerst entfernt wird und im Stapel das letzte eingefügte Datenelement zuerst entfernt wird. Die Warteschlange wirkt wie die Reihen von Menschen, die vor dem Kino stehen: Die erste Person, die in die angeschlossene Eintritts geht, wird an der Spitze des Teams kommen, um Tickets zu kaufen. Die letzte Person, die sich anstellt, kann Tickets kaufen.
Warteschlangen werden auch als Tools für Programmierer wie Stapel verwendet. Es kann auch verwendet werden, um reale Umgebungen zu simulieren, z. B. die Simulation von Personen, die in einer Bank warten, Flugzeuge, die darauf warten, abzuheben, oder Pakete im Internet darauf warten, übertragen zu werden.
Im Computerbetriebssystem arbeiten verschiedene Warteschlangen leise. Der Druckauftrag wartet auf den Druck in der Druckwarteschlange. Beim Eingeben auf der Tastatur gibt es auch eine Warteschlange, in der die Eingabe gespeichert wird. Wenn ein Schlüssel mit einem Textverarbeitungsprogramm und dem Computer vorübergehend etwas anderes erledigt wird, geht der abgebildete Inhalt nicht verloren und wartet in der Warteschlange, bis der Wortprozessor Zeit hat, ihn zu lesen. Die Warteschlange wird verwendet, um sicherzustellen, dass die Reihenfolge der Tippierung bei der Verarbeitung nicht geändert wird.
Grundlegende Operationen von Warteschlangen
Die beiden grundlegenden Vorgänge einer Warteschlange geben (Einfügen) eines Datenelements, dh ein Datenelement in den Schwanz der Warteschlange, und das andere entfernen (entfernen) ein Datenelement, dh das Entfernen des Datenelements am Kopf des Teams. Dies ähnelt dem Anstehen von Filmliebhabern bis zum Ende der Linie, wenn sie sich anstellen, um Tickets zu kaufen, dann an der Spitze der Linie zu kommen und dann die Warteschlange zu verlassen.
Die Benennung von Methoden zum Einsetzen und Entfernen von Datenelementen in den Stapel ist sehr Standard, Push and Pop. Die Warteschlangenmethode wurde bisher nicht standardisiert. "Insert" kann als Put, Add oder Enque bezeichnet werden, während "Löschen" als Löschen, Get oder Deque bezeichnet werden kann. Das Ende des Insertionsdatenelements kann auch zurück, den Schwanz oder das Ende gerufen werden. Der Leiter des Teams, der das Datenelement entfernt, kann auch als Kopf bezeichnet werden. Einsetzen, entfernen, vorne und hinten werden unten verwendet.
Fügen Sie den Wert in den Schwanz der Warteschlange ein, und der Schwanz des Warteschlangenpfeiles wird hinzugefügt, um auf das neue Datenelement zu verweisen.
Nachdem der Datenelement entfernt wurde, wird der Team des Teams von einem hinzugefügt. Normalerweise wird bei der Implementierung einer Warteschlange das gelöschte Datenelement im Speicher gespeichert, kann jedoch nicht zugegriffen werden, da auf den Kopf der Warteschlange in die nächste Position verschoben wurde.
Im Gegensatz zum Fall im Stapel beginnen Datenelemente in der Warteschlange nicht immer am 0 -Index des Arrays. Nach dem Entfernen einiger Datenelemente verweist der Header -Zeiger auf eine höhere Indexposition.
Der Ansichtsvorgang gibt den Wert des Header -Datenelements zurück, löscht das Datenelement jedoch nicht aus dem Team.
Wenn Sie ein Datenelement aus einer leeren Warteschlange entfernen oder ein Datenelement in eine vollständige Warteschlange einfügen möchten, fordert die Anwendung eine Fehlermeldung auf.
Schleifenwarteschlange
Wenn ein neues Datenelement in die Warteschlange eingefügt wird, bewegt sich der hintere Pfeil am Kopf des Teams nach oben in Richtung der großen Position des Array -Index. Beim Entfernen von Datenelementen bewegt sich auch der Schwanz des Frontzeigers der Warteschlange nach oben. Dieses Design kann der direkten Beobachtung der Menschen widersprechen, denn wenn sich die Leute für Kinokarten anstellen, bewegt sich die Warteschlange immer vorwärts, und nachdem die Person vor ihnen das Ticket kauft und die Warteschlange verlässt, gehen die anderen vorwärts. Nachdem Sie ein Datenelement in der Warteschlange im Computer gelöscht haben, können Sie auch alle anderen Datenelemente weiter verschieben, dies ist jedoch sehr effizient. Stattdessen halten wir alle Datenelemente durch die Bewegung der Kopf- und Schwanzzeiger der Warteschlange in der Position.
Das Problem bei diesem Design ist, dass der Schwanzzeiger schnell bis zum Ende des Arrays wechselt. Obwohl sich zu Beginn des Arrays eine leere Datenelementeinheit befindet, nämlich die Position des entfernten Datenelements, aber da sich der Heckzeiger nicht mehr rückwärts bewegen kann, können neue Datenelemente nicht eingefügt werden. Was soll ich tun?
Abwicklungsbehandlung
Um das Problem zu vermeiden, dass die Warteschlange unzufrieden ist, aber nicht in der Lage ist, neue Datenelemente einzufügen, können die Kopf- und Schwanzzeiger auf den Beginn des Arrays zurückgepackt werden. Dies ist die Schleifenwarteschlange (manchmal auch als "Pufferring" bezeichnet).
Der Prozess des Zeigerwechsels: Fügen Sie genügend Datenelemente in die Warteschlange ein, damit der Heckzeiger bis zum späten Ende des Arrays hinweist. Löschen Sie einige weitere Datenelemente am vorderen Ende des Arrays. Fügen Sie nun ein neues Datenelement ein. Sie werden sehen, dass der Schwanzzeiger vom Ende zur Ausgangsposition umgekehrt wird. Neue Datenelemente werden in diesen Ort eingefügt.
Fügen Sie weitere Datenelemente ein. Der Schwanzzeiger bewegt sich wie erwartet nach oben. Beachten Sie, dass nach dem Rückspulen des Schwanzzeigers er sich jetzt unter dem Kopfzeiger befindet, der die Anfangsposition umkehrt. Dies kann als "kaputte Sequenz" bezeichnet werden: Die Datenelemente in der Warteschlange sind in zwei verschiedenen Sequenzen im Array vorhanden.
Nachdem er genügend Datenelemente gelöscht hat, wickelt sich der Team auch darum. Zu diesem Zeitpunkt kehrt der Warteschlangenzeiger zur ersten Laufzeit zum Positionszustand zurück, und der Kopfzeiger befindet sich unter dem Heckzeiger. Die Datenelemente werden auch in eine einzelne kontinuierliche Sequenz wiederhergestellt.
Java -Code für Warteschlangen
Das Programm "Queue.java" erstellt eine Warteschlangenklasse, die die Methoden Insert (), REMED (), Peek (), Isempty () und Size () hat.
Paketstapel und Warteschlange;
Klasse Warteschlange {private int maxSize; Privat lang [] Quearray; private int vorne; privat int hinten; private int nitems; public queue (int s) {maxSize = s; quearray = new Long [maxSize]; vorne = 0; rücken = -1; nitems = 0; } public void Insert (lang j) {if (ard == maxSize-1) rard = -1; Quearray [++ hinten] = j; Nitems ++; } public long remove () {long temp = quearray [vorne ++]; if (vorne == maxSize) vorne = 0; Nitems--; Temperatur zurückgeben; } public Long peekfront () {return quearray [vorne]; } public boolean isempty () {return (nitems == 0); } public boolean iffull () {return (nitems == maxSize); } public int size () {return nitems; }}Die vom Programm implementierte Warteschlangenklasse hat nicht nur die Felder vorne (Kopf) und hinteren (Leiter des Teams), sondern auch die Anzahl der aktuellen Datenelemente in der Warteschlange: Nitems.
Die Voraussetzung für den Betrieb der Insert () -Methode ist, dass die Warteschlange nicht zufrieden ist. Diese Methode wird in main () nicht angezeigt, aber die Insert () -Methode sollte normalerweise zuerst aufgerufen werden, und dann sollte die Methode isful () nach Rückgabe falsch aufgerufen werden. (Ein allgemeinerer Ansatz besteht darin, der Methode Insert () ein Urteilsvermögen hinzuzufügen, um zu prüfen, ob die Warteschlange voll ist. Wenn ein Datenelement in die vollständige Warteschlange eingefügt wird, wird eine Ausnahme geworfen.)
Im Allgemeinen besteht der Insertionsvorgang darin, einen Heck (Team -Schwanzzeiger) hinzuzufügen und neue Daten an der vom Heckzeiger gerichteten Position einzulegen. Wenn der hintere Zeiger jedoch auf die Oberseite des Arrays zeigt, d. H. Die maxsize-1-Position, muss er vor dem Einfügen des Datenelements wieder auf den Boden des Arrays gewickelt werden. Der Wickelvorgang setzt das Heck auf -1. Wenn das Heck 1 hinzugefügt wird, ist es gleich 0, was der Indexwert am unteren Rand des Arrays ist und schließlich ein Nitem hinzugefügt wird.
Die Voraussetzung für den Betrieb der REME () -Methode ist, dass die Warteschlange nicht leer ist. Bevor Sie diese Methode aufrufen, sollten Sie die Methode isEmpty () aufrufen, um sicherzustellen, dass die Warteschlange nicht leer ist, oder diesen Fehlerprüfungsmechanismus zur Methode von REME () hinzufügen.
Der Betrieb von Entfernen erhält immer den Wert des Header -Datenelements vom vorderen Zeiger und fügt dann die vordere Fühe hinzu. Wenn Sie dies jedoch tun, dass der Wert der Front die Oberseite des Arrays überschreitet, muss die Front zu der Position zurückkehren, in der das Einweis des Arrays 0 beträgt. Während dieses Tests wird der Rückgabewert vorübergehend gespeichert. Schließlich wird Nitem um eins reduziert.
Die Peek () -Methode ist einfach und leicht zu verstehen: Es gibt den Wert des vom vorderen Zeiger gezeigten Datenelements zurück. Einige Warteschlangenimplementierungen ermöglichen auch das Anzeigen des Werts des Warteschlangen-End-Datenelements. Beispielsweise können diese Methoden Peekfront (), Peekrear () oder Just Front () und Heck () bezeichnet werden.
Die Implementierung von IsEmpty (), isfifl () und size () -Methoden beruhen alle auf das Feld Nitems, das zurückgibt, ob Nitems gleich 0 sind, unabhängig davon, ob sie Maxsize gleich ist oder ihren eigenen Wert zurückgibt.
Das Einbeziehen von Datenzählungsfeldern in der Warteschlangenklasse fügt den Methoden Insert () und REME () und REME () und die Methoden Insert () und REME () einen kleinen zusätzlichen Betrieb hinzu, und die Wert dieser Variablen müssen erhöht und verringern. Dies ist möglicherweise kein zusätzlicher Overhead, aber wenn Sie sich mit vielen Einfügen und Entfernen von Vorgängen befassen, kann dies die Leistung beeinflussen.
Da einige Warteschlangenimplementierungen nicht die Felder der Datenelementzählen verwenden, vorne und hinten berechnen, ob die Warteschlange leer oder voll ist und die Anzahl der Datenelemente. Wenn Sie dies tun, sind die Routinen isEmpty (), iffull () und size () ziemlich kompliziert, da die Abfolge der Datenelemente, wie bereits erwähnt, entweder in zwei Segmente oder ein kontinuierliches Segment zusammengefasst wird.
Und ein seltsames Problem trat auf. Wenn die Warteschlange voll ist, nehmen die vorderen und hinteren Zeiger eine bestimmte Position ein, aber wenn die Warteschlange leer ist, kann auch die gleiche Positionsbeziehung auftreten. Gleichzeitig scheint die Warteschlange voll oder leer zu sein. Die Lösung für dieses Problem ist: Machen Sie die Array -Kapazität mehr als die maximale Anzahl von Warteschlangendatenelementen.
Danke fürs Lesen, ich hoffe, es kann Ihnen helfen. Vielen Dank für Ihre Unterstützung für diese Seite!