Python Language
Stack
Sök…
Introduktion
En bunt är en behållare med föremål som sätts in och tas bort enligt principen för först in-ut (LIFO). I nedstängningsstackarna är det bara två operationer som är tillåtna: tryck objektet in i bunten och släpp objektet ur bunten . En stack är en databasstruktur med begränsad åtkomst - element kan läggas till och tas bort från stacken endast upptill . Här är en strukturell definition av en bunt: en bunt är antingen tom eller så består den av en topp och resten som är en bunt.
Syntax
- stack = [] # Skapa stacken
- stack.append (object) # Lägg till objekt längst upp i bunten
- stack.pop () -> object # Återgå det bästa objektet från stacken och ta bort det också
- lista [-1] -> objekt # Titta på det bästa objektet utan att ta bort det
Anmärkningar
Från Wikipedia :
Inom datavetenskap är en stack en abstrakt datatyp som fungerar som en samling element, med två huvudoperationer: push , som lägger till ett element i samlingen, och pop , som tar bort det senast tillagda elementet som ännu inte togs bort.
På grund av hur deras element nås är staplar även kända som Last-In, First-Out ( LIFO ) -stackar .
I Python kan man använda listor som staplar med append() som push och pop() som pop-operationer. Båda operationerna körs i konstant tid O (1).
Pythons deque kan också användas som en stack. Jämfört med listor deque push- och pop-operationer med konstant tidskomplexitet från båda ändarna.
Skapa en stackklass med ett listobjekt
Med hjälp av en list objekt kan du skapa en fullt fungerande generisk stack med hjälpare metoder som kikar och kontrollera om stacken är tom. Kolla in de officiella Python-dokumenten för att använda list som Stack här .
#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
Ett exempel kör:
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())
Produktion:
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
Parsing Parentheses
Buntar används ofta för att analysera. En enkel tolkningsuppgift är att kontrollera om en sträng parentes matchar.
Till exempel är strängen ([]) matchande eftersom de yttre och inre parenteserna bildar par. ()<>) matchar inte, eftersom den sista ) har ingen partner. ([)] är inte heller matchande, eftersom par måste vara antingen helt inuti eller utanför andra par.
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()