CKTIS / JavaScript
Stack, queue, and LRU cache algorithms
Compare a LIFO stack, a FIFO queue built from two stacks, and an LRU cache that evicts the least recently used entry when it exceeds capacity.
Version: ECMAScript 2024 and the current web platform; runtime support varies
Syntax
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);Stack/Queue/LRU cache algorithms differ in what they remove next. A stack (LIFO) returns the last item added first. On an array, push(value) appends and pop() removes and returns from the same end. Popping an empty stack returns undefined, which is indistinguishable from popping a stored undefined.
A queue (FIFO) returns the earliest item added first. push() and shift() work, but shift() can require moving the remaining items. With two stacks, enqueue onto incoming. To dequeue, transfer all items from incoming to outgoing only when outgoing is empty, then call outgoing.pop(). The transfer reverses the order. Assuming amortized O(1) stack operations, queue operations are amortized O(1), even though one transfer of k items costs O(k). An empty queue has the same undefined ambiguity.
An LRU cache evicts the least recently used entry, not necessarily the first inserted, when it exceeds capacity. Here, a hit or write refreshes recency; a miss leaves the order unchanged. Map iterates in insertion order: set() alone does not move an existing key, but delete() followed by set() moves it to the end. Evict the first key when over capacity. The hit flag distinguishes a miss from a stored undefined.
ECMAScript requires average sublinear access for Map; it does not guarantee O(1) for every LRU operation. A classic alternative pairs a hash table with a doubly linked list: lookup is typically expected O(1), and moving or unlinking a known node takes O(1). A limit on entries is neither a byte limit nor a time-to-live policy.
Examples
{
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(',')}`);
}Result
LIFO: B, A FIFO: A, B, C LRU: A, false, a,c
The stack returns `B` before `A`. The queue returns `A`, `B`, `C` even though `C` is added after `A` is removed. Reading `a` refreshes it, so writing `c` evicts `b` and leaves `a,c`.
Related lessons
- JavaScript · Lesson 7 · Advanced · Version: 4