Forstå Stack Implementering i Python
Datastrukturer spiller en nøkkelrolle i programmeringsverdenen. De hjelper oss med å organisere dataene våre på en måte som kan brukes effektivt. Stakken er en av de enkleste datastrukturene.
La oss lære om stabelen og dens implementering i Python.
Innholdsfortegnelse
Hva er en stabel?
En stabel ligner på haugen med bøker, stoler osv., i det virkelige liv. Og den følger sist inn/først ut (LIFO)-prinsippet. Det er den enkleste datastrukturen. La oss se scenariet med et eksempel fra den virkelige verden.
La oss si at vi har en haug med bøker som følger.
Når vi vil ha den tredje boken fra toppen da, må vi fjerne de to første bøkene fra toppen for å ta ut den tredje boken. Her går den øverste boken sist i bunken og kommer først i bunken. Datastrukturstabelen følger samme prinsipp Last-in/First-out (LIFO) i programmering.
Operasjoner i stabel
Det er hovedsakelig to operasjoner i en stabel
1. push(data)
Legger til eller skyver dataene inn i stabelen.
2. pop()
Fjerner eller spretter det øverste elementet fra stabelen.
Se illustrasjonene nedenfor av push- og pop-operasjoner.
Vi skal skrive noen hjelpefunksjoner som hjelper oss å få mer info om stabelen.
La oss se dem.
kikke()
Returnerer det øverste elementet fra stabelen.
er tom()
Returnerer om stabelen er tom eller ikke.
Nok konseptuelle aspekter ved stabeldatastrukturen. La oss hoppe inn i implementeringen uten videre.
Jeg antar at du har python installert på PC-en din, hvis ikke, kan du også prøve den elektroniske kompilatoren.
Stackimplementering
Implementering av stack er den enkleste sammenlignet med andre implementeringer av datastrukturer. Vi kan implementere en stack på flere måter i Python.
La oss se alle én etter én.
#1. Liste
Vi skal implementere stabelen ved å bruke listen i en klasse. La oss se trinnvis implementering av stabelen.
Trinn 1: Skriv en klasse som heter Stack.
class Stack: pass
Trinn 2: Vi må opprettholde dataene i en liste. La oss legge til en tom liste i Stack-klassen med navneelementer.
class Stack: def __init__(self): self.elements = []
Trinn 3: For å skyve elementene inn i stabelen trenger vi en metode. La oss skrive en push-metode som tar data som et argument og legge det til elementlisten.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data
Trinn 4: På samme måte, la oss skrive popmetoden som spretter ut det øverste elementet fra stabelen. Vi kan bruke pop-metoden for listedatatypen.
class Stack: ## ... def pop(self): return self.elements.pop()
Vi har fullført stackimplementeringen med de nødvendige operasjonene. La oss nå legge til hjelpefunksjonene for å få mer informasjon om stabelen.
Trinn 5: Vi kan få det øverste elementet fra stabelen ved å bruke den negative indeksen. Koden elementet[-1] returnerer den siste av listen. Det er det øverste elementet i stabelen i vårt tilfelle.
class Stack: ## ... def peek(self): return self.elements[-1]
Trinn 6: Hvis lengden på elementlisten er 0, er stabelen tom. La oss skrive en metode som returnerer om elementet er tomt eller ikke.
class Stack: ## ... def is_empty(self): return len(self.elements) == 0
Vi har fullført implementeringen av stabelen ved å bruke listedatatypen.
Åh! vent, vi implementerte det nettopp. Men så ikke hvordan jeg skulle bruke den. Hvordan bruke den da?
Kom, la oss se hvordan du implementerer det. Vi må lage et objekt for at Stack-klassen skal bruke det. Det er ikke noe å snakke om. La oss gjøre det først.
class Stack: ## ... if __name__ == '__main__': stack = Stack()
Vi har laget stabelobjektet og klar til å bruke det. La oss følge trinnene nedenfor for å teste stabeloperasjoner.
- Sjekk om stabelen er tom eller ikke ved å bruke metoden is_empty. Det bør returnere True.
- Skyv tallene 1, 2, 3, 4, 5 inn i stabelen ved å bruke push-metoden.
- Metoden is_empty skal returnere False. Sjekk det.
- Skriv ut det øverste elementet ved å bruke kikkmetoden.
- Pop elementet fra stabelen ved å bruke pop-metoden.
- Sjekk kikkelementet. Det skal returnere element 4.
- Ta nå alle elementene fra stabelen.
- Metoden is_empty skal returnere True. Sjekk det.
Vår stackimplementering er fullført hvis den består alle trinnene ovenfor. Prøv å skrive koden for trinnene ovenfor.
Skrev du koden? Nei, ikke bekymre deg, sjekk koden nedenfor.
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())
Hurra! vi har fullført stackimplementeringen fra bunnen av ved å bruke listedatatypen. Du vil se utdataene som nevnt nedenfor hvis du kjører koden ovenfor.
True False 5 4 True
Vi kan direkte bruke listedatatypen som en stabel. Implementeringen ovenfor av stack hjelper deg å forstå stackimplementeringen i andre programmeringsspråk også.
Du kan også sjekke ut disse listerelaterte artiklene.
La oss se den innebygde dekken fra samlingens innebygde modul som kan fungere som en stabel.
#2. deque fra samlinger
Den er implementert som en dobbel-ended kø. Siden den støtter tillegg og fjerning av elementer fra begge ender. Derfor kan vi bruke den som en stabel. Vi kan få den til å følge stabelens LIFO-prinsipp.
Den er implementert ved hjelp av andre datastrukturer kalt den dobbeltkoblede listen. Så ytelsen til innsetting og sletting av elementer er konsekvent. Å få tilgang til elementer fra den midterste koblede listen tok O(n) tid. Vi kan bruke den som en stabel da det ikke er nødvendig å få tilgang til midtelementene fra stabelen.
Før du implementerer stabelen, la oss se metodene som brukes for å implementere stabelen ved hjelp av køen.
- append(data) – brukes til å skyve dataene til stabelen
- pop() – brukes til å fjerne det øverste elementet fra stabelen
Det finnes ingen alternative metoder for kikk og er_tom. Vi kan skrive ut hele stabelen i stedet for kikkmetoden. Deretter kan vi bruke len-metoden for å sjekke om stabelen er tom eller ikke.
La oss implementere stabelen ved å bruke deque fra samlingsmodulen.
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 er det. Vi har lært hvordan du implementerer stack ved hjelp av deque fra samlingens innebygde modul. Du vil få utdata som nevnt nedenfor hvis du kjører programmet ovenfor.
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Til nå har vi sett to måter å implementere stabelen på. Er det noen andre måter å implementere en stack på? Ja! La oss se den siste måten å implementere en stabel på i denne opplæringen.
#3. LifoQueue
Selve navnet LifoQueue sier at det følger LIFO-prinsippet. Derfor kan vi bruke den som en stabel uten tvil. Det er fra den innebygde modulkøen. LifoQueue gir noen nyttige metoder som er nyttige i stabelimplementeringen. La oss se dem
- put(data) – legger til eller skyver dataene til køen
- get() – fjerner eller spretter det øverste elementet fra køen
- empty() – returnerer om stabelen er tom eller ikke
- qsize() – returnerer lengden på køen
La oss implementere stabelen ved å bruke LifoQueue fra kømodulen.
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())
Du vil få utdataene nevnt nedenfor hvis du kjører programmet ovenfor uten å endre det.
True False 5 4 3 Size 2 2 1 True
Anvendelse av Stack
Nå har du tilstrekkelig kunnskap om stabler til å bruke det i programmeringsproblemer. La oss se et problem og løse det ved hjelp av en stabel.
Gitt et uttrykk, skriv et program for å sjekke om parentesene, klammeparentesene, krøllete klammeparentesene er riktig balansert eller ikke.
La oss se noen eksempler.
Inndata: «[{}]([])»
Utgang: Balansert
Inndata: «{[}]([])»
Utgang: Ikke balansert
Vi kan bruke stabelen til å løse problemet ovenfor. La oss se fremgangsmåten for å løse problemet.
- Lag en stabel for å lagre karakterene.
- Hvis lengden på uttrykket er oddetall, er uttrykket Ikke balansert
- Iterer gjennom det gitte uttrykket.
- Hvis det gjeldende tegnet er åpningsparentesen fra ( eller { eller [, then push it to stack.
- Else if the current character is a closing bracket ) or } or ]og sprett deretter fra stabelen.
- Hvis tegnet som vises, samsvarer med startparentesen, fortsett ellers er ikke parentes balansert.
- Etter iterasjonen, hvis stabelen er tom, er ligningen Balansert, ellers er ligningen Ikke Balansert.
Vi kan bruke den angitte datatypen for sjekk 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 bruke stabelen til å løse mange flere problemer. Problemet ovenfor er ett av dem. Prøv å bruke stabelkonseptet der du synes det passer best for deg.
Konklusjon
Jaja! Du har fullført opplæringen. Jeg håper du likte veiledningen like mye som jeg gjør mens du laget den. Det var alt for opplæringen.
Lykke til med koding 🙂 👨💻