Stack

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 Stack 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. Stack 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 (check om stakken er tom). Stacks kan implementeres med arrays eller linked lists og har mange anvendelser i både hardware (call stack) og software (undo funktionalitet, expression evaluation). Stacks er simple men kraftfulde og er centrale i computerens funktion - hver gang en funktion kaldes, lægges dens kontekst på call stack.

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];
  }

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

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

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

// Eksempel: Parenteser 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

•Undo/redo funktionalitet i editorer
•Browser historik (back button)
•Function call stack i programming languages
•Expression evaluation og parsing
•Backtracking algoritmer (maze solving)

Fordele

✓Simple og intuitive operationer
✓O(1) tid for push og pop
✓Let at implementere
✓Lav memory overhead
✓Perfekt til LIFO scenarier

Ulemper

✗Begrænset adgang (kun top element)
✗Ingen random access til elementer
✗Kan overflow ved fixed size implementation
✗Ikke velegnet til søgning
✗Kun én adgangspunkt

Eksempler fra den virkelige verden

•Ctrl+Z undo i Word/Photoshop
•Tilbage knap i web browsers
•Pandekager stablet på tallerkenen
•Bogstabel på skrivebordet
•Email draft history

Relaterede strukturer

QueueDequeCall StackExpression Stack