CKTIS / JavaScript
Collecties: stack, queue en LRU-algoritme
Een stack verwerkt elementen volgens LIFO, een queue volgens FIFO en een LRU-cache verwijdert het minst recent gebruikte item. In JavaScript zijn ze met Array en Map te implementeren, maar de volgorde, bewerkingskosten en ontbrekende waarden vragen om bewuste aandacht.
Versie: 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 en LRU zijn regels voor collectiebeheer, geen namen van ingebouwde constructors. Een stack volgt LIFO: het laatst toegevoegde element wordt als eerste verwijderd. Voor een eenvoudige stack volstaat een array met push() en pop(). Een queue volgt FIFO: het eerst toegevoegde element wordt als eerste verwijderd; een eenvoudige variant gebruikt push() en shift().
shift() kan vereisen dat geïndexeerde eigenschappen worden verschoven. Ga er daarom niet van uit dat verwijderen aan het begin constante kosten heeft. Overweeg voor een grote queue een circulaire buffer of een beginindex met periodieke compactie; maak verwijzingen naar verwerkte objecten vrij. pop() en shift() geven undefined terug voor een lege array, waardoor een lege collectie niet te onderscheiden is van een collectie met de opgeslagen waarde undefined.
LRU (least recently used) verwijdert het minst recent gebruikte item wanneer de capaciteit wordt overschreden. Map bewaart de invoegvolgorde, maar noch get() noch set() op een bestaande sleutel werkt de positie bij. Verwijder het item en voeg het opnieuw toe bij een geslaagde leesactie en bij een schrijfactie; de eerste sleutel uit keys() is dan de kandidaat voor verwijdering. Het voorbeeld heeft een vaste capaciteit van 2; een versie met parameters moet controleren of de capaciteit een positief geheel getal is.
In het voorbeeld maakt has() onderscheid tussen een ontbrekende sleutel en een item met de waarde undefined, hoewel de openbare get() in beide gevallen undefined teruggeeft. De specificatie vereist voor Map gemiddeld sublineaire toegang, maar garandeert geen O(1). De code gebruikt syntax en functies uit ECMAScript 2015 en vereist geen browser-Web-API's. Uitvoering in Node bewijst geen compatibiliteit met een doelbrowser.
Voorbeelden
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(','));Resultaat
b a 1 false a,c
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.