CKTIS / JavaScript
Collezioni: stack, coda e algoritmo LRU
Uno stack elabora gli elementi in ordine LIFO, una coda in FIFO e una cache LRU rimuove la voce usata meno di recente. In JavaScript si possono implementare con Array e Map, ma occorre gestire consapevolmente ordine, costo delle operazioni e valori mancanti.
Versione: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Sintassi
stack.push(value); stack.pop(); queue.push(value); queue.shift(); map.delete(key); map.set(key, value); map.keys().next().valueStack, coda e LRU indicano regole per gestire le collezioni, non nomi di costruttori integrati. Uno stack segue LIFO: l’ultimo elemento aggiunto è il primo a essere rimosso. Per uno stack semplice basta un array con push() e pop(). Una coda segue FIFO: il primo elemento aggiunto è il primo a essere rimosso; una versione semplice usa push() e shift().
shift() può richiedere lo spostamento delle proprietà indicizzate, quindi non dare per scontato che la rimozione dall’inizio abbia costo costante. Per una coda grande, valuta un buffer circolare o un indice iniziale con compattazione periodica; libera i riferimenti agli oggetti consumati. pop() e shift() restituiscono undefined quando l’array è vuoto: non è quindi possibile distinguere una collezione vuota da una che contiene il valore undefined.
LRU (least recently used) rimuove la voce usata meno di recente quando si supera la capacità. Map mantiene l’ordine di inserimento, ma né get() né set() su una chiave esistente ne aggiorna la posizione. Elimina e reinserisci la voce quando una lettura ha esito positivo e quando scrivi; a quel punto la prima chiave di keys() è la candidata alla rimozione. L’esempio ha capacità fissa 2; una versione parametrizzata dovrebbe verificare che la capacità sia un intero positivo.
Nell’esempio, has() distingue una chiave mancante da una voce che contiene undefined, anche se il get() pubblico restituisce undefined in entrambi i casi. La specifica richiede per Map un accesso medio sublineare, non garantisce O(1). Il codice usa sintassi e funzionalità disponibili in ECMAScript 2015 e non richiede Web API del browser. Eseguirlo in Node non dimostra la compatibilità con un browser specifico.
Esempi
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(','));Risultato
b a 1 false a,c
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.