Datenstrukturen – Stapel

Beim Programmieren müssen wir mit vielen, vielen Daten arbeiten. Daher müssen wir die Daten effizient speichern und organisieren. Hier erweisen sich Datenstrukturen als nützlich. Wir können Datenstrukturen zum Speichern, Organisieren, Verarbeiten und Abrufen von Daten verwenden. Datenstrukturen können je nach Anordnung der Daten weiter in zwei Kategorien unterteilt werden.

In diesem Artikel werde ich über lineare Strukturen ( Stapel ) sprechen. Im Vergleich zu nichtlinearen Strukturen sind die Konzepte hinter linearen Strukturen relativ einfacher zu verstehen. Einige Beispiele für solche linearen Strukturen sind Stack, Queues, Deques und Lists. Wir werden jede dieser Datenstrukturen einzeln durchgehen. Man kann sich diese linearen Strukturen mit zwei Enden vorstellen. (vorne und hinten | links und rechts | oben und unten) Einige lineare Strukturen ermöglichen das Einfügen oder Entfernen von Elementen nur an einem Ende, während andere Strukturen dies an beiden Enden ermöglichen.

1. Stapel

• Ein Stapel ist also im Grunde eine geordnete Ansammlung von Elementen, bei der das Einfügen und Entfernen von Elementen am selben Ende erfolgt. Dieses Ende wird allgemein als „Top“ bezeichnet. Auch das der Oberseite gegenüberliegende Ende wird als „Unten“ bezeichnet.
• Außerdem befinden sich neuere Artikel oben und ältere unten. Daher ist die Reihenfolge beim Entfernen von Gegenständen aus dem Stapel die umgekehrte Reihenfolge wie beim Einlegen von Gegenständen in den Stapel.
• Nachdem wir nun das Verhalten eines Stapels gut verstanden haben, werfen wir einen Blick auf einige wichtige Vorgänge im Zusammenhang mit der Stapeldatenstruktur.
• push (Element) – Die Push-Methode wird verwendet, um ein Element oben in den Stapel einzufügen.
• pop () – Die Pop-Methode wird verwendet, um das oberste Element vom Stapel zu entfernen
• peek () – Die Peek-Methode wird verwendet, um das aktuell oberste Element des Stapels anzuzeigen.
• size () – Gibt die Anzahl der Elemente zurück, die auf dem Stapel vorhanden sind
• is_empty () – Diese Methode ist nützlich, um zu überprüfen, ob der Stapel leer ist oder nicht
• Beachten Sie, dass hier das Ende der Liste als oberstes Ende des Stapels betrachtet wird. (Zeitkomplexität – O(1)) Wir können den Anfang der Liste als die Spitze des Stapels betrachten, dies wäre jedoch nicht sehr effizient, da die Zeitkomplexität O(n) wäre , wenn wir Elemente verschieben oder entfernen.
• Wenn wir das Ende der Liste als die Spitze des Stapels betrachten


• Nachdem wir nun wissen, wie man einen Stack implementiert, werfen wir einen Blick auf einige Szenarien, in denen die Verwendung der Stack-Datenstruktur von entscheidender Bedeutung ist.
• Umrechnungen des Zahlensystems
• Sehen wir uns zunächst an, wie wir mithilfe eines Stapels eine Dezimalzahl in eine Binärzahl umwandeln können.

• Erweitern wir nun den obigen Algorithmus, um eine Dezimalzahl in ein beliebiges Zahlensystem zwischen 2 und 16 umzuwandeln.


Fast jede Programmiersprache da draußen verwendet Klammern in ihrer Syntax. Wenn wir die Klammern nicht ausgewogen verwenden, kann es daher zu einem Syntaxfehler kommen.

• In der ersten Phase dieses Problems werde ich nur eine Art von Klammern betrachten, beispielsweise (). Wir müssen prüfen, ob die Klammern ausgeglichen sind oder nicht. Bei Ausgewogenheit sollten wir „true“ zurückgeben, andernfalls „false“.
• ( ) – ausgeglichen | ( ( ) ) – ausgeglichen | ( ( ( )( ) ) ) – ausgeglichen
• ( ( ) nicht ausgeglichen | ( ) ( ) ( – nicht ausgeglichen | ( ( ( ) ) ( ) – nicht ausgeglichen

• ( [ ] ) – ausgeglichen | ( ( ) { } ) – ausgeglichen | ( ( [ { } [ ] ] ) ) – ausgeglichen
• ( ( ) nicht ausgeglichen | ( ) { } ] – nicht ausgeglichen | ( ( { } [ [ ) – nicht ausgeglichen


3. Kehren Sie eine Zeichenfolge mithilfe eines Stapels um



4. Infix | Postfix- und Präfix-Notation

In der Informatik haben wir es mit vielen arithmetischen Ausdrücken zu tun. Ein Ausdruck besteht aus Operatoren (+, -, *, / usw.), Operanden (A, B, c, d, 1, 2,…) und Symbolen wie Klammern.

• Infix-Notation – In dieser Notation wird der Operator zwischen den Operanden platziert. (<Operand> <Operator> <Operand>)
• Wenn der Ausdruck nur aus einem Operator besteht (z. B. 2 + 3, 4 * 6), können wir den Ausdruck sofort lösen. Wenn der Ausdruck jedoch mehr als einen Operator hat, können wir ihn aufgrund der Mehrdeutigkeit des Ausdrucks nicht direkt lösen. Betrachten Sie diesen Ausdruck als 1 + 4 * 5. Wenn wir zuerst die Addition durchführen, erhalten wir die Antwort als [ ( 1 + 4 ) * 5 ] = 25, und wenn wir zuerst die Multiplikation durchführen, erhalten wir die Antwort als [1 + (4 * 5 )] = 21. Wie Sie sehen können, gibt es in dieser Notation einige Unklarheiten. Um dieses Problem zu lösen, verwenden wir daher etwas, das „Operatorpriorität“ genannt wird. Gemäß der Operatorpriorität sollte die Multiplikation vor der Addition erfolgen. Die richtige Antwort sollte also 21 sein, nicht 25.
• Um einen Ausdruck zu lösen, der in Infix-Notation geschrieben ist, müssen wir grundsätzlich eine Reihe von Regeln befolgen und auch Klammern hinzufügen. Daher könnte diese Notation beim Lösen mehr Speicher beanspruchen. Um diese Herausforderungen zu meistern, haben Wissenschaftler zwei weitere Notationen entwickelt: Präfix und Postfix.
• In der Präfix-Notation wird der Operator vor den Operanden platziert (<Operator><Operand> <Operand>) , während in der Postfix-Notation der Operator nach den Operanden platziert wird. (<Operand> <Operand><Operator>)
• Im Vergleich zur Infix-Notation sind die beiden anderen Notationen für einen Menschen recht schwer zu lesen und zu verstehen. Da diese beiden Notationen jedoch keine zusätzlichen Symbole wie Klammern enthalten und keine Mehrdeutigkeiten enthalten, können die in diesen beiden Formaten geschriebenen Ausdrücke problemlos von Computern gelesen werden.


• Auswerten eines Postfix-Ausdrucks: Wenn wir einen Postfix-Ausdruck auswerten müssen, sollten wir mit dem Scannen von links beginnen, bis wir einen Operator finden. Sobald wir einen Operator gefunden haben, müssen wir die entsprechende algebraische Operation an den ersten beiden Operanden links vom Operator ausführen.

• Zunächst müssen alle Leerzeichen in unserer Eingabe entfernt werden. Daher müssen wir die Split-Methode verwenden. Dann müssen wir unseren Gesichtsausdruck von links nach rechts scannen. Wenn wir auf eine Zahl stoßen, müssen wir sie in den Stapel schieben. Wenn wir auf einen Operator stoßen, müssen wir zwei der obersten Elemente in unserem Stapel entfernen. Dann müssen wir unsere Hilfsfunktion aufrufen, um die arithmetische Operation auszuführen. Danach werden wir das Ergebnis in den Stapel schieben. Sobald wir mit dem Scannen fertig sind, geben wir den Rest in unserem Stapel zurück, nämlich die Antwort für den ausgewerteten Postfix-Ausdruck.


• Sehen wir uns nun an, wie wir mit Python einen Ausdruck im Infix-Format in Postfix konvertieren können.