Python Language
stack
Zoeken…
Invoering
Een stapel is een container met objecten die volgens het LIFO-principe (last-in first-out) worden ingevoegd en verwijderd. In de pushdown-stacks zijn slechts twee bewerkingen toegestaan: duw het item in de stapel en haal het item uit de stapel . Een stapel is een gegevensstructuur met beperkte toegang - elementen kunnen alleen bovenaan worden toegevoegd en van de stapel worden verwijderd . Hier is een structurele definitie van een stapel: een stapel is leeg of bestaat uit een bovenkant en de rest is een stapel.
Syntaxis
- stack = [] # Maak de stapel
- stack.append (object) # Voeg object toe aan de bovenkant van de stapel
- stack.pop () -> object # Retourneer het bovenste object uit de stapel en verwijder het ook
- list [-1] -> object # Kijk naar het bovenste object zonder het te verwijderen
Opmerkingen
Van Wikipedia :
In de informatica is een stapel een abstract gegevenstype dat dient als een verzameling elementen, met twee hoofdbewerkingen: push , waarmee een element aan de verzameling wordt toegevoegd, en pop , waarmee het meest recent toegevoegde element wordt verwijderd dat nog niet is verwijderd.
Vanwege de manier waarop hun elementen worden benaderd, worden stacks ook wel Last-In, First-Out ( LIFO ) -stapels genoemd .
In Python kan men lijsten gebruiken als stapels met append() als push en pop() als pop-operaties. Beide bewerkingen draaien in constante tijd O (1).
De deque datastructuur van de Python kan ook worden gebruikt als een stapel. Vergeleken met lijsten, staan deque 's push- en pop-bewerkingen toe met constante tijdcomplexiteit aan beide uiteinden.
Een stapelklasse maken met een lijstobject
Met behulp van een list object kunt u een volledig functionele generieke Stack met helper methoden zoals gluren en te controleren of de stapel is leeg te maken. Ga naar de officiële python documentatie voor het gebruik van list als Stack hier .
#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
Een voorbeeldrun:
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())
Output:
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
Haakjes ontleden
Stapels worden vaak gebruikt voor het parseren. Een eenvoudige parseringstaak is om te controleren of een reeks haakjes overeenkomt.
De tekenreeks ([]) komt bijvoorbeeld overeen, omdat de buitenste en binnenste haakjes paren vormen. ()<>) komt niet overeen, omdat de laatste ) geen partner heeft. ([)] komt ook niet overeen, omdat paren zich geheel binnen of buiten andere paren moeten bevinden.
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()