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
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.