Implementere og bruke grunnleggende datastrukturer.
Datastrukturar – lister, stakkar og køar
Ein datastruktur er ein måte å organisere og lagre data på slik at vi kan bruke dei effektivt. Du kjenner alt til listene i Python, men no skal vi sjå på meir spesialiserte strukturar: stakkar og køar.
Desse strukturane vert brukte overalt i programmering: frå tilbake-knappen i nettlesarane til oppgåvehandtering i operativsystem.
Stakk (Stack) er ein LIFO-struktur: Last In, First Out. Det siste elementet som vert lagt til er det fyrste som vert teke ut. Tenk på ein stabel med tallerkar.
Kø (Queue) er ein FIFO-struktur: First In, First Out. Det fyrste elementet som vert lagt til er det fyrste som vert teke ut. Tenk på ein kø i butikken.
Eksempel: Liste-operasjonar i Python
Den innebygde list i Python 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 ikkje alltid mest effektive for spesifikke brukstilfelle.
- push(element) – legg element på toppen av stakken
- pop() – fjernar og returnerer elementet på toppen
- peek() eller top() – ser på elementet på toppen utan å fjerne det
- is_empty() – sjekkar om stakken er tom
- size() – returnerer talet på element
Ein stakk har ingen tilgang til element i midten – berre toppen!
Eksempel: Implementere ein stakk
Lat oss lage vår eigen 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 ei liste internt, men tilbyr berre stakk-operasjonar!
Eksempel: Brukstilfelle for stakk – Angre-funksjon
Stakkar 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: HeiKvar gong du skriv, vert førre versjon pusha på stakken. Angre poppar han tilbake!
- enqueue(element) – legg element bakarst i køen
- dequeue() – fjernar og returnerer elementet fremst i køen
- peek() eller front() – ser på elementet fremst utan å fjerne det
- is_empty() – sjekkar om køen er tom
- size() – returnerer talet på element
Ein kø følgjer FIFO: fyrste inn, fyrste ut.
Eksempel: Implementere ein kø
Lat oss lage vår eigen 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 betre yting, bruk collections.deque.
Eksempel: Bruke collections.deque
Python har ein 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 operasjonar i begge endar.
Oppsummering
I dette kapittelet har du lært:
- Lister er fleksible, generelle datastrukturar
- Stakkar følgjer LIFO (Last In, First Out) – vert brukte for angre-funksjonar, navigasjonshistorikk
- Køar følgjer FIFO (First In, First Out) – vert brukte for oppgåvehandtering, meldingskøar
- Vi kan implementere stakkar og køar med lister
- collections.deque er meir effektivt for køar enn vanlege lister
Neste kapittel: Vi utvidar 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.