База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / JavaScript

Колекции: стек, опашка и алгоритъм LRU

Стекът обработва елементите по ред LIFO, опашката — по FIFO, а LRU кешът премахва записа, използван най-отдавна. В JavaScript те могат да се реализират с Array и Map, но трябва съзнателно да се управляват редът, цената на операциите и липсващите стойности.

Версия: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support

Синтаксис

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

Стек, опашка и LRU са правила за управление на колекции, а не имена на вградени конструктори. Стекът работи по LIFO: последният добавен елемент се премахва първи. За прост стек е достатъчен масив с push() и pop(). Опашката работи по FIFO: първият добавен елемент се премахва първи; прост вариант използва push() и shift().

shift() може да изисква преместване на индексирани свойства, затова не приемайте, че премахването от началото има постоянна цена. За голяма опашка обмислете кръгов буфер или начален индекс с периодично уплътняване; освобождавайте препратките към обработените обекти. pop() и shift() връщат undefined за празен масив, което не позволява да се различи празна колекция от колекция, съдържаща стойността undefined.

LRU (least recently used) премахва най-отдавна използвания запис при надвишаване на капацитета. Map запазва реда на вмъкване, но нито get(), нито set() за съществуващ ключ обновява позицията му. При успешно четене и при запис изтрийте записа и го добавете отново; първият ключ от keys() тогава е кандидатът за премахване. Примерът има фиксиран капацитет 2; параметризирана версия трябва да проверява дали капацитетът е положително цяло число.

В примера has() различава липсващ ключ от запис със стойност undefined, въпреки че публичният get() връща undefined и в двата случая. Спецификацията изисква средно подлинеен достъп за Map, но не гарантира O(1). Кодът използва синтаксис и функции, налични в ECMAScript 2015, и не изисква браузърни Web API. Изпълнението в Node не доказва съвместимост с целеви браузър.

Примери

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

Резултат

b
a
1
false
a,c

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници