Stacks & Queues

Stack — LIFO (Last In, First Out)

Wie ein Tellerstapel: oben drauf, oben weg.

• push(x) — oben drauf — O(1)
• pop() — oben weg — O(1)
• peek() — oben anschauen — O(1)

Anwendungen:

• Funktions-Aufruf-Stack (Call Stack)
• Undo-History
• Klammern-Prüfung in Compilern: "{[}]" — gültig?
• DFS (Depth-First Search) in Graphen

// JS — Array als Stack
const stack = [];
stack.push(1);   // [1]
stack.push(2);   // [1, 2]
stack.pop();     // 2 → [1]

Queue — FIFO (First In, First Out)

Wie eine Warteschlange: hinten ankommen, vorn dran.

• enqueue(x) — hinten anfügen — O(1)
• dequeue() — vorn raus — O(1) (mit Linked List oder Ring-Buffer)

Anwendungen:

• Task-Queues (Jobs nacheinander)
• Drucker-Queue
• BFS (Breadth-First Search)
• Event-Schleife in Browser/Node

Priority Queue / Heap

Erweiterung: Element mit höchster (oder niedrigster) Priorität raus, nicht das älteste.

• insert(x) — O(log n)
• extractMin/Max() — O(log n)

Anwendungen: Dijkstra (kürzeste Wege), Job-Scheduler, Heap-Sort.