CKTIS / JavaScript
Algoritmos de pila, cola y caché LRU
Compara una pila LIFO, una cola FIFO construida con dos pilas y una caché LRU que expulsa la entrada usada hace más tiempo cuando supera su capacidad.
Versión: ECMAScript 2024 and the current web platform; runtime support varies
Sintaxis
Stack: stack.push(value); stack.pop();
Two-stack queue: incoming.push(value); if (outgoing.length === 0) { while (incoming.length > 0) outgoing.push(incoming.pop()); } outgoing.pop();
Map-backed LRU refresh: cache.delete(key); cache.set(key, value);
Map-backed LRU eviction: if (cache.size > capacity) cache.delete(cache.keys().next().value);Una pila (LIFO) devuelve primero el último elemento añadido. En un array, push(value) añade al final y pop() extrae y devuelve un elemento de ese mismo extremo. En una pila vacía, pop() devuelve undefined, igual que si se extrajera un undefined almacenado.
Una cola (FIFO) devuelve primero el primer elemento añadido. Se pueden usar push() y shift(), pero shift() puede requerir desplazar los elementos restantes. Con dos pilas, añade a incoming. Para extraer, pasa todos los elementos de incoming a outgoing solo si outgoing está vacía y luego llama a outgoing.pop(). El traslado invierte el orden. Si las operaciones de pila cuestan O(1) amortizado, las de cola también, aunque trasladar k elementos cueste O(k). Una cola vacía presenta la misma ambigüedad con undefined.
Una caché LRU expulsa la entrada usada hace más tiempo, no necesariamente la primera insertada, al superar su capacidad. Aquí, una lectura con acierto o una escritura deja la entrada como la más reciente; un fallo de caché no altera el orden. Map se recorre en orden de inserción: set() por sí solo no mueve una clave existente, pero delete() seguido de set() la lleva al final. Si se supera la capacidad, expulsa la primera clave. hit distingue un fallo de un undefined almacenado.
ECMAScript exige acceso sublineal en promedio para Map, pero no garantiza O(1) en cada operación LRU. Una alternativa clásica combina una tabla hash y una lista doblemente enlazada: la búsqueda suele tener un coste esperado de O(1), y mover o desenlazar un nodo conocido cuesta O(1). Limitar el número de entradas no equivale a limitar los bytes ni a establecer una caducidad.
Ejemplos
{
const stack = [];
stack.push('A', 'B');
console.log(`LIFO: ${stack.pop()}, ${stack.pop()}`);
const incoming = [];
const outgoing = [];
const enqueue = value => incoming.push(value);
function dequeue() {
if (outgoing.length === 0) {
while (incoming.length > 0) outgoing.push(incoming.pop());
}
return outgoing.pop();
}
enqueue('A');
enqueue('B');
const first = dequeue();
enqueue('C');
console.log(`FIFO: ${first}, ${dequeue()}, ${dequeue()}`);
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 read(key) {
if (!cache.has(key)) return { hit: false };
const value = cache.get(key);
put(key, value);
return { hit: true, value };
}
put('a', 'A');
put('b', 'B');
const recent = read('a');
put('c', 'C');
console.log(`LRU: ${recent.value}, ${read('b').hit}, ${[...cache.keys()].join(',')}`);
}Resultado
LIFO: B, A FIFO: A, B, C LRU: A, false, a,c
La pila devuelve `B` antes que `A`. La cola devuelve `A`, `B`, `C`, aunque `C` se añada después de extraer `A`. Leer `a` lo deja como el más reciente, así que escribir `c` expulsa `b` y deja `a,c`.
Lecciones relacionadas
- JavaScript · Lección 7 · Avanzado · Versión: 4