Stapel und Warteschlangen in Verse | Unreal Editor für Fortnite Dokumentation

Übersicht

Stapel und Warteschlangen sind in der Computerwissenschaft allgemeine Datenstrukturen, welche die Reihenfolge festlegen, in der du Elemente hinzufügen und entfernen kannst. Du kannst mit ihnen die Reihenfolge steuern, in der du mit Daten interagierst:

Stapel: Ein Container, zu dem du Elemente in einer „zuerst herein, zuletzt hinaus“-Reihenfolge (first-in, last-out; FILO) hinzufügst und daraus entfernst, so wie zu das oberste Buch von einem Stapel Bücher herunternehmen würdest.
Warteschlange: Ein Container, zu dem du Elemente in einer „zuerst herein, zuerst hinaus“-Reihenfolge (first-in, first-out; FIFO) hinzufügst und daraus entfernst, wie zum Beispiel bei einer Schlange von Kunden, die für Essen anstehen.

Obwohl der zugrundeliegende Code für Stapel und Warteschlangen ähnlich ist, gibt es wesentliche Unterschiede und Stärken, die du nutzen kannst, um deine Erfahrung schnell, effizient und intuitiv zu machen.

Stapel

Stell dir Stapel als einen Stapel mit Pfannkuchen vor. Angenommen, du bist zum Frühstück in einem Restaurant und der Kellner reicht dir einen endlosen Stapel Pfannkuchen. Da du höflich sein möchtest, nimmst du dir immer nur einen Pfannkuchen und immer nur oben vom Stapel. Du kannst den Kellner bitten, einen neuen Pfannkuchen auf den Stapel zu legen (push), und wenn du hungrig bist, kannst du oben vom Stapel einen Pfannkuchen nehmen (pop) und ihn auf deinen Teller legen, um ihn zu essen. Wenn du einen bestimmten Pfannkuchen in der Mitte des Stapels essen möchtest, musst du von oben immer weiter Pfannkuchen weg essen, bis du zu dem kommst, den du haben möchtest. Der erste Pfannkuchen, der hinzugefügt wurde, wird der letzte sein, den du entfernst. So wird ein Stapel zu einer FILO-Datenstruktur (first-in, last-out; zuerst hinein, zuletzt hinaus).

Wann verwenden

Stapel sind praktisch, wenn du dich zurückarbeiten musst oder dir merken willst, in welcher Reihenfolge du Ereignisse abgewickelt hast. Das kann eine Rückgängig-Funktion sein, eine Ereigniskette oder eine Reihe von Auswahloptionen. Du könntest zum Beispiel einen Roboter haben, der sich durch ein Labyrinth mit verzweigenden Pfaden arbeiten muss. Wenn der Roboter im Labyrinth auf eine Gabelung trifft, wählt er einen Pfad und schiebt diese Auswahl in den Stapel. Wenn er in einer Sackgasse landet, arbeitet er sich rückwärts durch den Stapel, ruft seine eigene Auswahl ab, bis er einen neuen Pfad findet, den er nehmen kann.

Implementierung in Verse

Die Verse-API verfügt nicht über eine eingebaute Implementierung von Stapeln, aber du kannst selbst eine erstellen.

Du kannst die Elemente in einem Stapel mit jeder geordneten Datenstruktur darstellen, wie ein Array oder eine verknüpfte Liste. In diesem Beispiel verwendest du ein Array, da es dir einfachen Zugriff auf das oberste Element des Stapels bietet.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

Das Array Elements speichert die Objekte im Stapel, die den Typ t haben. Das bedeutet, dass du einen Stapel mit jedem Elementtyp initialisieren kannst, wie int, float, stack usw. Die Verwendung von type als Argument für die Stapelklasse ist ein Beispiel für einen parametrischen Typ.

Wir definieren zuerst einige Helferfunktionen. Du musst wissen, wo das oberste Element des Stapels ist, damit du Push() und Pop() für die Elemente nutzen kannst. Hierfür benötigst du drei Funktionen: Size(), IsEmpty() und Peek().

# Gibt die Größe des Stapels zurück
    Size<public>()<transacts>:int=
        Elements.Length

    # Ist erfolgreich, wenn der Stapel leer ist
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Gibt das oberste Element des Stapels zurück
    Peek<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]

Die Funktion Size() gibt einfach die Length des Elements-Arrays zurück. Die Funktion IsEmpty() ruft die Funktion Size() auf und verfügt über den Bezeichner <transacts>, was bedeutet, dass sie fehlschlägt, wenn Size() nicht gleich 0 ist.

Die Funktion Peek() gibt das Element mit dem obersten Index (Länge - 1) des Elements-Array zurück. Diese Funktion verfügt über die Bezeichner<decides><transacts>, da der Arrayzugriff fehlschlagen kann, wenn das Array leer ist.

Um einen Stapel zu instanziieren, kannst du eine Constructor-Funktion verwenden. Ein Constructor ist eine spezielle Funktion, die eine Instanz der Klasse erzeugt, mit der sie verbunden ist. Der Constructor legt die Anfangswerte für ein Objekt fest und ermöglicht den Zugriff auf den Wert von Elements und die Zuweisung eines Elemente-Ausgangsarrays.

# Erstellt einen Stapel aus einem Elemente-Anfangsarray InitialElements und gibt ihn zurück
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements

Push und Pop

Um Elemente zum Stapel hinzuzufügen und sie daraus zu entnehmen, musst du das neue Element entweder oben auf den Stapel legen (push) oder es von oben entfernen (pop).

# Fügt NewElement oben zum Stapel hinzu, indem ein neuer
# Stapel mit NewElement als oberstem Element zurückgegeben wird
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Entfernt das oberste Element vom Stapel und gibt ein Tupel mit dem neuen
# Stapel mit dem entfernten obersten Element und dem entfernten Element zurück.
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
    FirstElement := Peek[]
    (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

Die Funktion Push() nimmt das Element, das du oben auf den Stapel legen willst, und gibt einen neuen Stapel mit diesem Element als oberstem Element zurück. Das Zurückgeben eines neuen Stapels anstelle der Änderung des aktuellen Stapels ist ein Beispiel für die funktionale Programmierung, die das Risiko von Nebeneffekten reduziert.

Um die Funktion Pop() zu implementieren, musst du zuerst mit Peek() das oberste Element des Stapels finden. Dann musst du das oberste Element entfernen (mit der Funktion RemoveElement[]) und einen neuen Stapel ohne das Element zurückgeben. Du kannst mit einem Tupel sowohl den neuen Stapel als auch das entfernte Element zusammen zurückgeben. Aufgrund der fehlbaren Ausdrücke für den Arrayzugriff und den Aufruf an Peek(), benötigt Pop() die Bezeichner <decides><transacts>.

Vollständiger Code

Im Folgenden findest du den vollständigen Code für die Stapelklasse.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Fügt NewElement oben zum Stapel hinzu, indem ein neuer
    # Stapel mit NewElement als oberstem Element zurückgegeben wird
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Entfernt das oberste Element vom Stapel und gibt ein Tupel mit dem neuen
    # Stapel mit dem entfernten obersten Element und dem entfernten Element zurück.
    Pop<public>()<decides><transacts>:tuple(stack(t),t)=
        FirstElement := Peek[]
        (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

    # Gibt die Größe des Stapels zurück
    Size<public>()<transacts>:int=
        Elements.Length

    # Ist erfolgreich, wenn der Stapel leer ist
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Gibt das oberste Element des Stapels zurück
    Peek<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]

Warteschlangen

Stell dir eine Warteschlange als Sushi-Transportband vor. Angenommen, du sitzt in einem Sushi-Restaurant, das deine Sushi-Teller nacheinander über ein Transportband schickt, sodass sie in der Reihenfolge ankommen, in der sie bestellt wurden. Du kannst den Teller ganz vorne in der Reihe aus der Warteschlange entfernen (dequeue), um ihn zu essen, aber du kannst immer nur einen Teller nehmen. Wenn du einen neuen Teller bestellen möchtest, bittest du den Koch, einen Teller am Ende der Reihe einzureihen (enqueue). Wenn sich in der Reihe bereits andere Sushi-Teller befinden, musst du die Teller vorne in der Reihe leer essen, bis du zum Teller am Ende kommst. Der erste Sushi-Teller, der hinzugefügt wurde, wird der erste sein, den du entfernst. Das macht eine Warteschlange zu einer FIFO-Datenstruktur (first-in, first-out; zuerst hinein, zuerst heraus).

Wann verwenden

Warteschlangen sind praktisch, wenn du Daten basierend auf der Reihenfolge verarbeiten musst, in der sie eintreffen. Das kann das Bedienen eines Kunden in einem Drive-Thru sein, eintreffende Anrufe in einem Callcenter oder das Stellen von Fragen an einen Spieler in einem Interview. Wenn du zum Beispiel einen Warteraum für Spieler erstellen musst, während diese eine Aufgabe erfüllen oder ein Erlebnis nacheinander durchlaufen, kannst du eine Warteschlange nutzen, um die Spieler danach zu ordnen, wann sie eingetroffen sind (wer zuerst kommt, mahlt zuerst).

Implementierung in Verse

Die Verse-API verfügt nicht über eine eingebaute Implementierung von Warteschlangen, aber du kannst selbst eine erstellen.

Wie bei Stapeln kannst du die Elemente in der Warteschlange mit jeder geordneten Datenstruktur darstellen, wie einem Array oder einer verknüpften Liste. In diesem Beispiel verwendest du ein Array, da es dir einfachen Zugriff auf den Anfang und das Ende der Warteschlange bietet. Sieh dir für eine Warteschlangenimplementierung mit einer verknüpften Liste diesen Codeschnippsel an.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

Das Array Elements speichert die Objekte in der Warteschlange, die den Typ t hat. Das bedeutet, dass du eine Warteschlange mit jedem Elementtyp initialisieren kannst, wie int, float, queue usw. Die Verwendung von type als Argument für die Stapelklasse ist ein Beispiel für einen parametrischen Typ.

Wie Stapel benötigen auch Warteschlangen ein paar Helferfunktionen. Du musst wissen, wo sich der Anfang und das Ende der Warteschlange befinden, damit du Enqueue() und Dequeue() ausführen kannst. Es ist auch hilfreich, die Größe der Warteschlange zu kennen und ob die Warteschlange leer ist. Du definierst dies in vier Funktionen: Size(), IsEmpty(), Front() und Back().

# Gibt die Größe der Warteschlange zurück
Size<public>()<transacts>:int=
    Elements.Length

# Ist erfolgreich, wenn die Warteschlange leer ist
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Gibt das erste Element in der Warteschlange zurück
Front<public>()<decides><transacts>:t=
    Elements[0]

# Gibt das letzte Element in der Warteschlange zurück
Rear<public>()<decides><transacts>:t=
    Elements[Elements.Length - 1]

Die Funktion Size() gibt die Length des Elements-Arrays zurück. Die Funktion IsEmpty() ruft die Funktion Size() auf und verfügt über den Bezeichner <transacts>, was bedeutet, dass sie fehlschlägt, wenn Size() nicht gleich 0 ist.

Die Funktionen Front() und Rear() geben das Element am vordersten (Index 0) und letzten Index (Länge - 1) des Elements-Arrays zurück. Beide Funktionen verfügt über die Bezeichner<decides><transacts>, da der Arrayzugriff fehlschlagen kann, wenn das Array leer ist.

Wie stack muss auch die Klasse queue eine Constructor-Funktion verwenden, um das Array Elements zuzuweisen. Die Constructor-Funktion ermöglicht dir den Zugriff auf den Wert von Elements und die Zuweisung eines Elemente-Ausgangsarrays.

# Erstellt eine Warteschlange aus einem Elemente-Anfangsarray InitialElements und gibt sie zurück
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Enqueue und Dequeue

Um Elemente zur Warteschlange hinzuzufügen und sie daraus zu entnehmen, musst du das neue Element am Ende der Warteschlange einreihen (enqueue) oder ein Element am entnehmen (dequeue).

# Fügt ein neues Element zum Ende der Warteschlange hinzu, indem
# eine neue Warteschlange mit NewElement am Ende zurückgegeben wird.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Entfernt das Element vorne in der Warteschlange und gibt ein Tupel
# mit einer neuen Warteschlange mit entferntem Element und dem entfernten Element zurück.
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
    FirstElement := Front[]
    (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

Die Funktion Enqueue() nimmt das Element, das du in die Warteschlange einfügen möchtest, und gibt eine neue Warteschlange mit dem neuen Element am Ende zurück. Das Zurückgeben einer neuen Warteschlange anstelle der Änderung der aktuellen Warteschlange ist ein Beispiel für die funktionale Programmierung, die das Risiko von Nebeneffekten reduziert.

Bei der Funktion Dequeue() musst du das Element vorne in der Warteschlange entfernen und zurückgeben und außerdem eine neue Warteschlange mit dem entfernten ersten Element (mit der Funktion RemoveElement[]) zurückgeben. Aufgrund der fehlbaren Ausdrücke für den Arrayzugriff und den Aufruf an Front(), benötigt Dequeue() die Bezeichner <decides><transacts>.

Vollständiger Code

Im Folgenden findest du den vollständigen Code für die Warteschlangenklasse.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Fügt ein neues Element zum Ende der Warteschlange hinzu, indem
    # eine neue Warteschlange mit NewElement am Ende zurückgegeben wird.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Entfernt das Element vorne in der Warteschlange und gibt ein Tupel
    # mit einer neuen Warteschlange mit entferntem Element und dem entfernten Element zurück.
    Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
        FirstElement := Front[]
        (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

    # Gibt die Größe der Warteschlange zurück
    Size<public>()<transacts>:int=
        Elements.Length

    # Ist erfolgreich, wenn die Warteschlange leer ist
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Gibt das erste Element in der Warteschlange zurück
    Front<public>()<decides><transacts>:t=
        Elements[0]

    # Gibt das letzte Element in der Warteschlange zurück
    Rear<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]
       
# Erstellt eine Warteschlange aus einem Elemente-Anfangsarray InitialElements und gibt sie zurück
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

# Fügt ein neues Element zum Ende der Warteschlange hinzu, indem
    # eine neue Warteschlange mit NewElement am Ende zurückgegeben wird.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

# Entfernt das Element vorne in der Warteschlange und gibt ein Tupel
    # mit einer neuen Warteschlange mit entferntem Element und dem entfernten Element zurück.
    Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
        FirstElement := Front[]
        (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

# Gibt die Größe der Warteschlange zurück
    Size<public>()<transacts>:int=
        Elements.Length

# Ist erfolgreich, wenn die Warteschlange leer ist
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

# Gibt das erste Element in der Warteschlange zurück
    Front<public>()<decides><transacts>:t=
        Elements[0]

# Gibt das letzte Element in der Warteschlange zurück
    Rear<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]
       
# Erstellt eine Warteschlange aus einem Elemente-Anfangsarray InitialElements und gibt sie zurück
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Auf eigene Faust

Es gibt viele Möglichkeiten, über Stapeln und Warteschlangen zu iterieren und sie zu verbessern, und du solltest verschiedene Möglichkeiten zum Hinzufügen von Funktionen ausprobieren. Hier findest du einige Ideen für deine ersten Schritte:

Kannst du eine Warteschlange in eine kreisförmige Warteschlange verwandeln, bei der das letzte Element mit dem ersten Element verbunden ist und die Warteschlange eine Schleife ausführt?
Was ist mit einer Prioritätswarteschlange, in der Objekte danach geordnet werden, wann sie in die Warteschlange eingeordnet wurden UND ein weiterer Wert berücksichtigt wird?
Kannst du Spiele mit einem Stapel erstellen, zum Beispiel „Türme von Hanoi“? Wie ist es mit einem Restaurantspiel, bei dem Kunden in einer Warteschlange warten müssen?