6.1 Definition eines Stacks und seine Eigenschaften
Stack — das ist eine abstrakte Datenstruktur, die eine Sammlung von Elementen darstellt, organisiert nach dem Prinzip "zuletzt rein — zuerst raus" (Last In, First Out, LIFO). Ein Stack lässt sich mit einem Bücherstapel vergleichen: das zuletzt hinzugefügte Buch liegt oben auf dem Stapel und wird als erstes entfernt/genommen.
Eigenschaften eines Stacks:
- LIFO (Last In, First Out): Das zuletzt hinzugefügte Element wird als erstes extrahiert.
- Begrenzte Operationen: Im Stack werden nur hinzufügen (push), entfernen (pop) und betrachten (peek) des Elements an der Spitze unterstützt.
- Einseitiger Zugriff: Der Zugriff auf die Elemente ist nur von der Spitze des Stacks aus möglich.
- Einfachheit der Implementierung: Ein Stack kann leicht mit einem Array oder einer verketteten Liste realisiert werden.
- Speicherverwaltung: Temporäre Daten oder Zustände können in umgekehrter Reihenfolge der Hinzufügung gespeichert und abgerufen werden.
LIFO-Prinzip:
- Hinzufügen eines Elements (push): Ein neues Element wird oben auf den Stack gelegt.
- Entfernen eines Elements (pop): Das zuletzt hinzugefügte Element wird von der Spitze des Stacks entfernt.
- Ansehen der Spitze (peek): Ermöglicht das Anzeigen des Elements an der Spitze des Stacks, ohne es zu entfernen.
Elemente des Stacks werden von einer Seite hinzugefügt und entfernt, die als Spitze (top) bezeichnet wird. Daher befindet sich das zuletzt hinzugefügte Element immer an der Spitze und wird als erstes entfernt.
6.2 Grundlegende Operationen
Grundlegende Operationen: push, pop, peek
Operation push: Fügt ein neues Element an der Spitze des Stacks hinzu.
Zeitkomplexität: O(1).
Beispiel einer Stack-Emulation in Python mit der Klasse list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # Ausgabe: [10, 20]
Operation pop: Entfernt und gibt das Element an der Spitze des Stacks zurück.
Zeitkomplexität: O(1).
Beispiel einer Stack-Emulation in Python mit der Klasse list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # Ausgabe: 20
print(stack) # Ausgabe: [10]
Operation peek: Gibt das Element an der Spitze des Stacks zurück, ohne es zu entfernen.
Zeitkomplexität: O(1).
Beispiel der Implementierung:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # Ausgabe: 10
6.3 Beispiele für die Verwendung eines Stacks
Lass uns einige Beispiele für die Verwendung eines Stacks anführen:
Verwaltung von Funktionsaufrufen
In Python wird der Stack verwendet, um Funktionen während der Ausführung des Programms zu verfolgen. Jedes Mal, wenn eine Funktion aufgerufen wird, werden ihre Rücksprungadresse und lokalen Variablen in den Stack gelegt. Wenn die Funktion ihre Ausführung beendet, kehrt die Steuerung zu der Funktion zurück, die sie aufgerufen hat, und die Daten werden aus dem Stack abgerufen.
Beispiel für die Verwendung des Aufrufstapels:
In diesem Beispiel verwenden die rekursiven Aufrufe der Funktion factorial den Aufrufstapel, um den Status jedes Aufrufs zu speichern, bis die Basisbedingung (n == 1) erreicht ist.
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # Ausgabe: 120
Rückgängigmachen von Operationen (Undo)
Der Stack wird verwendet, um die Undo-Funktion in Texteditoren und anderen Anwendungen zu implementieren. Wenn der Benutzer eine Aktion ausführt, wird diese im Stack gespeichert. Bei der Ausführung der Undo-Operation wird die letzte Aktion aus dem Stack abgerufen und rückgängig gemacht.
Beispiel für die Verwendung des Stacks zum Rückgängigmachen von Operationen:
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# Beispiel der Verwendung:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # Ausgabe: "Hello World"
editor.undo()
print(editor.text) # Ausgabe: "Hello"
editor.undo()
print(editor.text) # Ausgabe: ""
GO TO FULL VERSION