Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / JavaScript

Coleções: pilha, fila e algoritmo LRU

Uma pilha processa elementos segundo LIFO, uma fila segundo FIFO e uma cache LRU remove a entrada menos recentemente utilizada. Em JavaScript, podem ser implementadas com Array e Map, mas é necessário gerir conscientemente a ordem, o custo das operações e os valores em falta.

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

Sintaxe

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

Pilha, fila e LRU são regras de gestão de coleções, não nomes de construtores incorporados. Uma pilha segue LIFO: o último elemento adicionado é o primeiro a ser removido. Um array com push() e pop() é suficiente para uma pilha simples. Uma fila segue FIFO: o primeiro elemento adicionado é o primeiro a ser removido; uma versão simples usa push() e shift().

shift() pode exigir a deslocação de propriedades indexadas, por isso não pressuponha um custo constante para remover do início. Para uma fila grande, considere um buffer circular ou um índice inicial com compactação periódica; liberte as referências aos objetos consumidos. pop() e shift() devolvem undefined quando o array está vazio, o que não permite distinguir uma coleção vazia de uma coleção que contém o valor undefined.

LRU (least recently used) remove a entrada menos recentemente utilizada quando a capacidade é excedida. Map preserva a ordem de inserção, mas nem get() nem set() numa chave existente atualizam a sua posição. Remova e volte a inserir a entrada quando uma leitura é bem-sucedida e ao escrever; a primeira chave de keys() passa então a ser a candidata a remoção. O exemplo tem capacidade fixa de 2; uma versão parametrizada deve verificar se a capacidade é um número inteiro positivo.

No exemplo, has() distingue uma chave em falta de uma entrada com o valor undefined, embora o get() público devolva undefined em ambos os casos. A especificação exige acesso médio sublinear para Map, mas não garante O(1). O código usa sintaxe e funcionalidades disponíveis no ECMAScript 2015 e não requer Web APIs do navegador. Executá-lo no Node não comprova a compatibilidade com um navegador específico.

Exemplos

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

Resultado

b
a
1
false
a,c

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes