In der Welt der Programmierung sind Datenstrukturen von entscheidender Bedeutung. Sie ermöglichen es uns, Informationen so zu ordnen, dass sie effizient genutzt werden können. Ein grundlegendes Konzept ist der Stack, eine der einfachsten Datenstrukturen.
Lassen Sie uns den Stack und seine Umsetzung in Python näher betrachten.
Was genau ist ein Stack?
Stellen Sie sich einen Stapel von Büchern oder Stühlen vor. Ein Stack funktioniert nach dem Prinzip „Last-In/First-Out“ (LIFO). Dies bedeutet, dass das zuletzt hinzugefügte Element als erstes entfernt wird. Betrachten wir ein anschauliches Beispiel.
Angenommen, wir haben einen Stapel Bücher vor uns.
Wenn wir nun das dritte Buch von oben benötigen, müssen wir zuerst die beiden oberen Bücher entfernen. Das oberste Buch ist also das letzte, das auf den Stapel gelegt wurde, aber das erste, das wieder heruntergenommen wird. Dieses LIFO-Prinzip ist die Grundlage für den Stack als Datenstruktur in der Programmierung.
Grundlegende Operationen eines Stacks
Ein Stack kennt hauptsächlich zwei grundlegende Operationen:
1. Push(Daten)
Diese Operation fügt neue Daten dem Stack hinzu, also legt sie „oben“ auf den Stapel.
2. Pop()
Diese Operation entfernt das oberste Element vom Stack, also nimmt es das oberste Element vom Stapel.
Betrachten Sie die folgenden Illustrationen für Push- und Pop-Operationen.
Zusätzlich zu den grundlegenden Operationen gibt es noch weitere hilfreiche Funktionen, die uns dabei helfen, mehr über den Stack zu erfahren.
Sehen wir sie uns genauer an.
peek()
Diese Funktion gibt uns das oberste Element des Stacks zurück, ohne es zu entfernen.
isEmpty()
Diese Funktion gibt uns einen booleschen Wert zurück, der angibt, ob der Stack leer ist oder nicht.
Nach dieser Einführung in die Theorie des Stacks, wollen wir uns nun der praktischen Umsetzung zuwenden.
Ich gehe davon aus, dass Python auf Ihrem Rechner installiert ist. Sollte das nicht der Fall sein, können Sie auch einen Online-Compiler verwenden.
Umsetzung des Stacks
Im Vergleich zu anderen Datenstrukturen ist der Stack relativ einfach zu implementieren. Es gibt verschiedene Möglichkeiten, einen Stack in Python zu realisieren.
Betrachten wir die verschiedenen Ansätze im Detail.
#1. Verwendung von Listen
Wir werden den Stack mithilfe einer Liste in einer Klasse implementieren. Sehen wir uns die Implementierung Schritt für Schritt an.
Schritt 1: Erstellen Sie eine Klasse namens Stack.
class Stack: pass
Schritt 2: Die Daten sollen in einer Liste gespeichert werden. Fügen wir eine leere Liste namens ‚elements‘ innerhalb der Stack-Klasse hinzu.
class Stack:
def __init__(self):
self.elements = []
Schritt 3: Um Elemente auf den Stack zu „schieben“, benötigen wir eine Methode. Wir erstellen eine ‚push‘-Methode, die Daten als Argument akzeptiert und diese an die Liste ‚elements‘ anhängt.
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
Schritt 4: Entsprechend erstellen wir die ‚pop‘-Methode, die das oberste Element vom Stack entfernt. Hierzu nutzen wir die ‚pop‘-Methode des Listendatentyps.
class Stack:
## ...
def pop(self):
return self.elements.pop()
Die grundlegende Implementierung des Stacks mit den erforderlichen Operationen ist nun abgeschlossen. Ergänzen wir diese um hilfreiche Funktionen, um weitere Informationen zum Stack zu erhalten.
Schritt 5: Mit einem negativen Index können wir das oberste Element des Stacks abrufen. Der Ausdruck [-1] gibt das letzte Element der Liste zurück, was in unserem Fall dem obersten Element des Stacks entspricht.
class Stack:
## ...
def peek(self):
return self.elements[-1]
Schritt 6: Wenn die Liste ‚elements‘ die Länge 0 hat, ist der Stack leer. Erstellen wir eine Methode, die überprüft, ob die Liste leer ist.
class Stack:
## ...
def is_empty(self):
return len(self.elements) == 0
Die Implementierung des Stacks mit dem Listendatentyp ist nun abgeschlossen.
Moment mal! Wir haben den Stack zwar implementiert, aber noch nicht gesehen, wie wir ihn verwenden. Wie machen wir das?
Schauen wir uns an, wie wir ihn zum Laufen bringen. Zuerst müssen wir ein Objekt der Stack-Klasse erstellen. Das ist nicht schwer. Los gehts:
class Stack: ## ... if __name__ == '__main__': stack = Stack()
Wir haben nun ein Stack-Objekt erstellt und können dieses verwenden. Führen Sie die folgenden Schritte aus, um die Stack-Operationen zu testen:
- Überprüfen Sie mit der Methode ‚is_empty‘, ob der Stack leer ist. Das Ergebnis sollte ‚True‘ sein.
- Fügen Sie die Zahlen 1, 2, 3, 4, 5 mit der Methode ‚push‘ zum Stack hinzu.
- Die Methode ‚is_empty‘ sollte nun ‚False‘ zurückgeben. Überprüfen Sie dies.
- Geben Sie das oberste Element mit der Methode ‚peek‘ aus.
- Entfernen Sie das oberste Element mit der Methode ‚pop‘ vom Stack.
- Überprüfen Sie nun erneut das oberste Element mit ‚peek‘. Das Ergebnis sollte 4 sein.
- Entfernen Sie nun alle Elemente vom Stack.
- Die Methode ‚is_empty‘ sollte nun wieder ‚True‘ zurückgeben. Überprüfen Sie dies.
Unsere Stack-Implementierung ist abgeschlossen, wenn sie alle obigen Schritte erfolgreich durchläuft. Versuchen Sie nun, den Code für die obigen Schritte selbst zu schreiben.
Haben Sie den Code fertig? Keine Sorge, sehen Sie sich den Code hier an:
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
def pop(self):
return self.elements.pop()
def peek(self):
return self.elements[-1]
def is_empty(self):
return len(self.elements) == 0
if __name__ == '__main__':
stack = Stack()
## checking is_empty method -> true
print(stack.is_empty())
## pushing the elements
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
## again checking is_empty method -> false
print(stack.is_empty())
## printing the topmost element of the stack -> 5
print(stack.peek())
## popping the topmost element -> 5
stack.pop()
## checking the topmost element using peek method -> 4
print(stack.peek())
## popping all the elements
stack.pop()
stack.pop()
stack.pop()
stack.pop()
## checking the is_empty method for the last time -> true
print(stack.is_empty())
Super! Wir haben den Stack von Grund auf mit dem Listendatentyp implementiert. Wenn Sie den obigen Code ausführen, sollten Sie die folgende Ausgabe erhalten:
True False 5 4 True
Wir könnten den Listendatentyp auch direkt als Stack verwenden. Die obige Implementierung verdeutlicht jedoch das zugrunde liegende Konzept des Stacks, was auch in anderen Programmiersprachen nützlich ist.
Schauen Sie sich auch diese Artikel über Listen an.
Betrachten wir nun die eingebaute ‚deque‘ aus dem Modul ‚collections‘, die ebenfalls als Stack verwendet werden kann.
#2. Verwendung von Deque aus Collections
Die ‚deque‘ ist als doppelseitige Warteschlange implementiert. Sie ermöglicht das Hinzufügen und Entfernen von Elementen von beiden Seiten. Daher können wir sie auch als Stack verwenden. Wir können sie so nutzen, dass sie dem LIFO-Prinzip des Stacks folgt.
Sie basiert intern auf einer doppelt verketteten Liste. Die Leistung beim Einfügen und Entfernen von Elementen ist somit konstant. Der Zugriff auf Elemente in der Mitte einer verketteten Liste nimmt O(n) Zeit in Anspruch. Für den Stack ist dies nicht relevant, da man nicht auf die Elemente im Inneren des Stacks zugreift.
Bevor wir den Stack mit ‚deque‘ implementieren, betrachten wir die Methoden, die wir dafür verwenden können.
- append(data) – Fügt Daten zum Stack hinzu.
- pop() – Entfernt das oberste Element vom Stack.
Es gibt keine direkte Entsprechung zu den Methoden ‚peek‘ und ‚is_empty‘. Anstelle der ‚peek‘-Methode können wir den gesamten Stack ausgeben. Mit der Methode ‚len‘ können wir überprüfen, ob der Stack leer ist.
Implementieren wir den Stack nun mit ‚deque‘ aus dem Modul ‚collections‘.
from collections import deque ## creating deque object stack = deque() ## checking whether stack is empty or not -> true print(len(stack) == 0) ## pushing the elements stack.append(1) stack.append(2) stack.append(3) stack.append(4) stack.append(5) ## again checking whether stack is empty or not -> false print(len(stack) == 0) ## printing the stack print(stack) ## popping the topmost element -> 5 stack.pop() ## printing the stack print(stack) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the whether stack is empty or not for the last time -> true print(len(stack) == 0)
Das ist alles! Wir haben gelernt, wie man einen Stack mit ‚deque‘ aus dem Modul ‚collections‘ implementiert. Wenn Sie das obige Programm ausführen, erhalten Sie folgende Ausgabe:
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Bisher haben wir zwei verschiedene Möglichkeiten kennengelernt, einen Stack zu implementieren. Gibt es noch weitere? Ja! Wir betrachten im Folgenden eine letzte Möglichkeit.
#3. Verwendung von LifoQueue
Der Name ‚LifoQueue‘ deutet bereits darauf hin, dass sie dem LIFO-Prinzip folgt. Daher können wir sie ebenfalls als Stack verwenden. Sie stammt aus dem Modul ‚queue‘. Die ‚LifoQueue‘ bietet einige nützliche Methoden, die für die Implementierung des Stacks hilfreich sind. Schauen wir sie uns an:
- put(data) – Fügt Daten der Warteschlange hinzu (Push-Operation).
- get() – Entfernt das oberste Element aus der Warteschlange (Pop-Operation).
- empty() – Gibt an, ob der Stack leer ist.
- qsize() – Gibt die Größe der Warteschlange zurück.
Implementieren wir den Stack nun mit ‚LifoQueue‘ aus dem Modul ‚queue‘.
from queue import LifoQueue
## creating LifoQueue object
stack = LifoQueue()
## checking whether stack is empty or not -> true
print(stack.empty())
## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
## again checking whether stack is empty or not -> false
print(stack.empty())
## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())
## checking the stack size
print("Size", stack.qsize())
print(stack.get())
print(stack.get())
## checking the whether stack is empty or not for the last time -> true
print(stack.empty())
Die Ausführung des obigen Codes liefert folgende Ausgabe:
True False 5 4 3 Size 2 2 1 True
Anwendungsfälle des Stacks
Nachdem Sie sich nun ausreichend Wissen über Stacks angeeignet haben, können wir uns überlegen, wo diese bei der Lösung von Programmierproblemen eingesetzt werden können. Betrachten wir ein konkretes Problem und lösen es mit einem Stack.
Schreiben Sie ein Programm, das für einen gegebenen Ausdruck überprüft, ob die runden, eckigen und geschweiften Klammern korrekt ausbalanciert sind.
Hier sind einige Beispiele:
Eingabe: „[{}]([])“
Ausgabe: Ausgeglichen
Eingabe: „{[}]([])“
Ausgabe: Nicht ausgeglichen
Wir können einen Stack verwenden, um das obige Problem zu lösen. Die einzelnen Schritte sind:
- Erstellen Sie einen Stack zum Speichern der Klammern.
- Wenn die Länge des Ausdrucks ungerade ist, ist der Ausdruck nicht ausgeglichen.
- Iterieren Sie durch den Ausdruck:
- Wenn das aktuelle Zeichen eine öffnende Klammer ( oder { oder [ ist, legen Sie es auf den Stack.
- Wenn das aktuelle Zeichen eine schließende Klammer ) oder } oder ] ist, entfernen Sie das oberste Element vom Stack.
- Wenn das entfernte Element mit der zugehörigen öffnenden Klammer übereinstimmt, fahren Sie fort. Andernfalls sind die Klammern nicht ausgeglichen.
- Wenn der Stack nach der Iteration leer ist, ist der Ausdruck ausgeglichen. Andernfalls ist er nicht ausgeglichen.
Wir können einen Set-Datentyp verwenden, um die Klammerpaare zu prüfen.
## stack
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
def pop(self):
return self.elements.pop()
def peek(self):
return self.elements[-1]
def is_empty(self):
return len(self.elements) == 0
def balance_check(expression):
## checking the length of the expression
if len(expression) % 2 != 0:
## not balanced if the length is odd
return False
## for checking
opening_brackets = set('([{')
pairs = set([ ('(',')'), ('[',']'), ('{','}') ])
## stack initialization
stack = Stack()
## iterating through the given expression
for bracket in expression:
## checking whether the current bracket is opened or not
if bracket in opening_brackets:
## adding to the stack
stack.push(bracket)
else:
## popping out the last bracket from the stack
popped_bracket = stack.pop()
## checking whether popped and current bracket pair
if (popped_bracket, bracket) not in pairs:
return False
return stack.is_empty()
if __name__ == '__main__':
if balance_check('[{}]([])'):
print("Balanced")
else:
print("Not Balanced")
if balance_check('{[}]([])'):
print("Balanced")
else:
print("Not Balanced")
Wir können den Stack nutzen, um viele weitere Probleme zu lösen. Das obige Problem ist nur eines davon. Versuchen Sie, das Stack-Konzept anzuwenden, wann immer Sie es für sinnvoll halten.
Zusammenfassung
Herzlichen Glückwunsch! Sie haben das Tutorial nun abgeschlossen. Ich hoffe, es hat Ihnen genauso viel Spaß gemacht wie mir beim Erstellen. Das war es für dieses Tutorial.
Viel Spaß beim Programmieren 🙂 👨💻