Forstå Stack Implementering i Python

by
Tweet
Share
Share
Pin
0 Shares

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.

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.

  Lag et slektstre med disse 8 beste verktøyene

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å.

  Jeg betalte $42 for at Apple skulle installere en skjermbeskytter, og jeg er ikke engang gal

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.

  Hvordan finne og bruke kobber i Minecraft

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 🙂 👨‍💻