CKTIS / JavaScript
Kolekcije: stog, red i LRU algoritam
Stog obrađuje elemente po načelu LIFO, red po načelu FIFO, a LRU predmemorija uklanja zapis koji se najdulje nije koristio. U JavaScriptu se mogu izraditi pomoću Array i Map, ali treba svjesno upravljati redoslijedom, troškom operacija i vrijednostima koje nedostaju.
Verzija: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Sintaksa
stack.push(value); stack.pop(); queue.push(value); queue.shift(); map.delete(key); map.set(key, value); map.keys().next().valueStog, red i LRU označavaju pravila upravljanja kolekcijama, a ne nazive ugrađenih konstruktora. Stog radi po načelu LIFO: posljednji dodani element uklanja se prvi. Za jednostavan stog dovoljan je niz s push() i pop(). Red radi po načelu FIFO: prvi dodani element uklanja se prvi; jednostavna inačica koristi push() i shift().
shift() može zahtijevati pomicanje indeksiranih svojstava, stoga nemojte pretpostaviti da uklanjanje s početka ima konstantan trošak. Za velik red razmotrite kružni međuspremnik ili početni indeks s povremenim sažimanjem; oslobodite reference na preuzete objekte. pop() i shift() vraćaju undefined za prazan niz, pa se prazna kolekcija ne može razlikovati od kolekcije koja sadrži vrijednost undefined.
LRU (least recently used) pri prekoračenju kapaciteta uklanja zapis koji se najdulje nije koristio. Map čuva redoslijed umetanja, ali ni get() ni set() za postojeći ključ ne osvježava njegov položaj. Pri uspješnom čitanju i pri pisanju uklonite zapis pa ga ponovno umetnite; prvi ključ iz keys() tada je kandidat za uklanjanje. Primjer ima fiksni kapacitet 2; parametrizirana inačica trebala bi provjeriti je li kapacitet pozitivan cijeli broj.
U primjeru has() razlikuje ključ koji nedostaje od zapisa s vrijednošću undefined, iako javni get() u oba slučaja vraća undefined. Specifikacija za Map zahtijeva prosječan podlinearan pristup, ali ne jamči O(1). Kod koristi sintaksu i mogućnosti dostupne u ECMAScript 2015 te ne zahtijeva web API-je preglednika. Pokretanje u Nodeu ne dokazuje kompatibilnost s ciljanim preglednikom.
Primjeri
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(','));Rezultat
b a 1 false a,c
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.