Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / JavaScript

Kolekcje: stos, kolejka i algorytm LRU

Stos przetwarza elementy w kolejności LIFO, kolejka w FIFO, a pamięć podręczna LRU usuwa najdawniej używany wpis. W JavaScript można je zbudować za pomocą Array i Map, ale trzeba świadomie obsłużyć kolejność, koszt operacji i brak wartości.

Wersja: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support

Składnia

stack.push(value); stack.pop(); queue.push(value); queue.shift(); map.delete(key); map.set(key, value); map.keys().next().value

Stos, kolejka i LRU to reguły zarządzania kolekcją, nie nazwy wbudowanych konstruktorów. Stos działa według LIFO: ostatni dodany element znika pierwszy. Tablica z push() i pop() wystarcza do prostego stosu. Kolejka działa według FIFO: pierwszy dodany element znika pierwszy; prosty wariant używa push() i shift().

shift() może wymagać przesuwania właściwości indeksowych, więc nie zakładaj stałego kosztu usuwania początku. Dla dużej kolejki rozważ bufor cykliczny albo indeks początku z okresowym porządkowaniem; zwalniaj referencje do odebranych obiektów. pop() i shift() zwracają undefined dla pustej tablicy, co nie odróżnia pustej kolekcji od przechowywanej wartości undefined.

LRU (least recently used) usuwa najdawniej używany wpis po przekroczeniu pojemności. Map zachowuje kolejność dodawania, lecz samo get() ani set() istniejącego klucza nie odświeża jego pozycji. Usuń i ponownie dodaj wpis przy trafieniu odczytu i przy zapisie; pierwszy klucz z keys() wskazuje wtedy kandydata do usunięcia. Przykład ma stałą pojemność 2; parametryzowana wersja powinna sprawdzać, czy pojemność jest dodatnią liczbą całkowitą.

W przykładzie has() odróżnia brak klucza od wpisu z wartością undefined, choć publiczne get() zwraca w obu sytuacjach undefined. Specyfikacja wymaga średnio podliniowego dostępu do Map, nie gwarantuje O(1). Kod używa składni i mechanizmów dostępnych w ECMAScript 2015; nie wymaga przeglądarkowych Web APIs. Uruchomienie w Node nie dowodzi zgodności docelowej przeglądarki.

Przykłady

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(','));

Wynik

b
a
1
false
a,c

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła