CKTIS / JavaScript
Colecciones: pila, cola y algoritmo LRU
Una pila procesa elementos en orden LIFO, una cola en FIFO y una caché LRU expulsa la entrada menos utilizada recientemente. En JavaScript se pueden implementar con Array y Map, pero hay que gestionar deliberadamente el orden, el coste de las operaciones y los valores ausentes.
Versión: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Sintaxis
stack.push(value); stack.pop(); queue.push(value); queue.shift(); map.delete(key); map.set(key, value); map.keys().next().valuePila, cola y LRU describen reglas para gestionar colecciones, no nombres de constructores integrados. Una pila sigue LIFO: el último elemento añadido es el primero en retirarse. Para una pila sencilla basta un array con push() y pop(). Una cola sigue FIFO: el primer elemento añadido es el primero en retirarse; una versión sencilla usa push() y shift().
shift() puede requerir mover propiedades indexadas, así que no des por hecho que eliminar al principio tiene un coste constante. Para una cola grande, considera un búfer circular o un índice de inicio con compactación periódica; libera las referencias a los objetos consumidos. pop() y shift() devuelven undefined cuando el array está vacío, lo que no permite distinguir una colección vacía de otra que almacena el valor undefined.
LRU (least recently used) expulsa la entrada menos utilizada recientemente cuando se supera la capacidad. Map conserva el orden de inserción, pero ni get() ni set() sobre una clave existente actualizan su posición. Elimina y vuelve a insertar la entrada cuando una lectura tiene éxito y al escribir; entonces, la primera clave de keys() identifica la candidata a expulsión. El ejemplo tiene una capacidad fija de 2; una versión parametrizada debería comprobar que sea un entero positivo.
En el ejemplo, has() distingue una clave ausente de una entrada cuyo valor es undefined, aunque el get() público devuelve undefined en ambos casos. La especificación exige acceso medio sublineal para Map, pero no garantiza O(1). El código usa sintaxis y funcionalidades disponibles en ECMAScript 2015; no necesita Web APIs del navegador. Ejecutarlo en Node no demuestra que sea compatible con un navegador concreto.
Ejemplos
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(','));Resultado
b a 1 false a,c
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.