CKTIS / JavaScript
Kolekcie: zásobník, fronta a algoritmus LRU
Zásobník spracúva prvky v poradí LIFO, fronta v poradí FIFO a vyrovnávacia pamäť LRU odstráni najdlhšie nepoužitý záznam. V JavaScripte sa dajú vytvoriť pomocou Array a Map, no treba vedome riešiť poradie, náklady operácií a chýbajúce hodnoty.
Verzia: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Syntax
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ú pravidlá správy kolekcií, nie názvy vstavaných konštruktorov. Zásobník funguje podľa LIFO: naposledy pridaný prvok sa odstráni ako prvý. Na jednoduchý zásobník stačí pole s push() a pop(). Fronta funguje podľa FIFO: ako prvý sa odstráni najskôr pridaný prvok; jednoduchý variant používa push() a shift().
shift() môže vyžadovať presúvanie indexovaných vlastností, preto nepredpokladajte, že odstránenie zo začiatku má konštantné náklady. Pri veľkej fronte zvážte kruhový buffer alebo počiatočný index s občasným zhutnením; uvoľňujte referencie na odobraté objekty. pop() a shift() vracajú pri prázdnom poli undefined, takže nemožno odlíšiť prázdnu kolekciu od kolekcie, ktorá obsahuje hodnotu undefined.
LRU (least recently used) pri prekročení kapacity odstráni najdlhšie nepoužitý záznam. Map zachováva poradie vloženia, ale get() ani set() pri existujúcom kľúči jeho pozíciu neobnoví. Pri úspešnom čítaní aj pri zápise záznam odstráňte a znova vložte; prvý kľúč z keys() potom označuje kandidáta na odstránenie. Príklad má pevnú kapacitu 2; parametrizovaná verzia by mala overiť, či je kapacita kladné celé číslo.
V príklade has() rozlišuje chýbajúci kľúč od záznamu s hodnotou undefined, hoci verejné get() vracia v oboch prípadoch undefined. Špecifikácia pre Map vyžaduje priemerný podlineárny prístup, nie zaručené O(1). Kód používa syntax a funkcie dostupné v ECMAScript 2015 a nevyžaduje webové API prehliadača. Spustenie v Node nedokazuje kompatibilitu s cieľovým prehliadačom.
Prí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ýsledok
b a 1 false a,c
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.