CKTIS / JavaScript
Kolekce: zásobník, fronta a algoritmus LRU
Zásobník zpracovává prvky v pořadí LIFO, fronta v pořadí FIFO a mezipaměť LRU odstraní nejdéle nepoužitý záznam. V JavaScriptu je lze sestavit pomocí Array a Map, je však třeba vědomě řešit pořadí, náklady operací a chybějící hodnoty.
Verze: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Syntaxe
stack.push(value); stack.pop(); queue.push(value); queue.shift(); map.delete(key); map.set(key, value); map.keys().next().valueZásobník, fronta a LRU označují pravidla správy kolekcí, nikoli názvy vestavěných konstruktorů. Zásobník funguje podle LIFO: naposledy přidaný prvek se odebere jako první. Pro jednoduchý zásobník stačí pole s push() a pop(). Fronta funguje podle FIFO: jako první se odebere nejdříve přidaný prvek; jednoduchá varianta používá push() a shift().
shift() může vyžadovat přesouvání indexovaných vlastností, proto nepředpokládejte, že odebrání prvku ze začátku má konstantní náklady. U velké fronty zvažte kruhový buffer nebo počáteční index s občasným zhuštěním; uvolňujte reference na odebrané objekty. pop() a shift() vracejí pro prázdné pole undefined, takže nelze odlišit prázdnou kolekci od kolekce obsahující hodnotu undefined.
LRU (least recently used) při překročení kapacity odstraní nejdéle nepoužitý záznam. Map zachovává pořadí vložení, ale get() ani set() u existujícího klíče jeho pozici neobnoví. Při úspěšném čtení i při zápisu záznam odstraňte a znovu vložte; první klíč z keys() pak označuje kandidáta na odstranění. Příklad má pevnou kapacitu 2; parametrizovaná verze by měla ověřit, že kapacita je kladné celé číslo.
V příkladu has() rozlišuje chybějící klíč od záznamu s hodnotou undefined, přestože veřejné get() vrací v obou případech undefined. Specifikace pro Map vyžaduje průměrný podlineární přístup, nikoli zaručené O(1). Kód používá syntaxi a funkce dostupné v ECMAScript 2015 a nevyžaduje webová API prohlížeče. Spuštění v Node nedokazuje kompatibilitu s cílovým prohlížečem.
Příklady
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(','));Výsledek
b a 1 false a,c
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.