Lær Python-stack: Implementasjon & Eksempler

Datastrukturer: En Dypdykk i Stakken

I programmeringens verden spiller datastrukturer en avgjørende rolle. De er fundamentet for hvordan vi organiserer og administrerer data, noe som har stor innvirkning på effektiviteten til kode. Blant de mest grunnleggende datastrukturene finner vi stakken.

La oss utforske stakken og hvordan vi implementerer den ved hjelp av Python.

Hva kjennetegner en Stakk?

En stakk kan illustreres med en stabel av bøker eller stoler i den fysiske verden. Den opererer etter prinsippet «sist inn, først ut» (LIFO). Dette gjør stakken til en svært enkel, men likevel kraftfull datastruktur. Tenk deg en bunke med bøker; for å få tak i den tredje boken fra toppen, må du fjerne de to øverste først. På samme måte fungerer en stakk innenfor programmering: det elementet som legges til sist, er det første som fjernes.

Stakkoperasjoner

Det finnes primært to basisoperasjoner i en stakk:

1. push(data)

Denne operasjonen tilfører et nytt element, «data», til toppen av stakken.

2. pop()

Denne operasjonen fjerner elementet som ligger øverst i stakken og returnerer det.

For bedre å visualisere disse prosessene, se illustrasjonene under:

I tillegg finnes det hjelpefunksjoner som gir oss mer innsikt i stakkens tilstand:

kikk()

Denne funksjonen returnerer elementet på toppen av stakken uten å fjerne det.

er_tom()

Denne funksjonen sjekker om stakken er tom eller ikke og returnerer en boolsk verdi (True eller False).

Med det konseptuelle grunnlaget på plass, er vi nå klare til å se på implementeringen i praksis.

Implementering av Stakken i Python

Det finnes flere måter å implementere en stakk i Python, hver med sine fordeler og ulemper. La oss utforske noen av de mest vanlige metodene.

#1. Liste som Stakk

En vanlig tilnærming er å bruke en Python-liste som grunnlag for stakken. Ved å kapsle inn listefunksjonaliteten i en klasse, oppnår vi et mer strukturert og lesbart kodebilde.

Trinn 1: Definer en klasse med navnet «Stakk».

class Stakk:
	pass

Trinn 2: Initialiser en tom liste for å holde elementene.

class Stakk:
	def __init__(self):
		self.elementer = []

Trinn 3: Implementer «push»-metoden for å legge til elementer.

class Stakk:
	def __init__(self):
		self.elementer = []

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

Trinn 4: Implementer «pop»-metoden for å fjerne elementer.

class Stakk:
	## ...
	def pop(self):
		return self.elementer.pop()

Trinn 5: Implementer «kikk»-metoden for å se det øverste elementet.

class Stakk:
	## ...

	def kikk(self):
		return self.elementer[-1]

Trinn 6: Implementer «er_tom»-metoden for å sjekke om stakken er tom.

class Stakk:
	## ...
	def er_tom(self):
		return len(self.elementer) == 0

Nå som stakkeklassen er ferdig, la oss se hvordan vi bruker den i praksis.

class Stakk: 
    ## ...

if __name__ == '__main__':
    stakk = Stakk()

Test stakk-operasjonene:

• Sjekk om stakken er tom ved å bruke «er_tom»-metoden.
• Legg til tallene 1, 2, 3, 4, 5 i stakken med «push»-metoden.
• Bekreft at stakken ikke lenger er tom.
• Hent det øverste elementet med «kikk»-metoden.
• Fjern det øverste elementet med «pop»-metoden.
• Sjekk det nye øverste elementet med «kikk».
• Tøm stakken ved å fjerne alle elementer.
• Bekreft at stakken er tom igjen.

Fullstendig kodeeksempel:

class Stakk: 
    def __init__(self): 
        self.elementer = [] 
    
    def push(self, data): 
        self.elementer.append(data) 
        return data 
    
    def pop(self): 
        return self.elementer.pop() 
        
    def kikk(self): 
        return self.elementer[-1] 
        
    def er_tom(self): 
        return len(self.elementer) == 0

if __name__ == '__main__':
    stakk = Stakk()
    
    ## Sjekker om den er tom -> true
    print(stakk.er_tom())

    ## Legger til elementene
    stakk.push(1)
    stakk.push(2)
    stakk.push(3)
    stakk.push(4)
    stakk.push(5)

    ## Sjekker igjen om den er tom -> false
    print(stakk.er_tom())

    ## Skriver ut det øverste elementet -> 5
    print(stakk.kikk())

    ## Fjerner det øverste elementet -> 5
    stakk.pop()

    ## Sjekker det øverste elementet med peek -> 4
    print(stakk.kikk())

    ## Fjerner alle elementene
    stakk.pop()
    stakk.pop() 
    stakk.pop() 
    stakk.pop() 

    ## Sjekker om den er tom for siste gang -> true
    print(stakk.er_tom())

Utdata:

True
False
5
4
True

Det er viktig å huske at vi kan bruke Python sine innebygde lister direkte som en stakk, men den ovennevnte implementasjonen hjelper å forstå prinsippet bedre.

#2. Deque fra Samlingsmodulen

En annen metode er å bruke «deque» (dobbelt-ended kø) fra Pythons «collections»-modul. Den støtter effektiv tilføying og fjerning av elementer fra begge ender, noe som gjør den egnet for å implementere en stakk.

Metodene vi bruker er:

• `append(data)`: Legger til et element på toppen av stakken.
• `pop()`: Fjerner og returnerer det øverste elementet fra stakken.

Siden «deque» ikke har en direkte «kikk»-metode, kan vi skrive ut hele stakken for å se innholdet. For å sjekke om stakken er tom, kan vi bruke `len()`.

Kodeeksempel:

from collections import deque

## Oppretter et deque-objekt
stakk = deque()

## Sjekker om stakken er tom -> true
print(len(stakk) == 0)

## Legger til elementene
stakk.append(1)
stakk.append(2)
stakk.append(3)
stakk.append(4)
stakk.append(5)

## Sjekker om stakken er tom igjen -> false
print(len(stakk) == 0)

## Skriver ut stakken
print(stakk)

## Fjerner det øverste elementet -> 5
stakk.pop()

## Skriver ut stakken
print(stakk)

## Fjerner alle elementene
stakk.pop()
stakk.pop()
stakk.pop()
stakk.pop()

## Sjekker om stakken er tom for siste gang -> true
print(len(stakk) == 0)

Utdata:

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

#3. LifoQueue fra Kømodulen

Den tredje tilnærmingen er å benytte «LifoQueue» (Last In First Out Queue) fra Pythons innebygde «queue»-modul. Som navnet tilsier, følger denne strukturen LIFO-prinsippet og er derfor en direkte stakk-implementering.

Noen av de viktigste metodene:

• `put(data)`: Legger til elementer på toppen av stakken.
• `get()`: Fjerner og returnerer det øverste elementet.
• `empty()`: Sjekker om stakken er tom.
• `qsize()`: Returnerer antall elementer i stakken.

Kodeeksempel:

from queue import LifoQueue

## Oppretter et LifoQueue-objekt
stakk = LifoQueue()

## Sjekker om stakken er tom -> true
print(stakk.empty())

## Legger til elementene
stakk.put(1)
stakk.put(2)
stakk.put(3)
stakk.put(4)
stakk.put(5)

## Sjekker igjen om stakken er tom -> false
print(stakk.empty())

## Fjerner alle elementene
print(stakk.get())
print(stakk.get())
print(stakk.get())

## Sjekker størrelsen på stakken
print("Størrelse", stakk.qsize())

print(stakk.get())
print(stakk.get())

## Sjekker om stakken er tom for siste gang -> true
print(stakk.empty())

Utdata:

True
False
5
4
3
Størrelse 2
2
1
True

Anvendelser av Stakken

Stakken har mange praktiske anvendelser innen programmering. La oss se på et klassisk eksempel: balansering av parenteser.

Oppgaven går ut på å sjekke om et gitt uttrykk med parenteser, klammeparenteser og krøllparenteser er korrekt balansert. For eksempel er «[{}]([])» balansert, mens «{[}]([])» ikke er det.

Løsningen er å bruke en stakk:

• Opprett en stakk for å lagre åpningsparentesene.
• Dersom lengden på uttrykket er et oddetall, er det ikke balansert.
• Iterer gjennom uttrykket:
  • Hvis vi møter en åpningsparentes («(«, «{«, «[«), legg den til i stakken.
  • Hvis vi møter en lukkeparentes («)», «}», «]»), fjern den øverste parentesen fra stakken.
  • Hvis den fjernede parentesen ikke matcher den lukkende, er uttrykket ikke balansert.
• Til slutt, hvis stakken er tom, er uttrykket balansert.

Kodeeksempel:

## stakk
class Stakk: 
    def __init__(self): 
        self.elementer = [] 
    
    def push(self, data): 
        self.elementer.append(data) 
        return data 
        
    def pop(self): 
        return self.elementer.pop() 
    
    def kikk(self): 
        return self.elementer[-1] 
        
    def er_tom(self): 
        return len(self.elementer) == 0

def balansesjekk(uttrykk):
    ## Sjekker lengden på uttrykket
    if len(uttrykk) % 2 != 0:
        ## ikke balansert hvis lengden er oddetall
        return False
    
    ## for sjekking
    åpningsparenteser = set('([{') 
    par = set([ ('(',')'), ('[',']'), ('{','}') ]) 
    
    ## Initialiserer stakken
    stakk = Stakk()
    
    ## Itererer gjennom uttrykket
    for parentes in uttrykk:

        ## Sjekker om nåværende parentes er en åpningsparentes        
        if parentes in åpningsparenteser:
            ## Legger til i stakken
            stakk.push(parentes)
        else:
            ## Fjerner den siste parentesen fra stakken
            fjernet_parentes = stakk.pop()
        
            ## Sjekker om den fjernede og nåværende parentes er et par
            if (fjernet_parentes, parentes) not in par:
                return False
    
    return stakk.er_tom()

if __name__ == '__main__':
    if balansesjekk('[{}]([])'):
        print("Balansert")
    else:
        print("Ikke Balansert")
    
    if balansesjekk('{[}]([])'):
        print("Balansert")
    else:
        print("Ikke Balansert")

Dette er bare ett eksempel på hvordan stakker kan brukes til å løse problemer. Stakker brukes også i blant annet: funksjonskall i programmer, reversering av ord og mye mer.

Konklusjon

Med dette er vi ved veis ende i denne veiledningen. Vi har utforsket hva stakker er, hvordan de fungerer, og sett på forskjellige implementeringsmetoder i Python. Vi har også sett på et praktisk eksempel. Jeg håper at du føler deg komfortabel med å bruke stakker i dine egne programmeringsprosjekter.

Lykke til med kodingen! 👨‍💻