Stak

Lineær

En LIFO (Last In First Out) datastruktur hvor det sidste element tilføjet er det første der fjernes.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(n)`
Search	`O(n)`
Insertion	`O(1)`
Deletion	`O(1)`

Beskrivelse

En stak er en fundamental datastruktur der følger Last In First Out (LIFO) princippet - det element der sidst blev lagt på stakken er det første der tages af. Forestil dig en stak tallerkener hvor du kun kan tage den øverste tallerken. Stakken understøtter to primære operationer: push (tilføj element til toppen) og pop (fjern element fra toppen). Derudover findes peek/top (se øverste element uden at fjerne det) og isEmpty (tjek om stakken er tom). Stakke kan implementeres med arrays eller lænkede lister og har mange anvendelser i både hardware (kaldsstak) og software (fortryd-funktionalitet, udtryksberegning). Stakke er simple men kraftfulde og er centrale i computerens funktion - hver gang en funktion kaldes, lægges dens kontekst på kaldsstakken.

Kode Eksempel

// JavaScript Stack implementation
class Stack {
  constructor() {
    this.items = [];
  }

  // Tilføj element til toppen
  push(element) {
    this.items.push(element);
  }

  // Fjern og returner top-element
  pop() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.pop();
  }

  // Se top-element uden at fjerne
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.items.length - 1];
  }

  // Tjek om stakken er tom
  isEmpty() {
    return this.items.length === 0;
  }

  // Få størrelsen
  size() {
    return this.items.length;
  }

  // Ryd stakken
  clear() {
    this.items = [];
  }
}

// Eksempel: Parentes-matching
function isBalanced(expression) {
  const stack = new Stack();
  const pairs = { '(': ')', '[': ']', '{': '}' };
  
  for (let char of expression) {
    if (pairs[char]) {
      stack.push(char);
    } else if (Object.values(pairs).includes(char)) {
      if (stack.isEmpty() || pairs[stack.pop()] !== char) {
        return false;
      }
    }
  }
  return stack.isEmpty();
}

Anvendelsesområder

•Fortryd/gentag-funktionalitet i editorer
•Browserhistorik (tilbage-knap)
•Funktionskaldsstak i programmeringssprog
•Udtryksberegning og parsing
•Backtracking-algoritmer (labyrintløsning)

Fordele

✓Simple og intuitive operationer
✓O(1) tid for push og pop
✓Let at implementere
✓Lavt hukommelsesforbrug
✓Perfekt til LIFO-scenarier

Ulemper

✗Begrænset adgang (kun top-element)
✗Ingen tilfældig adgang til elementer
✗Kan overløbe ved fast størrelse-implementering
✗Ikke velegnet til søgning
✗Kun ét adgangspunkt

Eksempler fra den virkelige verden

•Ctrl+Z fortryd i Word/Photoshop
•Tilbage-knap i webbrowsere
•Pandekager stablet på tallerken
•Bogstabel på skrivebordet
•E-mail kladdehistorik

Relaterede strukturer

QueueDequeCall StackExpression Stack