Welche Datenstruktur hat eine Warteschlange?

Queue ist eine lineare Datenstruktur. Die Warteschlange erlaubt nur Löschoperationen am vorderen Ende der Tabelle, während Einfügungsoperationen am hinteren Ende der Tabelle ausgeführt werden. Wie der Stapel ist die Warteschlange eine lineare Tabelle mit eingeschränkten Operationen Das Ende der Warteschlange wird als Ende der Warteschlange bezeichnet, und der Löschvorgang wird ausgeführt. Das Ende wird als Kopf des Teams bezeichnet.

Die Betriebsumgebung dieses Artikels: Windows 10-System, Thinkpad T480-Computer.

Queue ist eine lineare Datenstruktur.

Queue ist eine spezielle lineare Tabelle, die nur Löschvorgänge am vorderen Ende der Tabelle und Einfügevorgänge am hinteren Ende der Tabelle zulässt ist eine Operation für eingeschränkte lineare Tabellen. Das Ende, das den Einfügevorgang ausführt, wird als Ende der Warteschlange bezeichnet, und das Ende, das den Löschvorgang ausführt, wird als Kopf der Warteschlange bezeichnet. Wenn die Warteschlange keine Elemente enthält, spricht man von einer leeren Warteschlange.

Die Datenelemente der Warteschlange werden auch Warteschlangenelemente genannt. Das Einfügen eines Warteschlangenelements in die Warteschlange wird als Enqueuing bezeichnet, das Löschen eines Warteschlangenelements aus der Warteschlange wird als Dequeuing bezeichnet. Da die Warteschlange nur das Einfügen an einem Ende und das Löschen am anderen Ende zulässt, kann nur das Element, das am frühesten in die Warteschlange eintritt, zuerst aus der Warteschlange gelöscht werden. Daher wird die Warteschlange auch als „First-in-first-out“ (FIFO – zuerst) bezeichnet in first out) lineare Liste.

Sequentielle Warteschlange

Um eine sequentielle Warteschlangenstruktur einzurichten, müssen Sie einen kontinuierlichen Speicherplatz statisch zuweisen oder dynamisch beantragen und zwei Zeiger für die Verwaltung festlegen. Einer ist der vordere Zeiger des Kopfes, der auf das Kopfelement zeigt, der andere ist der hintere Zeiger des Schwanzes, der auf den Speicherort des nächsten Elements zeigt, das dem Team hinzugefügt wird, wie in der Abbildung gezeigt Wenn ein Element am Ende der Warteschlange eingefügt wird, erhöht sich die Rückseite um 1; jedes Mal, wenn ein Element am Anfang der Warteschlange gelöscht wird, erhöht sich die Vorderseite um 1. Während die Einfüge- und Löschvorgänge fortschreiten, ändert sich die Anzahl der Warteschlangenelemente weiter, und der von der Warteschlange belegte Speicherplatz bewegt sich auch in dem kontinuierlichen Speicherplatz, der der Warteschlangenstruktur zugewiesen ist. Wenn vorne = hinten, gibt es keine Elemente in der Warteschlange, was als leere Warteschlange bezeichnet wird. Wenn der hintere Bereich über den kontinuierlichen Speicherplatz hinausgeht, der auf die Zuweisung hinweist, kann die Warteschlange keine neuen Elemente mehr einfügen, es gibt jedoch häufig einen großen verfügbaren Speicherplatz, der zu diesem Zeitpunkt nicht belegt ist. Bei diesen Speicherplätzen handelt es sich um bereits belegte Speichereinheiten Warteschlangenelemente, die aus der Warteschlange entfernt wurden.

Überlaufphänomen in der sequentiellen Warteschlange:

(1) „Unterlauf“-Phänomen: Wenn die Warteschlange leer ist, wird das Überlaufphänomen durch den Warteschlangenvorgang verursacht. „Unterlauf“ ist ein normales Phänomen und wird häufig als Bedingung für die Übertragung der Programmsteuerung verwendet.

(2) „Echter Überlauf“-Phänomen: Wenn die Warteschlange voll ist, führt eine Push-Operation auf dem Stapel zu einem Speicherplatzüberlauf. „Echter Überlauf“ ist eine Fehlerbedingung und sollte vermieden werden.

(3) „Falscher Überlauf“-Phänomen: Da die Kopf- und Schwanzzeiger während der Warteschlangen- und Warteschlangenoperationen nur zunehmen, aber nicht abnehmen, kann der Speicherplatz des gelöschten Elements niemals wiederverwendet werden. Wenn die tatsächliche Anzahl der Elemente in der Warteschlange weitaus kleiner ist als die Größe des Vektorraums, ist der Warteschlangenvorgang möglicherweise nicht möglich, da der Endzeiger die Obergrenze des Vektorraums überschritten hat. Dieses Phänomen wird als „falscher Überlauf“ bezeichnet.

Kreisförmige Warteschlange

Um den Warteschlangenraum tatsächlich wiederverwendbar zu machen, wird bei der tatsächlichen Verwendung der Warteschlange die Methode zur Warteschlangennutzung häufig leicht verbessert: Unabhängig vom Einfügen oder Löschen wird der hintere Zeiger um 1 oder der vordere Zeiger um 1 erhöht, sobald sich der vordere Zeiger um 1 erhöht um 1 überschreitet es den zugewiesenen Warteschlangenraum und leitet ihn an die Startposition dieses kontinuierlichen Raums. Wenn Sie wirklich von MaxSize-1 um 1 auf 0 wechseln, können Sie die Restoperationen „rear%MaxSize“ und „front%MaxSize“ verwenden, um dies zu erreichen. Dies stellt sich den Warteschlangenraum tatsächlich als kreisförmigen Raum vor, und die Speichereinheiten im kreisförmigen Raum werden zyklisch verwendet. Die auf diese Weise verwaltete Warteschlange wird auch als kreisförmige Warteschlange bezeichnet. Neben einigen einfachen Anwendungen ist die kreisförmige Warteschlange die wirklich praktische Warteschlange.

Wenn in einer kreisförmigen Warteschlange die Warteschlange leer ist, gibt es vorne = hinten, und wenn der gesamte Warteschlangenraum voll ist, gibt es auch vorne = hinten. Um zwischen den beiden Situationen zu unterscheiden, wird festgelegt, dass die zirkuläre Warteschlange höchstens MaxSize-1-Warteschlangenelemente enthalten kann. Wenn nur noch eine leere Speichereinheit in der zirkulären Warteschlange vorhanden ist, ist die Warteschlange voll. Daher ist die Bedingung, dass die Warteschlange leer ist, vorne = hinten, und die Bedingung, dass die Warteschlange voll ist, ist vorne = (hinten + 1) % MaxSize. Die Situation bei leeren und vollen Warteschlangen ist wie folgt:

Empfehlung: „

Programmiervideo

“

Das obige ist der detaillierte Inhalt vonWelche Datenstruktur hat eine Warteschlange?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!