Tutorial zur Python-Stack-Datenstruktur

Implementieren Sie einen LIFO-Stack in Python. Führen Sie unser interaktives Stack-Codebeispiel aus, um Push-, Pop-, Peek- und Kapazitätsgrenzen zu meistern.

Versuchen Sie es im Editor

Übersicht

Ein Stack ist eine lineare Datenstruktur, die dem Last-In-First-Out-Prinzip (LIFO) folgt. Das bedeutet, dass das zuletzt zum Stapel hinzugefügte Element das allererste ist, das entfernt wird, ähnlich wie bei einem Plattenstapel.

Der Stapel unterstützt zwei Hauptoperationen: Push (fügt ein Element oben hinzu) und Pop (entfernt das zuletzt hinzugefügte Element). Darüber hinaus ermöglicht ein Blick- oder Top-Vorgang die Inspektion des oberen Elements, ohne es zu entfernen.

In Python können Stapel einfach mithilfe einer Liste mit den Methoden „.append()“ und „.pop()“ oder mithilfe des Objekts „collections.deque“ erstellt werden, das optimierte doppelendige Warteschlangenoperationen in O(1)-Zeit bietet.

Code- und Ausführungsausgabe

Eine benutzerdefinierte Stack-Implementierung, die die Listenstruktur von Python verwendet, um Push-, Pop- und Peek-Funktionen zu emulieren.

stack.py

Versuchen Sie es im Editor

class Stack:
    def __init__(self):
        self.items = []
        
    def is_empty(self):
        return len(self.items) == 0
        
    def push(self, item):
        self.items.append(item)
        print(f"Pushed: {item}")
        
    def pop(self):
        if self.is_empty():
            return "Underflow: Stack is empty"
        popped = self.items.pop()
        print(f"Popped: {popped}")
        return popped
        
    def peek(self):
        if self.is_empty():
            return "Stack is empty"
        return self.items[-1]
        
    def size(self):
        return len(self.items)

# Initialize stack
stack = Stack()
stack.push("Apples")
stack.push("Bananas")
stack.push("Cherries")

print(f"Current Stack Size: {stack.size()}")
print(f"Top Element (Peek): {stack.peek()}")

stack.pop()
print(f"Stack after Pop: {stack.items}")

Terminal-Ausgabe

Pushed: Apples
Pushed: Bananas
Pushed: Cherries
Current Stack Size: 3
Top Element (Peek): Cherries
Popped: Cherries
Stack after Pop: ['Apples', 'Bananas']

Schrittweise Umsetzung

Verwalten von Rückgängig-Funktionen in Softwaresystemen
Syntaxanalyse und Klammerprüfung in Compilern
Verfolgen von Ausführungsaufrufstapeln während der Rekursion in Engines

Häufig gestellte Fragen

Warum wird „collections.deque“ einer normalen Liste für Stacks vorgezogen?

Obwohl Listen praktisch sind, handelt es sich im Grunde genommen um dynamische Arrays. Wenn sich die Größe ändert, kann die Neuzuweisung des Speichers O(n) Zeit in Anspruch nehmen. Das Deque-Objekt verwendet eine doppelt verknüpfte Listenarchitektur, die O(1)-Pushes und -Pops garantiert.

Können Stapel in Python überlaufen?

Eine Standard-Stack-Klasse in Python, die Listenarrays verwendet, wächst, bis sie den gesamten verfügbaren Systemspeicher belegt. Der Rekursionsstapel in Python hat jedoch ein Standardlimit (normalerweise 1000), um zu verhindern, dass Endlosschleifen den Interpreter zum Absturz bringen.