Implementere og bruke grunnleggende datastrukturer.
Datastrukturer – lister, stakker og køer
En datastruktur er en måte å organisere og lagre data på slik at vi kan bruke dem effektivt. Du kjenner allerede til Pythons lister, men nå skal vi se på mer spesialiserte strukturer: stakker og køer.
Disse strukturene brukes overalt i programmering: fra nettlesernes tilbake-knapp til oppgavehåndtering i operativsystemer.
Stakk (Stack) er en LIFO-struktur: Last In, First Out. Det siste elementet som legges til er det første som tas ut. Tenk på en stabel med tallerkener.
Kø (Queue) er en FIFO-struktur: First In, First Out. Det første elementet som legges til er det første som tas ut. Tenk på en kø i butikken.
Eksempel: Liste-operasjoner i Python
Pythons innebygde list er veldig fleksibel:
# Lage liste
tall = [1, 2, 3, 4, 5]
# Legge til elementer
tall.append(6) # [1, 2, 3, 4, 5, 6]
tall.insert(0, 0) # [0, 1, 2, 3, 4, 5, 6]
# Fjerne elementer
tall.pop() # Fjerner siste: 6
tall.pop(0) # Fjerner første: 0
# Hente elementer
første = tall[0]
siste = tall[-1]
# Iterere
for tall_element in tall:
print(tall_element)
# Lengde
antall = len(tall)Lister er gode generelt, men ikke alltid mest effektive for spesifikke brukstilfeller.
- push(element) – legger element på toppen av stakken
- pop() – fjerner og returnerer elementet på toppen
- peek() eller top() – ser på elementet på toppen uten å fjerne det
- is_empty() – sjekker om stakken er tom
- size() – returnerer antall elementer
En stakk har ingen tilgang til elementer i midten – bare toppen!
Eksempel: Implementere en stakk
La oss lage vår egen Stakk-klasse:
class Stakk:
def __init__(self):
self._elementer = []
def push(self, element):
"""Legger element på toppen."""
self._elementer.append(element)
def pop(self):
"""Fjerner og returnerer element fra toppen."""
if self.is_empty():
raise IndexError("pop fra tom stakk")
return self._elementer.pop()
def peek(self):
"""Ser på topp-elementet uten å fjerne."""
if self.is_empty():
raise IndexError("peek i tom stakk")
return self._elementer[-1]
def is_empty(self):
"""Sjekker om stakken er tom."""
return len(self._elementer) == 0
def size(self):
"""Returnerer antall elementer."""
return len(self._elementer)
def __str__(self):
return f"Stakk({self._elementer})"
# Bruk
stakk = Stakk()
stakk.push(1)
stakk.push(2)
stakk.push(3)
print(stakk) # Stakk([1, 2, 3])
print(stakk.pop()) # 3 (siste inn, først ut)
print(stakk.pop()) # 2
print(stakk.peek()) # 1 (ser på toppen)Stakken bruker en liste internt, men tilbyr bare stakk-operasjoner!
Eksempel: Brukstilfelle for stakk – Angre-funksjon
Stakker er perfekte for å implementere "angre" (undo):
class Teksteditor:
def __init__(self):
self.tekst = ""
self.historikk = Stakk()
def skriv(self, ny_tekst):
"""Legger til tekst og lagrer forrige versjon."""
self.historikk.push(self.tekst)
self.tekst += ny_tekst
def angre(self):
"""Går tilbake til forrige versjon."""
if not self.historikk.is_empty():
self.tekst = self.historikk.pop()
else:
print("Ingen ting å angre!")
def vis(self):
print(f"Tekst: {self.tekst}")
# Bruk
editor = Teksteditor()
editor.skriv("Hei ")
editor.vis() # Tekst: Hei
editor.skriv("verden!")
editor.vis() # Tekst: Hei verden!
editor.angre()
editor.vis() # Tekst: HeiHver gang du skriver, pushes forrige versjon på stakken. Angre popper den tilbake!
- enqueue(element) – legger element bakerst i køen
- dequeue() – fjerner og returnerer elementet fremst i køen
- peek() eller front() – ser på elementet fremst uten å fjerne det
- is_empty() – sjekker om køen er tom
- size() – returnerer antall elementer
En kø følger FIFO: første inn, først ut.
Eksempel: Implementere en kø
La oss lage vår egen Kø-klasse:
class Kø:
def __init__(self):
self._elementer = []
def enqueue(self, element):
"""Legger element bakerst i køen."""
self._elementer.append(element)
def dequeue(self):
"""Fjerner og returnerer element fremst i køen."""
if self.is_empty():
raise IndexError("dequeue fra tom kø")
return self._elementer.pop(0) # Fjerner første element
def peek(self):
"""Ser på fremste element uten å fjerne."""
if self.is_empty():
raise IndexError("peek i tom kø")
return self._elementer[0]
def is_empty(self):
"""Sjekker om køen er tom."""
return len(self._elementer) == 0
def size(self):
"""Returnerer antall elementer."""
return len(self._elementer)
def __str__(self):
return f"Kø({self._elementer})"
# Bruk
kø = Kø()
kø.enqueue("Person A")
kø.enqueue("Person B")
kø.enqueue("Person C")
print(kø) # Kø(['Person A', 'Person B', 'Person C'])
print(kø.dequeue()) # Person A (første inn, først ut)
print(kø.dequeue()) # Person B
print(kø.peek()) # Person C (ser på fremste)Merk: pop(0) er ineffektivt for store lister (O(n)). For bedre ytelse, bruk collections.deque.
Eksempel: Bruke collections.deque
Python har en innebygd, effektiv kø-implementasjon: collections.deque.
from collections import deque
# Lage en kø
kø = deque()
# Enqueue (legg til bakerst)
kø.append("Første")
kø.append("Andre")
kø.append("Tredje")
# Dequeue (fjern fra fremst)
print(kø.popleft()) # Første
# Peek (se på fremste)
print(kø[0]) # Andre
# Bruke som stakk også:
stakk = deque()
stakk.append(1)
stakk.append(2)
print(stakk.pop()) # 2 (siste inn, først ut)
# deque er O(1) for både append og popleft!deque (double-ended queue) er optimalisert for raske operasjoner i begge ender.
Oppsummering
I dette kapittelet har du lært:
- Lister er fleksible, generelle datastrukturer
- Stakker følger LIFO (Last In, First Out) – brukes for angre-funksjoner, navigasjonshistorikk
- Køer følger FIFO (First In, First Out) – brukes for oppgavehåndtering, meldingskøer
- Vi kan implementere stakker og køer med lister
- collections.deque er mer effektivt for køer enn vanlige lister
Neste kapittel: Vi utvider til ordbøker og mengder!
Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.