Forståelse af stakimplementering i Python

Datastrukturer spiller en nøglerolle i programmeringsverdenen. De hjælper os med at organisere vores data på en måde, der kan bruges effektivt. Stakken er en af ​​de enkleste datastrukturer.

Lad os lære om stakken og dens implementering i Python.

Hvad er en stak?

En stak ligner bunken af ​​bøger, stole osv.., i det virkelige liv. Og det følger Last-in/First-out (LIFO)-princippet. Det er den enkleste datastruktur. Lad os se scenariet med et eksempel fra den virkelige verden.

Lad os sige, at vi har en bunke bøger som følger.

Når vi vil have den tredje bog fra toppen, så skal vi fjerne de første to bøger fra toppen for at tage den tredje bog ud. Her går den øverste bog sidst i bunken og kommer først i bunken. Datastrukturstakken følger samme princip Last-in/First-out (LIFO) i programmering.

Operationer i stakken

Der er hovedsageligt to operationer i en stak

1. push(data)

Tilføjer eller skubber data ind i stakken.

2. pop()

Fjerner eller springer det øverste element fra stakken.

Se nedenstående illustrationer af push og pop operationer.

Vi vil skrive nogle hjælpefunktioner, der hjælper os med at få mere info om stakken.

Lad os se dem.

kig()

Returnerer det øverste element fra stakken.

er tom()

Returnerer, om stakken er tom eller ej.

Nok konceptuelle aspekter af stakdatastrukturen. Lad os springe ind i implementeringen uden videre.

Jeg antager, at du har python installeret på din pc, hvis ikke, kan du også prøve online-kompileren.

Stakimplementering

Implementering af stak er den nemmeste sammenlignet med andre implementeringer af datastrukturer. Vi kan implementere en stak på flere måder i Python.

Lad os se dem alle én efter én.

#1. Liste

Vi skal implementere stakken ved hjælp af listen i en klasse. Lad os se den trinvise implementering af stakken.

Trin 1: Skriv en klasse kaldet Stak.

class Stack:
	pass

Trin 2: Vi skal vedligeholde dataene på en liste. Lad os tilføje en tom liste i Stack-klassen med navneelementer.

class Stack:
	def __init__(self):
		self.elements = []

Trin 3: For at skubbe elementerne ind i stakken har vi brug for en metode. Lad os skrive en push-metode, der tager data som et argument og tilføje det til elementlisten.

class Stack:
	def __init__(self):
		self.elements = []

	def push(self, data):
		self.elements.append(data)
		return data

Trin 4: Lad os på samme måde skrive pop-metoden, der springer det øverste element ud fra stakken. Vi kan bruge pop-metoden for listedatatypen.

class Stack:
	## ...
	def pop(self):
		return self.elements.pop()

Vi har afsluttet stakimplementeringen med de nødvendige operationer. Lad os nu tilføje hjælpefunktionerne for at få mere information om stakken.

Trin 5: Vi kan få det øverste element fra stakken ved hjælp af det negative indeks. Kodeelementet [-1] returnerer den sidste af listen. Det er det øverste element i stakken i vores tilfælde.

class Stack:
	## ...

	def peek(self):
		return self.elements[-1]

Trin 6: Hvis længden af ​​elementlisten er 0, så er stakken tom. Lad os skrive en metode, der returnerer, om elementet er tomt eller ej.

class Stack:
	## ...
	def is_empty(self):
		return len(self.elements) == 0

Vi har gennemført implementeringen af ​​stakken ved hjælp af listedatatypen.

Åh! vent, vi har lige implementeret det. Men kunne ikke se hvordan man brugte det. Hvordan bruger man det så?

Kom, lad os se, hvordan du implementerer det. Vi skal oprette et objekt for at Stack-klassen kan bruge det. Det er ikke nogen stor sag. Lad os gøre det først.

class Stack: 
    ## ...

if __name__ == '__main__':
    stack = Stack()

Vi har oprettet stakobjektet og er klar til at bruge det. Lad os følge nedenstående trin for at teste stakoperationer.

• Tjek, om stakken er tom eller ej ved at bruge metoden is_empty. Det burde returnere True.
• Skub tallene 1, 2, 3, 4, 5 ind i stakken ved hjælp af push-metoden.
• Metoden is_empty skulle returnere False. Tjekke det.
• Udskriv det øverste element ved hjælp af kigmetoden.
• Pop elementet fra stakken ved hjælp af pop-metoden.
• Tjek kig-elementet. Det skal returnere element 4.
• Pluk nu alle elementerne fra stakken.
• Metoden is_empty skulle returnere True. Tjekke det.

Vores stackimplementering er fuldført, hvis den består alle ovenstående trin. Prøv at skrive koden til ovenstående trin.

Har du skrevet koden? Nej, bare rolig, tjek 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 fuldført stakimplementeringen fra bunden ved hjælp af listedatatypen. Du vil se output som nævnt nedenfor, hvis du kører ovenstående kode.

True
False
5
4
True

Vi kan direkte bruge listedatatypen som en stak. Ovenstående implementering af stak hjælper dig med at forstå stakimplementeringen i andre programmeringssprog.

Du kan også tjekke disse listerelaterede artikler.

Lad os se den indbyggede deque fra samlingens indbyggede modul, som kan fungere som en stak.

#2. deque fra samlinger

Det er implementeret som en dobbeltkø. Da det understøtter tilføjelse og fjernelse af elementer fra begge ender. Derfor kan vi bruge det som en stak. Vi kan få det til at følge stablens LIFO-princip.

Den implementeres ved hjælp af andre datastrukturer kaldet den dobbeltforbundne liste. Så udførelsen af ​​indsættelse og sletning af elementer er konsekvent. Adgang til elementer fra den midterste linkede liste tog O(n) tid. Vi kan bruge den som en stak, da der ikke er behov for at få adgang til de midterste elementer fra stakken.

Før du implementerer stakken, lad os se de metoder, der bruges til at implementere stakken ved hjælp af køen.

• append(data) – bruges til at skubbe data til stakken
• pop() – bruges til at fjerne det øverste element fra stakken

Der er ingen alternative metoder til kig og is_empty. Vi kan printe hele stakken i stedet for kigmetoden. Dernæst kan vi bruge len-metoden til at kontrollere, om stakken er tom eller ej.

Lad os implementere stakken ved hjælp af deque fra samlingsmodulet.

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 man implementerer stack ved hjælp af deque fra samlingens indbyggede modul. Du vil få output som nævnt nedenfor, hvis du udfører ovenstående program.

True
False
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
True

Indtil nu har vi set to måder at implementere stakken på. Er der andre måder at implementere en stack på? Ja! Lad os se den sidste måde at implementere en stak i denne vejledning.

#3. LifoQueue

Selve navnet LifoQueue siger, at det følger LIFO-princippet. Derfor kan vi uden tvivl bruge den som en stak. Det er fra den indbyggede modulkø. LifoQueue giver nogle praktiske metoder, der er nyttige i stakimplementeringen. Lad os se dem

• put(data) – tilføjer eller skubber data til køen
• get() – fjerner eller åbner det øverste element fra køen
• empty() – returnerer om stakken er tom eller ej
• qsize() – returnerer længden af ​​køen

Lad os implementere stakken ved hjælp af LifoQueue fra kømodulet.

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 får outputtet nævnt nedenfor, hvis du udfører ovenstående program uden at ændre det.

True
False
5
4
3
Size 2
2
1
True

Anvendelse af stak

Nu har du tilstrækkelig viden om stakke til at anvende det i programmeringsproblemer. Lad os se et problem og løse det ved hjælp af en stak.

Givet et udtryk, skriv et program for at kontrollere, om parenteser, bøjler, bøjler er afbalanceret korrekt eller ej.

Lad os se nogle eksempler.

Input: “[{}]([])”

Output: Balanceret

Input: “{[}]([])”

Output: Ikke afbalanceret

Vi kan bruge stakken til at løse ovenstående problem. Lad os se trinene til at løse problemet.

• Opret en stak for at gemme karaktererne.
• Hvis længden af ​​udtrykket er ulige, er udtrykket Ikke afbalanceret
• Gentag gennem det givne udtryk.
  • Hvis det aktuelle tegn er den indledende parentes fra ( eller { eller [, then push it to stack.
  • Else if the current character is a closing bracket ) or } or ]og pop derefter fra stakken.
  • Hvis det viste tegn stemmer overens med startparentesen, så fortsæt, ellers er paranteser ikke afbalancerede.
• Efter iterationen, hvis stakken er tom, er ligningen Balanceret, ellers er ligningen Ikke Balanceret.

Vi kan gøre brug af den indstillede datatype til kontrol af parentes match.

## 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 bruge stakken til at løse mange flere problemer. Ovenstående problem er et af dem. Prøv at anvende stak-konceptet, hvor du synes, det passer dig bedst.

Konklusion

Jah! Du har gennemført selvstudiet. Jeg håber, du nød tutorialen lige så meget, som jeg gør, mens du lavede den. Det var det for tutorialen.

God kodning 🙂 👨‍💻