Python Language
Stapel
Suche…
Einführung
Ein Stapel ist ein Container mit Objekten, die nach dem LIFO-Prinzip (Last-in-First-Out) eingefügt und entfernt werden. In den Pushdown-Stapeln sind nur zwei Vorgänge zulässig: Schieben Sie den Gegenstand in den Stapel und ziehen Sie den Gegenstand aus dem Stapel . Ein Stapel ist eine begrenzte Zugriffsdatenstruktur - Elemente können nur oben hinzugefügt und aus dem Stapel entfernt werden . Hier ist eine strukturelle Definition eines Stapels: Ein Stapel ist entweder leer oder besteht aus einer Oberseite und dem Rest, der ein Stapel ist.
Syntax
- stack = [] # Erstellen Sie den Stapel
- stack.append (object) # Fügt ein Objekt am oberen Rand des Stapels hinzu
- stack.pop () -> object # Gibt das oberste Objekt aus dem Stapel zurück und entfernt es auch
- list [-1] -> object # Sehen Sie das oberste Objekt an, ohne es zu entfernen
Bemerkungen
Von Wikipedia :
In der Informatik ist ein Stapel ein abstrakter Datentyp, der als Auflistung von Elementen dient, mit zwei Hauptoperationen: Push (Hinzufügen), um ein Element zur Auflistung hinzuzufügen, und Pop ( Pop) , um das zuletzt hinzugefügte Element zu entfernen, das noch nicht entfernt wurde.
Aufgrund des Zugriffs auf ihre Elemente werden Stapel auch als Last-In-, First-Out- ( LIFO ) -Stapel bezeichnet .
In Python kann man Listen als Stapel verwenden, mit append() als Push und pop() als Popoperationen. Beide Operationen laufen in konstanter Zeit O (1).
Die deque Datenstruktur des Python kann auch als Stapel verwendet werden. Im Vergleich zu Listen ermöglichen deque s Push- und Pop-Operationen mit konstanter zeitlicher Komplexität von beiden Seiten.
Erstellen einer Stack-Klasse mit einem Listenobjekt
Ein Verwenden list Objekt können Sie einen voll funktionsfähigen generic Stapel mit Hilfsmethoden wie spähen und die Überprüfung erstellen , wenn der Stapel leer ist. Schauen Sie sich die offiziellen Python-Dokumente für die Verwendung der list als Stack hier an .
#define a stack class
class Stack:
def __init__(self):
self.items = []
#method to check the stack is empty or not
def isEmpty(self):
return self.items == []
#method for pushing an item
def push(self, item):
self.items.append(item)
#method for popping an item
def pop(self):
return self.items.pop()
#check what item is on top of the stack without removing it
def peek(self):
return self.items[-1]
#method to get the size
def size(self):
return len(self.items)
#to view the entire stack
def fullStack(self):
return self.items
Ein Beispiellauf:
stack = Stack()
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
print('Pushing integer 1')
stack.push(1)
print('Pushing string "Told you, I am generic stack!"')
stack.push('Told you, I am generic stack!')
print('Pushing integer 3')
stack.push(3)
print('Current stack:', stack.fullStack())
print('Popped item:', stack.pop())
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
Ausgabe:
Current stack: []
Stack empty?: True
Pushing integer 1
Pushing string "Told you, I am generic stack!"
Pushing integer 3
Current stack: [1, 'Told you, I am generic stack!', 3]
Popped item: 3
Current stack: [1, 'Told you, I am generic stack!']
Stack empty?: False
Parsen von Klammern
Stapel werden häufig zum Parsen verwendet. Eine einfache Parsing-Aufgabe besteht darin, zu prüfen, ob eine Klammerfolge übereinstimmt.
Zum Beispiel stimmt die Zeichenfolge ([]) überein, da die äußeren und inneren Klammern Paare bilden. ()<>) stimmt nicht überein, da der letzte ) keinen Partner hat. ([)] stimmt auch nicht überein, da Paare entweder vollständig innerhalb oder außerhalb anderer Paare sein müssen.
def checkParenth(str):
stack = Stack()
pushChars, popChars = "<({[", ">)}]"
for c in str:
if c in pushChars:
stack.push(c)
elif c in popChars:
if stack.isEmpty():
return False
else:
stackTop = stack.pop()
# Checks to see whether the opening bracket matches the closing one
balancingBracket = pushChars[popChars.index(c)]
if stackTop != balancingBracket:
return False
else:
return False
return not stack.isEmpty()