Woher weiß ich, wann ich einen Stapel anstelle von anderen Sammlungen verwenden soll?

Question

Hier ist ein wenig Auftakt zu der allgemeineren Frage, über die ich mich wundere:

Ich habe vor kurzem eine Programmieraufgabe, wo Sie eine Methode schreiben sollen, die das Gleichgewicht der Klammern in einem bestimmten String überprüft. Die Methode sollte einen String aufnehmen und den Index zurückgeben, bei dem der erste Zusatz ')' oder '(' Klammern, oder die Länge des Strings, wenn sie gleich sind. Einige Beispieleingaben wären wie folgt: ") (asdf))) "- 0; (((asdf))) "- 0;" (((asdf)) "- 1;" (ab) ((cd) (asdf) "- 5.

Ich begann mit dem Versuch Erstellen Sie eine Liste für jede Richtung von Klammern, die die Indizes von allen in der Zeichenfolge speichern würde.Ich würde dann jedes Zeichen in der Zeichenfolge durchlaufen, fügen Sie den Index zu einer der beiden Listen hinzu, wenn sie übereinstimmen, und prüfen Sie, ob sie bereits vorhanden waren Diese Strategie funktionierte für einige der Fälle, aber bestimmte Szenarien scheiterten noch immer.Wenn ich festgefahren war, überprüfte ich einige der anderen Antworten auf die Herausforderung und sah, dass sie einen Stapel verwendeten, um den Index der linken Klammern zu speichern und pop von, wenn nötig.Dieser Weg arbeitete viel, viel besser, und ich fühlte mich ein wenig peinlich für nicht daran denken selbst.

Das bringt mich zu meiner Frage ... wie mache ich kn Wenn es besser ist, einen Stack gegenüber anderen verschiedenen Collections zu verwenden? Was sind einige häufige Dinge, die mich dazu bringen können, einen Stack gegenüber einer anderen Collection zu verwenden?

Ich weiß, wie Stacks arbeiten und habe sie in einigen Tutorials und so verwendet, aber habe mich nie wirklich finden sie in der realen Welt zu verwenden ... die, nachdem ich die Einfachheit, die sie mit der Herausforderung erstellt haben, denke ich habe einige Möglichkeiten verpasst, um Code einfacher/besser zu machen.

Answer 1

Wenn Sie mit LIFO (Last In First Out) arbeiten müssen wie beim Aufruf der Funktion oder mit Postfix-Notation.

You can see here more java examples!

Answer 2

Wie schon andere gesagt hat, ein Stapel für verwendet, wenn Sie Ihre Sammlung brauchen Last In, First Out (LIFO) Verhalten zu haben. Dies kann sich manifestieren, wenn Sie Informationen auf dem "obersten" oder "letzten" von etwas verarbeiten.

Das Beispiel Sie war darüber gesprochen, ein großartiges Beispiel dafür, wie man am effektivsten Prozessgruppen Klammern, speichern Sie die linke Klammer in einer Sammlung, und Sie die aktuellste linken Klammer entfernen, wenn Sie in eine rechts- laufen Klammer.

Stapel können auch in bestimmten Baum/Graph-Traversalalgorithmen verwendet werden. Ansätze für die erste Tiefe verwenden einen Stapel, um die Liste der Knoten zu speichern, die noch durchlaufen werden müssen, da die Verwendung eines Stapels kombiniert mit einem konsistenten Einfügungsmuster die inhärente Eigenschaft hat, die Tiefe der Bäume über ihre Breite zu durchsuchen. (Die Kehrseite davon ist, dass Breath-First Traversal-Algorithmen stattdessen eine Queue verwenden.)

Eine andere mögliche Verwendung wäre ein Kartenspiel. Für die meisten Spiele interessiert es dich nicht, was irgendwo in der Mitte des Decks ist. Wenn der Spieler eine Karte braucht, zieht er einfach eine Karte von der Spitze. Da dies das Verhalten eines Stacks genau nachahmt, wäre ein Stack eine mögliche Überlegung für diese Art von Anwendung. (Schließlich ist ein "Deck" nur ein Stapel Karten.)

Es gibt eine Reihe anderer Anwendungen. Allen gemeinsam ist, dass sie für Zeiten funktionieren, in denen Sie entweder das oberste Element oder das neueste Element einer Sammlung benötigen. Zu wissen, ob Ihre spezielle Anwendung von einem Stack profitieren würde, erfordert ein wenig Erfahrung, um diese Szenarien zu erkennen.

EDIT: Oh, und natürlich gibt es den-Stack, die .NET-Anwendungen für Verfahren-scope und temporäre Variablen. Es ist kein Zufall, dass es seinen Namen mit der Datenstruktur teilt. Wenn eine Variable in einer Methode deklariert ist, wird die Speicherzuordnung am Ende eines Stapels hinzugefügt. Wenn die Methode dann zurückkehrt und die Variable den Gültigkeitsbereich verlässt, wird dieser Speicher vom Stapel ausgegeben und an den Garbage Collector übergeben.

Answer 3

Ein anderer guter Fall für einen Stapel ist, wenn Sie einen "Kontext" eingeben, den Sie schließlich verlassen werden. Dies umso mehr, wenn Sie einige Informationen speichern, die nur zwischen den beiden Augenblicken gültig sind und vergessen werden können, sobald Sie diesen "Kontext" verlassen haben.

Im Klammerbeispiel geben Sie "ein", wenn Sie ( übereinstimmen und den Klammernblock bei Übereinstimmung mit ) "verlassen". Während Sie sich in den Klammern befinden, müssen Sie sich an die Anfangsposition von ( erinnern (falls es keine Übereinstimmung gibt )), aber sobald Sie die passende ) finden, können Sie diese Information vergessen.

Answer 4

Das Folgende ist die gewählte Antwort von der Frage SO kopiert: When to use the Stack collection in C#?

P. S. Ich plagiiere nicht. Ich habe diese Antwort geschrieben.

---

Im Idealfall verwenden Sie, oder erstellen Sie je nach Bedarf, Klassen, die widerspiegeln, wie die Dinge in der realen Welt arbeiten, die Dinge, die Sie in Code modellieren. Solche Klassen geben uns ein Abstraktionsniveau, so dass wir in Bezug auf das, was wir modellieren/simulieren, kodieren können. Zusätzlich hilft die Verwendung eines vertrauten Paradigmas, wenn eine komplexe Sache codiert wird. Um zu sagen: Oh, diese Fuzzinator Klasse benutzt einen Stack. Ich weiß was ein Stack ist und wie es funktioniert.

Zweitens gibt uns diese Klasse der höheren Abstraktionsstufe Code, der funktioniert (wir gehen davon aus, dass das .NET-Framework getestet wurde) und erspart uns die Zeit und den Schmerz, das Rad neu zu erfinden.

Drittens ist der Code leichter zu lesen, einfacher zu verstehen, einfacher zu ändern und so weiter. Es ist wartungsfreundlicher.

Die Verwendung von Klassen mit verfeinerterer Funktionalität hilft zu begrenzen, wie wir es vermasseln könnten.

Insgesamt ist Ihre Anwendung einfach besser, wenn sie auf geeigneten Abstraktionsebenen codiert ist.

Stack ist eine dieser Klassen.

Mein HP-41X Rechner führt seine Arithmetik mit einem Stapel aus. Diese Art der Berechnung nennt sich RPN - Reverse Polish Notation.

Wenn ich eine Cafeteria simulieren würde, wäre der Stack perfekt für diesen Plattenstapel. Die Platten steigen von oben auf und ab. Nicht die Mitte, nicht das Ende; nur die Spitze. Ein Stapel. Ich kann nur Push() und Pop() Platten, die den Code einfacher und klarer macht. Alternativ stellen Sie sich vor, Sie codieren mit dem C# -Aquivalent von subatomaren Partikeln - generische Auflistung oder generisches IEnumerable, usw. Am Ende verwende ich allgemeine Hilfsmethoden und Eigenschaften mit allgemeinen Namen mit mehreren variablen Zahlen von Parametern, die in der Gesamtheit unklar sind die Tatsache, dass ich Teller staple.