CKTIS / JavaScript
Sammlungen: Stack, Queue und LRU-Algorithmus
Ein Stack verarbeitet Elemente nach LIFO, eine Queue nach FIFO, und ein LRU-Cache entfernt den am längsten nicht verwendeten Eintrag. In JavaScript lassen sich diese Strukturen mit Array und Map umsetzen; Reihenfolge, Operationskosten und fehlende Werte müssen dabei bewusst behandelt werden.
Version: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Syntax
stack.push(value); stack.pop(); queue.push(value); queue.shift(); map.delete(key); map.set(key, value); map.keys().next().valueStack, Queue und LRU bezeichnen Regeln zur Verwaltung von Sammlungen, keine Namen eingebauter Konstruktoren. Ein Stack folgt LIFO: Das zuletzt hinzugefügte Element wird zuerst entfernt. Für einen einfachen Stack genügt ein Array mit push() und pop(). Eine Queue folgt FIFO: Das zuerst hinzugefügte Element wird zuerst entfernt; eine einfache Variante verwendet push() und shift().
shift() kann das Verschieben indizierter Eigenschaften erfordern. Gehe daher nicht von konstanten Kosten beim Entfernen am Anfang aus. Ziehe bei einer großen Queue einen Ringpuffer oder einen Anfangsindex mit gelegentlichem Neuordnen in Betracht; gib Referenzen auf verarbeitete Objekte frei. pop() und shift() geben bei einem leeren Array undefined zurück. Damit lässt sich eine leere Sammlung nicht von einer Sammlung unterscheiden, die den Wert undefined enthält.
LRU (least recently used) entfernt bei überschrittener Kapazität den am längsten nicht verwendeten Eintrag. Map bewahrt die Einfügereihenfolge, aber weder get() noch set() für einen vorhandenen Schlüssel aktualisiert dessen Position. Lösche den Eintrag bei einem erfolgreichen Lesezugriff und beim Schreiben und füge ihn erneut ein; der erste Schlüssel aus keys() ist dann der Kandidat zum Entfernen. Das Beispiel hat eine feste Kapazität von 2; eine parametrisierte Version sollte prüfen, ob die Kapazität eine positive ganze Zahl ist.
Im Beispiel unterscheidet has() einen fehlenden Schlüssel von einem Eintrag mit dem Wert undefined, obwohl das öffentliche get() in beiden Fällen undefined zurückgibt. Die Spezifikation verlangt für Map durchschnittlich sublinearen Zugriff, garantiert aber nicht O(1). Der Code verwendet Syntax und Funktionen aus ECMAScript 2015 und benötigt keine Browser-Web-APIs. Ein Lauf in Node beweist keine Kompatibilität mit einem bestimmten Zielbrowser.
Beispiele
const stack = [];
stack.push('a', 'b');
console.log(stack.pop());
const queue = [];
queue.push('a', 'b');
console.log(queue.shift());
const cache = new Map();
const capacity = 2;
function put(key, value) {
cache.delete(key);
cache.set(key, value);
if (cache.size > capacity) {
cache.delete(cache.keys().next().value);
}
}
function get(key) {
if (!cache.has(key)) return undefined;
const value = cache.get(key);
cache.delete(key);
cache.set(key, value);
return value;
}
put('a', 1);
put('b', 2);
console.log(get('a'));
put('c', 3);
console.log(cache.has('b'));
console.log([...cache.keys()].join(','));Ergebnis
b a 1 false a,c
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.