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

CKTIS / JavaScript

Algoritmos de pilhas, filas e caches LRU

Compara uma pilha LIFO, uma fila FIFO construída com duas pilhas e uma cache LRU que remove a entrada usada há mais tempo quando excede a capacidade.

Versão: ECMAScript 2024 and the current web platform; runtime support varies

Sintaxe

Stack: stack.push(value); stack.pop();
Two-stack queue: incoming.push(value); if (outgoing.length === 0) { while (incoming.length > 0) outgoing.push(incoming.pop()); } outgoing.pop();
Map-backed LRU refresh: cache.delete(key); cache.set(key, value);
Map-backed LRU eviction: if (cache.size > capacity) cache.delete(cache.keys().next().value);

Uma pilha (LIFO) devolve primeiro o último elemento adicionado. Num array, push(value) acrescenta no fim e pop() retira e devolve um elemento desse mesmo lado. Numa pilha vazia, pop() devolve undefined, tal como ao retirar um undefined guardado.

Uma fila (FIFO) devolve primeiro o elemento que entrou primeiro. Podes usar push() e shift(), mas shift() pode obrigar a deslocar os restantes elementos. Com duas pilhas, acrescenta a incoming. Para retirar um elemento, transfere tudo de incoming para outgoing apenas se outgoing estiver vazia e, depois, chama outgoing.pop(). A transferência inverte a ordem. Se as operações da pilha tiverem custo amortizado O(1), as da fila também têm custo amortizado O(1), embora transferir k elementos custe O(k). Uma fila vazia tem a mesma ambiguidade com undefined.

Uma cache LRU remove a entrada usada há mais tempo, que não é necessariamente a primeira inserida, quando ultrapassa a capacidade. Aqui, ler com sucesso ou escrever torna a entrada a mais recente; uma leitura sem correspondência não muda a ordem. Map é percorrido pela ordem de inserção: set() por si só não move uma chave existente, mas delete() seguido de set() leva-a para o fim. Se a capacidade for ultrapassada, remove a primeira chave. hit distingue uma ausência de um undefined guardado.

ECMAScript exige acesso sublinear em média para Map, mas não garante O(1) para cada operação LRU. Uma alternativa clássica combina uma tabela de dispersão com uma lista duplamente ligada: a pesquisa costuma ter custo esperado O(1), e mover ou desligar um nó conhecido custa O(1). Limitar o número de entradas não impõe um limite em bytes nem um prazo de validade.

Exemplos

{
  const stack = [];
  stack.push('A', 'B');
  console.log(`LIFO: ${stack.pop()}, ${stack.pop()}`);

  const incoming = [];
  const outgoing = [];
  const enqueue = value => incoming.push(value);
  function dequeue() {
    if (outgoing.length === 0) {
      while (incoming.length > 0) outgoing.push(incoming.pop());
    }
    return outgoing.pop();
  }
  enqueue('A');
  enqueue('B');
  const first = dequeue();
  enqueue('C');
  console.log(`FIFO: ${first}, ${dequeue()}, ${dequeue()}`);

  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 read(key) {
    if (!cache.has(key)) return { hit: false };
    const value = cache.get(key);
    put(key, value);
    return { hit: true, value };
  }
  put('a', 'A');
  put('b', 'B');
  const recent = read('a');
  put('c', 'C');
  console.log(`LRU: ${recent.value}, ${read('b').hit}, ${[...cache.keys()].join(',')}`);
}

Resultado

LIFO: B, A
FIFO: A, B, C
LRU: A, false, a,c

A pilha devolve `B` antes de `A`. A fila devolve `A`, `B`, `C`, mesmo que `C` só entre depois de `A` sair. Ler `a` torna-o o mais recente, pelo que escrever `c` remove `b` e deixa `a,c`.

Lições relacionadas

  • JavaScript · Lição 7 · Avançado · Versão: 4

Fontes