Stapel und Warteschlangen

Überblick

Stapel und Warteschlangen sind in der Computerwissenschaft gängige 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, in den du Elemente in der Reihenfolge zuerst rein, zuletzt raus (FILO) einfügst und entfernst, z. B. wenn Sie ein Buch vom oberen Ende eines Bücherstapels zum Lesen auswählen.

• Warteschlange: ein Container, in den du Elemente in der Reihenfolge zuerst rein, zuletzt raus (FIFO) einfügst und entfernst, z.B.l bei der Bearbeitung einer Kundenschlange, die auf eine Mahlzeit warten.

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 deinen Kellner bitten, einen neuen Pfannkuchen auf den Stapel zu pushen, und wenn du hungrig bist, kannst du oben vom Stapel einen Pfannkuchen nehmen 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 oder zuerst rein, zuletzt raus Datenstruktur.

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 von 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](parametric-types-in-verse).

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().

# Returns the size of the stack.
    Size<public>()<transacts>:int=
        Elements.Length

    # Succeeds if the stack is empty.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Returns the top element of the stack.
    Peek<public>()<decides><transacts>:t=

Die Funktion Size() gibt einfach die Length des Arrays Elements 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.

# Creates and returns a stack from an initial array of elements InitialElements.
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.

# Adds NewElement to the top of the stack by returning a new
# stack with NewElement as the top
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Removes the element on top of the stack and returns a tuple of both a new
# stack with the top element removed and the removed element.
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 oberstes Element zurück. Das Zurückgeben eines neuen Stapels anstelle der Änderung des aktuellen Stapels ist ein Beispiel für functional programming und reduziert das Risiko von side effects.

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{}

    # Adds NewElement to the top of the stack by returning a new
    # stack with NewElement as the top
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Removes the element on top of the stack and returns a tuple of both a new
    # stack with the top element removed and the removed element.

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 die Platte am Anfang der Warteschlange entnehmen, um sie abzuholen und zu essen, aber du kannst immer nur eine Platte auf einmal abholen. Wenn du eine neue Platte bestellen möchtest, bittest du den Chef, eine Platte einzureihen. 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 oder First In, First Out Datenstruktur.

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 von 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. Für eine Warteschlangen-Implementierung mit einer verknüpften Liste, schau dir dieses Code-Snippet an.

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

Das Array Elements speichert die Objekte in der Warteschlange vom Typ t. 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](parametric-types-in-verse).

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().

# Returns the size of the queue
Size<public>()<transacts>:int=
    Elements.Length

# Succeeds if the queue is empty
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Returns the element at the front of the queue.
Front<public>()<decides><transacts>:t=

Die Funktion Size() gibt die Length des Arrays Elements 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 Element-Arrays zurück. Beide Funktionen verfügen ü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.

# Creates and returns a queue from an initial array of elements InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Einreihen und Entreihen

Um Elemente zur Warteschlange hinzuzufügen und sie daraus zu entnehmen, musst du das neue Element entweder am Ende der Warteschlange einreihen oder ein Element von vorne entnehmen.

# Adds a new element to the back of the queue by returning a
# new queue with NewElement at the back.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Removes the element at the front of the queue and returns a tuple of
# both a new queue with the element removed and the removed element.
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 functional programming und reduziert das Risiko von side effects.

Für die 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{}

    # Adds a new element to the back of the queue by returning a
    # new queue with NewElement at the back.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Removes the element at the front of the queue and returns a tuple of
    # both a new queue with the element removed and the removed element.

Eigenständig

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:

• Kann man eine Warteschlange in eine kreisförmige Warteschlange verwandeln, bei der das letzte Element mit dem ersten Element verbunden ist und die Warteschlange eine Schleife bildet?

• Wie wäre es mit einer Prioritätswarteschlange, in der Objekte basierend auf dem Zeitpunkt ihres Eingangs in die Warteschlange UND nach einem anderen Wert geordnet werden?

• Kannst du Spiele mit einem Stapel erstellen, wie z. B. Tower of Hanoi? Wie ist es mit einem Restaurantspiel, bei dem Kunden in einer Warteschlange warten müssen?