2.2 Datastrukturer – lister, stakker og køer

Tallerkener og butikkøer

En datastruktur er ganske enkelt en måte å organisere og lagre data på, slik at vi kan bruke dem effektivt. Du kjenner allerede Pythons lister – en ordnet samling der du kan legge til, fjerne og hente elementer på vilkårlige posisjoner med append, insert, pop og indeksering. Men noen ganger trenger vi mer spesialiserte strukturer, og to av dem dukker opp overalt i programmering: stakker og køer.

Tenk på en stabel med tallerkener. Du legger nye tallerkener på toppen, og du tar dem også av toppen. Den siste du la på, er den første du tar av. Det er en stakk, og prinsippet kalles LIFO – Last In, First Out.

Tenk så på en kø i butikken. Den som stiller seg først, blir ekspedert først. Den nyeste i køen må vente. Det er en kø, og prinsippet kalles FIFO – First In, First Out.

Disse to enkle reglene – ta fra toppen eller ta fra fronten – er forskjellen mellom en stakk og en kø, og de avgjør hvilke problemer hver av dem løser best.

Stakken i praksis

En stakk tilbyr bare noen få operasjoner, og det er hele poenget. Med push(element) legger du noe på toppen, med pop() fjerner og returnerer du topp-elementet, og med peek() titter du på toppen uten å fjerne det. I tillegg har vi is_empty() og size(). Det avgjørende er at en stakk ikke gir tilgang til elementer i midten – bare toppen.

Vi kan bygge vår egen stakk med en vanlig liste internt:

class Stakk:
    def __init__(self):
        self._elementer = []
    def push(self, element):
        self._elementer.append(element)
    def pop(self):
        if self.is_empty():
            raise IndexError("pop fra tom stakk")
        return self._elementer.pop()
    def peek(self):
        return self._elementer[-1]
    def is_empty(self):
        return len(self._elementer) == 0

Pusher du A, B og C og popper to ganger, får du C og deretter B – det siste inn kommer først ut. Et perfekt bruksområde er en angre-funksjon. En teksteditor kan pushe forrige versjon av teksten på en stakk hver gang du skriver. Når du angrer, popper den den forrige versjonen tilbake. Akkurat samme tankegang ligger bak nettleserens tilbake-knapp: den sist besøkte siden er den første du går tilbake til.

Køen og en effektiv snarvei

Køen speilvender stakken. Med enqueue(element) legger du noe bakerst, og med dequeue() fjerner du elementet fremst – det som har ventet lengst. peek() lar deg se på det fremste uten å fjerne det. Vi kan også bygge køen med en liste:

class Kø:
    def __init__(self):
        self._elementer = []
    def enqueue(self, element):
        self._elementer.append(element)
    def dequeue(self):
        return self._elementer.pop(0)  # fjerner første element

Legger du inn 10, 20 og 30 og dequeuer to ganger, får du 10 og deretter 20 – først inn, først ut. Men her er en viktig detalj: pop(0) på en vanlig liste er ineffektivt for store mengder data, fordi alle de andre elementene må flyttes ett hakk fram. I fagspråk sier vi at operasjonen er O(n).

Derfor har Python en innebygd, effektiv løsning i modulen collections: en deque (double-ended queue, «kø med to ender»). Den lar deg legge til bakerst med append og fjerne fra fronten med popleft, og begge operasjonene er O(1) – like raske uansett størrelse. En deque kan til og med brukes som stakk, med append og pop. Når du trenger en kø i praksis, er collections.deque nesten alltid riktig valg.

Oppsummering

Vi startet med tallerkener og butikkøer, og endte med to grunnleggende datastrukturer. Lister er fleksible og generelle. Stakker følger LIFO – Last In, First Out – og passer for angre-funksjoner og navigasjonshistorikk, med operasjonene push, pop og peek. Køer følger FIFO – First In, First Out – og passer for oppgavehåndtering og meldingskøer, med enqueue, dequeue og peek.

Vi kan implementere begge med en liste internt, men for køer er list.pop(0) ineffektivt fordi alle elementene må flyttes. Løsningen er collections.deque, en kø med to ender som gir raske O(1)-operasjoner og til og med kan brukes som stakk. I neste kapittel utvider vi til ordbøker og mengder.