Stak (datastruktur): LIFO forklaret — definition og eksempler

Lær stak (LIFO) på få minutter: klar definition, praktiske eksempler og kodeeksempler. Perfekt for studerende og udviklere — forstå push/pop, anvendelser og kompleksitet hurtigt.

Stakken er en af de vigtigste datastrukturer inden for datalogi. For at forstå, hvordan en stak fungerer, skal du tænke på et spil kort med billedsiden nedad. Vi kan kun nemt få adgang til det kort, der ligger øverst. Når vi ønsker at se på det øverste kort, er der to ting, vi kan gøre: Vi kan kigge på det, men lade det blive på stakken, eller vi kan tage det af. Når vi tager det øverste objekt af, tager vi det af stakken. Hvis vi ønsker at tilføje et andet kort til toppen af stakken, skubber vi det.

En stak kaldes en LIFO-samling (last-in-first-out). Det betyder, at den sidste ting, der er tilføjet (pushed), er den første ting, der bliver trukket (popped) ud. Hvis det sidste kort, vi lagde på vores stak af kort, var et es, er det første kort, vi trak fra toppen, det samme es.

Grundlæggende operationer

• push(item) — lægger et element øverst på stakken.
• pop() — fjerner og returnerer det øverste element; giver typisk en fejl eller et særligt resultat ved underflow (tom stak).
• peek()/top() — returnerer det øverste element uden at fjerne det.
• isEmpty() — tjekker om stakken er tom.
• size() — returnerer antal elementer i stakken.

Tids- og plads-kompleksitet

• Push og pop kan implementeres i O(1) tid (konstant tid) både for arrays (amortiseret O(1) ved dynamisk resizing) og for linked lists.
• Pladskravet er O(n), hvor n er antallet af elementer på stakken.
• Ved en begrænset (bounded) stak kan push fejle, når kapaciteten er nået; ved dynamiske strukturer håndteres dette ved at udvide underliggende buffer.

Implementeringsmuligheder

• Array-baseret — enkel og hurtig; ofte brugt når maksimal størrelse er kendt eller når dynamisk resizing er acceptabelt.
• Linked list — hver node peger på næste element; push/pop i starten af listen er O(1) og ingen resizing nødvendig.
• Persistent/immutabel stak — hver operation returnerer en ny version af stakken (bruges i funktionel programmering).

Eksempler (pseudokode og Python)

 # Pseudokode stack = tom push(x): stack.top = x + stack.top pop(): if stack tom -> fejl; ellers returner øverste element  # Simpelt Python-eksempel class Stack:     def __init__(self):         self._data = []     def push(self, item):         self._data.append(item)     def pop(self):         if not self._data:             raise IndexError("pop fra tom stak")         return self._data.pop()     def peek(self):         return self._data[-1] if self._data else None     def is_empty(self):         return len(self._data) == 0 

Typiske anvendelser

• Funktionskald/rekursion: Call stack i operativsystemet eller runtime holder returadresser og lokale variabler. Overfyldning af denne stak fører til "stack overflow".
• Udtryksevaluering: Omregning fra infix til postfix og evaluering af aritmetiske udtryk bruger stakke til operatorprioritet.
• Backtracking: DFS i grafer og løsningssøgningsalgoritmer bruger stakke til at gemme beslutninger og rulle tilbage.
• Fortryd/angre-funktion: Teksteditorer gemmer ændringer i en stak for at kunne fortryde handlinger i omvendt rækkefølge.
• Browser-historik: To stakke (tilbage/for) bruges ofte til at håndtere frem og tilbage navigation.

Fejl og grænsetilfælde

• Underflow: Forsøg på at poppe fra en tom stak skal håndteres eksplicit (fejl, null-værdi eller undtagelse).
• Overflow: I en fast størrelse stak kan push fejle, hvis kapaciteten er nået; i dynamiske stakke skal resizing ske kontrolleret for at undgå stor hukommelsesbrug.
• Tråd-sikkerhed: I flertrådede miljøer skal adgang synkroniseres (låse eller lock-free datastrukturer) for at undgå race conditions.

Varianter og avancerede emner

• Lock-free concurrent stacks: Implementeret med atomare operationer (f.eks. compare-and-swap) for høj-ydeevne i flertrådet kode.
• Multistak: Flere stakke i én arraystruktur for at spare plads eller optimere adgangsmønstre.
• Deque (dobbelt-ended queue): Generelt mere fleksibel end en stak, da den tillader indsættelse og fjernelse i begge ender.

Opsummering

Stakken er en enkel men meget kraftfuld datastruktur baseret på LIFO-princippet. Dens typiske operationer push, pop og peek er effektive og lette at implementere. Stakke indgår i grundfundamentet for bl.a. funktionskald, rekursion, parsering og backtracking, og forståelsen af stakke er central i både algoritme- og systemdesign.

Søg efter bogstav