A Stapel ist eine lineare Datenstruktur, die Elemente in a speichert Last-In/First-Out (LIFO) oder First-In/Last-Out (FILO)-Methode. Im Stapel wird ein neues Element an einem Ende hinzugefügt und ein Element nur an diesem Ende entfernt. Die Einfüge- und Löschvorgänge werden oft als Push und Pop bezeichnet.

Die mit dem Stapel verbundenen Funktionen sind:

• leer() – Gibt zurück, ob der Stapel leer ist – Zeitkomplexität: O(1)
• Größe() – Gibt die Größe des Stapels zurück – Zeitkomplexität: O(1)
• top() / peek() – Gibt einen Verweis auf das oberste Element des Stapels zurück – Zeitkomplexität: O(1)
• drücken(a) – Fügt das Element „a“ oben im Stapel ein – Zeitkomplexität: O(1)
• Pop() – Löscht das oberste Element des Stapels – Zeitkomplexität: O(1)

Implementierung:

Es gibt verschiedene Möglichkeiten, einen Stack in Python zu implementieren. Dieser Artikel behandelt die Implementierung eines Stacks mithilfe von Datenstrukturen und Modulen aus der Python-Bibliothek.
Stack in Python kann auf folgende Weise implementiert werden:

• Liste
• Sammlungen.deque
• queue.LifoQueue

Implementierung mit Liste:

Die in Python integrierte Datenstrukturliste kann als Stapel verwendet werden. Anstelle von push() wird append() verwendet, um Elemente oben im Stapel hinzuzufügen, während pop() das Element in LIFO-Reihenfolge entfernt.
Leider weist die Liste einige Mängel auf. Das größte Problem besteht darin, dass es mit zunehmendem Wachstum zu Geschwindigkeitsproblemen kommen kann. Die Elemente in der Liste werden nebeneinander im Speicher gespeichert. Wenn der Stapel größer wird als der Speicherblock, der ihn derzeit enthält, muss Python einige Speicherzuweisungen vornehmen. Dies kann dazu führen, dass einige append()-Aufrufe viel länger dauern als andere.

# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

Implementierung mitcollections.deque:

Der Python-Stack kann mithilfe der Deque-Klasse aus dem Collections-Modul implementiert werden. Deque wird gegenüber der Liste in den Fällen bevorzugt, in denen wir schnellere Anhänge- und Popup-Vorgänge von beiden Enden des Containers benötigen, da deque im Vergleich zur Liste, die O(n) bereitstellt, eine Zeitkomplexität von O(1) für Append- und Pop-Vorgänge bietet. Zeitkomplexität.

Auf deque werden die gleichen Methoden wie in der Liste verwendet: append() und pop().

# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

Implementierung mithilfe des Warteschlangenmoduls

Das Warteschlangenmodul verfügt auch über eine LIFO-Warteschlange, die im Grunde ein Stapel ist. Daten werden mit der Funktion put() in die Warteschlange eingefügt und get() entnimmt Daten aus der Warteschlange.

In diesem Modul stehen Ihnen verschiedene Funktionen zur Verfügung:

• maximale Größe – Anzahl der in der Warteschlange zulässigen Elemente.
• leer() – Gibt „True“ zurück, wenn die Warteschlange leer ist, andernfalls „False“.
• voll() – Geben Sie „True“ zurück, falls vorhanden maximale Größe Elemente in der Warteschlange. Wenn die Warteschlange mit maxsize=0 (Standardeinstellung) initialisiert wurde, gibt full() niemals True zurück.
• erhalten() – Entfernen Sie ein Element aus der Warteschlange und geben Sie es zurück. Wenn die Warteschlange leer ist, warten Sie, bis ein Artikel verfügbar ist.
• get_nowait() – Geben Sie einen Artikel zurück, wenn einer sofort verfügbar ist, andernfalls wird QueueEmpty ausgelöst.
• setzen(Artikel) – Einen Artikel in die Warteschlange stellen. Wenn die Warteschlange voll ist, warten Sie, bis ein freier Platz verfügbar ist, bevor Sie den Artikel hinzufügen.
• put_nowait(item) – Stellen Sie einen Artikel in die Warteschlange, ohne ihn zu blockieren. Wenn kein freier Slot sofort verfügbar ist, erhöhen Sie QueueFull.
• qsize() – Gibt die Anzahl der Elemente in der Warteschlange zurück.

# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>

0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

Implementierung mithilfe einer einfach verknüpften Liste:

Die verknüpfte Liste verfügt über zwei Methoden addHead(item) und removeHead(), die in konstanter Zeit ausgeführt werden. Diese beiden Methoden eignen sich zur Implementierung eines Stacks.

• getSize() – Ermitteln Sie die Anzahl der Elemente im Stapel.
• ist leer() – Gibt „True“ zurück, wenn der Stapel leer ist, andernfalls „False“.
• spähen() – Geben Sie den obersten Gegenstand im Stapel zurück. Wenn der Stapel leer ist, lösen Sie eine Ausnahme aus.
• push(Wert) – Schieben Sie einen Wert in den Kopf des Stapels.
• Pop() – Entfernen Sie einen Wert im Kopf des Stapels und geben Sie ihn zurück. Wenn der Stapel leer ist, lösen Sie eine Ausnahme aus.

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # Ermittelt die aktuelle Größe des Stapels def getSize(self): return self.size # Prüfe, ob der Stack leer ist def isEmpty(self): return self.size = = 0 # Holen Sie sich das oberste Element des Stapels def peek(self): # Überprüfen Sie die Hygiene, um zu sehen, ob # ein leerer Stapel angezeigt wird. if self.isEmpty(): return None return self.head.next.value # Schieben Sie einen Wert in den Stapel. def push(self, value): node = Node(value) node.next = self.head.next # Den neuen Knoten auf den aktuellen Kopf zeigen lassen self.head.next = node #!!! # Aktualisieren Sie den Kopf als neuen Knoten self.size += 1 # Entfernen Sie einen Wert vom Stapel und geben Sie ihn zurück. def pop(self): if self.isEmpty(): raise Exception('Popping from an empty stack') remove = self.head.next self.head.next = remove.next #!!! geändert self.size -= 1 return remove.value # Treibercode if __name__ == '__main__': stack = Stack() for i in range(1, 11): stack.push(i) print(f' Stack: {stack}') für _ in range(1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # Variablenname geändert print(f'Stack: { stack}')>

Ausgabe

Stack: 10->9->8->7->6->5->4->3->2->1 Pop: 10 Pop: 9 Pop: 8 Pop: 7 Pop: 6 Stapel: 5->4->3->2->1>

Vorteile von Stack:

• Stapel sind einfache Datenstrukturen mit einem klar definierten Satz von Operationen, wodurch sie leicht zu verstehen und zu verwenden sind.
• Stapel sind für das Hinzufügen und Entfernen von Elementen effizient, da diese Operationen eine zeitliche Komplexität von O(1) haben.
• Um die Reihenfolge der Elemente umzukehren, verwenden wir die Stapeldatenstruktur.
• Stacks können verwendet werden, um Undo/Redo-Funktionen in Anwendungen zu implementieren.

Nachteile von Stack:

• Die Größenbeschränkung im Stapel ist ein Nachteil und wenn dieser voll ist, können Sie dem Stapel keine weiteren Elemente hinzufügen.
• Stapel bieten keinen schnellen Zugriff auf andere Elemente als das oberste Element.
• Stapel unterstützen keine effiziente Suche, da Sie Elemente einzeln einfügen müssen, bis Sie das gesuchte Element gefunden haben.