Nachdem diese wichtigen Methoden erklärt wurden, werfen wir einen Blick auf die endgültige Implementierung unserer Stack-Klasse:
Die Push- und Pop-Methoden erscheinen genau wie erwartet (Zeilen 13-32). Wir können unsere Push-Methode verwenden, um einen benutzerdefinierten Initialisierer mit einigen variablen Werten zu erstellen (Zeilen 7-11). Zusätzlich können wir nach einem leeren Stapel suchen, indem wir prüfen, ob unser rootNode einen Wert hat (Zeilen 34-36) und eine grundlegende Druckmethode haben, die unsere Liste durchläuft, solange sie über die nächste Eigenschaft auf Knoten zugreifen kann (Zeilen 38-44).
Ein grundlegender Test unserer Stack-Funktionalität sieht folgendermaßen aus:
Zu wissen, wie man einen Stack implementiert, ist eine Sache, aber noch wichtiger ist es, Situationen zu erkennen, für die ein Stack gut geeignet ist. In diesem nächsten Abschnitt werden wir uns drei solcher Fälle ansehen.
Anwendungsfall 1: Reihenfolge umkehren
Da die Reihenfolge eines Stapels festgelegt ist, kann die umgekehrte Reihenfolge sehr einfach erreicht werden, indem Elemente von einem Stapel und sofort auf einen anderen gelegt werden. Kein Herumspielen mit dem Tauschen von Indizes!
Anwendungsfall 2: Testen der Symmetrie
Ein weiterer guter Anwendungsfall für Stapel ist das Testen der Symmetrie. Im folgenden Beispiel testen wir eine Reihe von Klammern, um sicherzustellen, dass jede schließende Klammer das richtige Gegenstück zu einer früheren öffnenden Klammer ist.
Wir beginnen mit der Überprüfung, dass die Anzahl der Zeichen durch zwei teilbar ist, da eine ungerade Anzahl von Zeichen durch zwei teilbar wäre (Zeile 6). Als nächstes überprüfen wir, ob wir gültige Eingaben haben, indem wir einen Zeichensatz illegaler Zeichen definieren und dann überprüfen, ob unsere Eingabezeichenfolge einen Nullbereich illegaler Zeichen enthält (Zeilen 7-8). Um zu überprüfen, ob unsere schließenden und öffnenden Klammern übereinstimmen, fügen wir sie als Schlüssel-Wert-Paare in ein Wörterbuch ein (Zeile 10). In anderen Situationen können Sie möglicherweise den inversen Wert berechnen, ohne Paare in einem Wörterbuch speichern zu müssen. Dann haben wir unseren Stapel (Zeile 11). Der Zweck unseres Stapels besteht in diesem Fall darin, Öffnungsklammern zu speichern. Wenn wir unsere Zeichenfolge durchlaufen, können wir überprüfen, ob unser Zeichen eine öffnende Klammer ist, indem wir testen, ob es sich um einen Schlüssel in unserem Wörterbuch handelt. Wenn ja, schieben wir es auf unseren Stapel. Sobald wir unsere erste geschlossene Klammer gefunden haben, wissen wir, dass wir die zweite Hälfte unseres Musters durcharbeiten, also setzen wir unseren firstHalf boolean auf false (Zeile 12). Wenn wir nach diesem Punkt weitere öffnende Klammern finden, können wir den Booleschen Wert überprüfen und einen fehlgeschlagenen Test anzeigen. Für jede schließende Klammer entfernen wir die letzte öffnende Klammer und prüfen, ob es sich um ein korrektes Schlüssel-Wert-Paar handelt. Auch hier müssen wir die Zeichenfolge nur einmal durchlaufen, sodass wir aus einem linearen Algorithmus viel Wert ziehen.
Anwendungsfall 3: Rückgängigmachen von Befehlen
Schließlich verwenden wir einen Stapel in Verbindung mit dem Befehlsmuster, um einen Rückgängigmachungsverlauf zu erstellen. Schauen wir uns zunächst ein einfaches Bankkontoobjekt an. Es hat ein Guthaben und ein Überziehungslimit sowie einige einfache Methoden zum Ein- und Auszahlen von Geldern:
Anstatt die Ein- und Auszahlungsmethoden direkt aufzurufen, können wir die relevanten Informationen in einem Befehl speichern. Im folgenden Snippet geben wir an, welche Art von Aktion wir mit einer Enum-Eigenschaft (Einzahlung oder Auszahlung) und einem Betrag ausführen möchten . Wir speichern auch einen booleschen Wert, um anzuzeigen, ob der Befehl ausgeführt werden konnte (Zeilen 4-11). Beachten Sie, dass, wenn die Auszahlungsanforderung das Überziehungslimit überschreitet, dem Bankkonto nichts passiert und der boolesche Wert false bleibt, andernfalls wird er nach Abschluss des Befehls wahr (Zeilen 18-26). Wir haben zwei Methoden, um den Befehl aufzurufen oder rückgängig zu machen, wobei jede ein Bankkonto als Argument verwendet (Zeilen 18 & 28). Diese Methoden nehmen das Bankkonto und rufen seine Instanzmethoden auf, die wir im vorherigen Snippet gesehen haben.
Zurück zum Bankkonto können wir nun unsere commandStack-Eigenschaft einführen, die mit unserem BankAccountType (Zeile 47) initialisiert wurde. Wir markieren unsere Einzahlungs- und Auszahlungsmethoden als fileprivate, so dass sie nur von unserem BankAccountCommand (Zeilen 62 & 66) aufgerufen werden können. Jetzt haben wir zwei exponierte Methoden: process(command:) und undoLastCommand() . Der erste akzeptiert einen Befehl als Eingabe, führt ihn mit dem Bankkonto als Eingabe aus und schiebt den Befehl dann auf den Stapel. Mit der Methode undoLastCommand wird der letzte Befehl vom Stapel entfernt und rückgängig gemacht (Zeilen 51-60).
Dies ist ein sehr einfaches Muster, und eines, das sehr mächtig ist. Die möglichen Anwendungen sind endlos und sorgen für eine zufriedenstellende Benutzererfahrung.
Und jetzt sehen wir das Muster in Aktion:
Wrap Up
In diesem Artikel haben wir das Konzept eines Stacks und das LIFO-Verhalten untersucht. Wir haben unseren eigenen Stapel mithilfe einer doppelt verknüpften Liste implementiert und gezeigt, wie Speicher zugewiesen und freigegeben wird, wenn sich die Größe des Stapels ändert. Wir haben uns auch drei gängige Anwendungsfälle für Stapel angesehen: Umkehren, Testen der Symmetrie und Rückgängigmachen. Jede dieser drei Situationen kommt unzählige Male in realen Projekten vor. Ich hoffe, dass Sie sich einen Stack als geeignete Struktur für diese Anforderungen vorstellen. Wie immer, danke fürs Lesen!