Datastrukturer utgör en grundläggande del av programmeringen. De möjliggör effektiv organisering av data för snabbare och smidigare användning. En av de mest grundläggande datastrukturerna är stacken.
Låt oss utforska stackens funktioner och se hur den implementeras i Python.
Vad är en stack?
En stack kan jämföras med en stapel av exempelvis böcker eller stolar i verkligheten. Den följer principen ”sist in, först ut” (LIFO – Last-In/First-Out). Detta gör den till en av de mest lättförståeliga datastrukturerna. Låt oss ta ett praktiskt exempel.
Föreställ dig en stapel med böcker.
Om vi behöver den tredje boken uppifrån, måste vi först ta bort de två översta böckerna. Den översta boken, som lades till sist, tas alltså bort först. Inom programmering följer stackdatastrukturen samma LIFO-princip.
Operationer inom stacken
Det finns främst två grundläggande operationer i en stack:
1. push(data)
Lägger till ett element, data, ovanpå stacken.
2. pop()
Tar bort och returnerar det översta elementet från stacken.
Nedan följer visualiseringar som illustrerar push- och pop-operationer.
Vi kommer även att definiera några hjälpfunktioner som ger oss mer information om stackens tillstånd.
Låt oss se dessa funktioner.
peek()
Returnerar det översta elementet i stacken utan att ta bort det.
is_empty()
Returnerar sant om stacken är tom, annars falskt.
Nu har vi täckt den teoretiska delen av stackar. Dags att hoppa in i implementeringen!
Jag förutsätter att Python är installerat på din dator. Om inte, kan du använda en online-kompilator.
Implementera stacken
Att implementera en stack är relativt enkelt jämfört med andra datastrukturer. Det finns flera sätt att göra det i Python.
Låt oss utforska dessa alternativ.
#1. Använda en lista
Vi implementerar stacken med hjälp av en lista inom en klass. Här följer en steg-för-steg-guide:
Steg 1: Definiera en klass som heter Stack.
class Stack: pass
Steg 2: Vi använder en lista för att lagra stackens element. Vi lägger till en tom lista i Stack-klassen som ett attribut som vi kallar ”elements”.
class Stack: def __init__(self): self.elements = []
Steg 3: Vi behöver en metod för att lägga till element i stacken, en ”push”-metod. Den tar data som ett argument och lägger till det i ”elements”-listan.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data
Steg 4: Vi skapar också en ”pop”-metod som tar bort och returnerar det översta elementet från stacken. Vi kan använda listans inbyggda ”pop”-metod.
class Stack: ## ... def pop(self): return self.elements.pop()
Nu har vi implementerat stacken med de nödvändiga operationerna. Låt oss lägga till hjälpfunktionerna för att få mer information om stacken.
Steg 5: Vi kan komma åt det översta elementet via negativ indexering av listan. Koden elements[-1] returnerar det sista elementet i listan, vilket i vårt fall är det översta elementet i stacken.
class Stack: ## ... def peek(self): return self.elements[-1]
Steg 6: Om ”elements”-listans längd är noll, är stacken tom. Vi skapar en metod som returnerar sant om stacken är tom och falskt annars.
class Stack: ## ... def is_empty(self): return len(self.elements) == 0
Nu har vi färdigställt implementeringen av stacken med hjälp av listdatatypen.
Vänta lite! Vi har precis implementerat den, men hur använder vi den? Låt oss se hur vi går till väga.
För att använda Stack-klassen måste vi först skapa ett objekt av den. Det är inte svårt, låt oss börja med det.
class Stack:
## ...
if __name__ == '__main__':
stack = Stack()
Vi har nu skapat ett stackobjekt och är redo att använda det. Låt oss följa stegen nedan för att testa stackoperationerna:
- Kontrollera om stacken är tom med ”is_empty”-metoden. Den bör returnera ”True”.
- Lägg till talen 1, 2, 3, 4, 5 i stacken med ”push”-metoden.
- ”is_empty”-metoden bör nu returnera ”False”. Kontrollera detta.
- Skriv ut det översta elementet med ”peek”-metoden.
- Ta bort det översta elementet från stacken med ”pop”-metoden.
- Kontrollera det översta elementet igen med ”peek”. Det bör returnera 4.
- Ta bort alla element från stacken.
- ”is_empty”-metoden bör nu returnera ”True”. Kontrollera även detta.
Vår stackimplementering är korrekt om den passerar alla dessa steg. Försök att skriva koden för att genomföra ovanstående steg.
Har du skrivit koden? Om inte, oroa dig inte, se koden nedan.
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
def pop(self):
return self.elements.pop()
def peek(self):
return self.elements[-1]
def is_empty(self):
return len(self.elements) == 0
if __name__ == '__main__':
stack = Stack()
## checking is_empty method -> true
print(stack.is_empty())
## pushing the elements
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
## again checking is_empty method -> false
print(stack.is_empty())
## printing the topmost element of the stack -> 5
print(stack.peek())
## popping the topmost element -> 5
stack.pop()
## checking the topmost element using peek method -> 4
print(stack.peek())
## popping all the elements
stack.pop()
stack.pop()
stack.pop()
stack.pop()
## checking the is_empty method for the last time -> true
print(stack.is_empty())
Bra jobbat! Vi har implementerat stacken från grunden med hjälp av listor. Om du kör ovanstående kod får du utdata enligt nedan:
True False 5 4 True
Det går även att använda listdatatypen direkt som en stack. Den ovanstående implementeringen hjälper dig att förstå hur stackar implementeras i andra programmeringsspråk.
Du kan även utforska dessa relaterade artiklar om listor.
Låt oss nu undersöka den inbyggda ”deque” från modulen ”collections”, som också kan användas som en stack.
#2. ”deque” från ”collections”
”deque” (double-ended queue) implementeras som en dubbelkö. Eftersom den stödjer tillägg och borttagning av element från båda ändar, kan vi använda den som en stack genom att följa LIFO-principen.
Den implementeras med hjälp av en annan datastruktur: dubbellänkade listor. Detta gör prestandan för att lägga till och ta bort element konsekvent. Att komma åt element i mitten av en länkad lista tar O(n) tid. Vi kan använda ”deque” som stack eftersom vi inte behöver komma åt element i mitten.
Innan vi implementerar stacken, låt oss se de metoder som används för att implementera stacken med hjälp av ”deque”:
- ”append(data)” – används för att lägga till elementet ”data” i stacken.
- ”pop()” – används för att ta bort det översta elementet från stacken.
Det finns inga direkta motsvarigheter till ”peek” och ”is_empty”. Vi kan skriva ut hela stacken istället för att använda en ”peek”-metod. För att kontrollera om stacken är tom eller inte, kan vi använda ”len”-metoden.
Låt oss implementera stacken med ”deque” från modulen ”collections”:
from collections import deque ## creating deque object stack = deque() ## checking whether stack is empty or not -> true print(len(stack) == 0) ## pushing the elements stack.append(1) stack.append(2) stack.append(3) stack.append(4) stack.append(5) ## again checking whether stack is empty or not -> false print(len(stack) == 0) ## printing the stack print(stack) ## popping the topmost element -> 5 stack.pop() ## printing the stack print(stack) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the whether stack is empty or not for the last time -> true print(len(stack) == 0)
Det är allt! Vi har lärt oss hur man implementerar en stack med ”deque” från modulen ”collections”. Om du kör koden får du utdata enligt nedan:
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Hittills har vi sett två sätt att implementera en stack. Finns det andra sätt? Ja! Låt oss se det sista sättet att implementera en stack i denna handledning.
#3. ”LifoQueue”
Namnet ”LifoQueue” säger allt – den följer LIFO-principen. Därför kan vi utan tvekan använda den som en stack. Den finns i den inbyggda modulen ”queue”. ”LifoQueue” tillhandahåller några metoder som är användbara för stackimplementering. Låt oss undersöka dem:
- ”put(data)” – lägger till elementet ”data” i kön.
- ”get()” – tar bort och returnerar det översta elementet från kön.
- ”empty()” – returnerar sant om stacken är tom och falskt annars.
- ”qsize()” – returnerar längden på kön.
Låt oss implementera en stack med ”LifoQueue” från modulen ”queue”:
from queue import LifoQueue
## creating LifoQueue object
stack = LifoQueue()
## checking whether stack is empty or not -> true
print(stack.empty())
## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
## again checking whether stack is empty or not -> false
print(stack.empty())
## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())
## checking the stack size
print("Size", stack.qsize())
print(stack.get())
print(stack.get())
## checking the whether stack is empty or not for the last time -> true
print(stack.empty())
Om du kör koden ovan utan att ändra den får du utdata enligt nedan:
True False 5 4 3 Size 2 2 1 True
Användning av Stack
Nu har du tillräckligt med kunskap om stackar för att kunna använda dem i programmeringsproblem. Låt oss undersöka ett problem och lösa det med hjälp av en stack.
Givet ett uttryck, skriv ett program för att kontrollera om parenteser, klamrar och hakparenteser är korrekt balanserade eller inte.
Låt oss se några exempel:
Input: ”[{}]([])”
Output: Balanserad
Input: ”{[}]([])”
Output: Ej balanserad
Vi kan använda en stack för att lösa ovanstående problem. Här följer stegen för att lösa problemet:
- Skapa en stack för att lagra tecknen.
- Om längden på uttrycket är udda, är uttrycket inte balanserat.
- Iterera igenom det givna uttrycket:
- Om det aktuella tecknet är en öppnande parentes (, { eller [, lägg till den i stacken.
- Annars, om det aktuella tecknet är en stängande parentes ), } eller ], ta bort det översta elementet från stacken.
- Om det borttagna tecknet matchar den inledande parentesen, fortsätt; annars är inte parenteserna balanserade.
- Efter iterationen, om stacken är tom, är ekvationen balanserad; annars är den inte balanserad.
Vi kan använda datatypen set för att kontrollera matchning av parenteser.
## stack
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
def pop(self):
return self.elements.pop()
def peek(self):
return self.elements[-1]
def is_empty(self):
return len(self.elements) == 0
def balance_check(expression):
## checking the length of the expression
if len(expression) % 2 != 0:
## not balanced if the length is odd
return False
## for checking
opening_brackets = set('([{')
pairs = set([ ('(',')'), ('[',']'), ('{','}') ])
## stack initialization
stack = Stack()
## iterating through the given expression
for bracket in expression:
## checking whether the current bracket is opened or not
if bracket in opening_brackets:
## adding to the stack
stack.push(bracket)
else:
## popping out the last bracket from the stack
popped_bracket = stack.pop()
## checking whether popped and current bracket pair
if (popped_bracket, bracket) not in pairs:
return False
return stack.is_empty()
if __name__ == '__main__':
if balance_check('[{}]([])'):
print("Balanced")
else:
print("Not Balanced")
if balance_check('{[}]([])'):
print("Balanced")
else:
print("Not Balanced")
Vi kan använda stacken för att lösa många fler problem. Ovanstående problem är ett av dem. Försök att tillämpa stackkonceptet där du tycker att det passar bäst.
Sammanfattning
Bra jobbat! Du har kommit till slutet av den här handledningen. Jag hoppas att du har tyckt om den lika mycket som jag. Det var allt för denna gång.
Lycka till med kodningen! 🙂 👨💻