LIFO Cache: essência, algoritmo de pilha e como funciona

O que é LIFO Cache?

LIFO Cache (Last In First Out Cache) é um cache de tamanho fixo implementado sobre uma pilha. Quando um novo elemento é adicionado a um cache cheio, o elemento mais recente (topo) é removido e o novo elemento ocupa seu lugar. O nome “Last In First Out” significa que o elemento que entrou por último no cache será eliminado primeiro.

Esta política difere radicalmente do LRU e FIFO. Enquanto o LRU tenta manter os dados mais relevantes (por tempo do último acesso) e o FIFO preserva a “idade” dos dados, o LIFO sacrifica deliberadamente os dados recentes. Isso pode parecer contra-intuitivo para armazenamento em cache, mas para certos cenários o LIFO se mostra a solução ótima.

Uma implementação clássica de LIFO Cache usa uma pilha baseada em array ou lista encadeada. Um array fornece armazenamento compacto e localidade de cache, mas requer pré-alocação de memória para maxSize. Uma lista encadeada é mais flexível, mas cada elemento requer memória adicional para ponteiros (8–16 bytes por elemento).

Operações Básicas do LIFO Cache

A operação push(value) adiciona um elemento ao topo da pilha. Se o tamanho atingir maxSize, o topo é removido antes da inserção. A operação pop() remove e retorna o elemento superior — útil para cenários de “desfazer última ação”. A operação peek() retorna o elemento superior sem removê-lo — para visualizar o último estado salvo sem alterar a pilha.

Como funciona o LIFO Cache

O princípio de funcionamento do LIFO Cache é extremamente simples: todas as operações são realizadas em uma extremidade da estrutura — o topo da pilha. Quando um novo elemento é adicionado, ele é colocado no topo. Se a pilha estiver cheia, o elemento do topo é removido e o novo ocupa seu lugar. A eliminação sempre afeta apenas um elemento — o topo — portanto, o algoritmo não requer iteração ou busca.

Esta propriedade torna o LIFO Cache o mais rápido entre todas as políticas de eliminação: todas as operações são executadas em O(1) sem quaisquer estruturas de dados adicionais. Não é necessária uma tabela hash para buscas, nem uma lista duplamente encadeada para reordenar — apenas um simples ponteiro para o topo da pilha. O consumo de memória é mínimo: apenas o armazenamento dos próprios elementos.

No entanto, a simplicidade tem um lado negativo: o LIFO Cache não considera a frequência ou o tempo do último acesso aos dados. Se uma aplicação solicitar primeiro os dados A, B, C e depois A novamente, C (o último adicionado) será eliminado quando o cache estiver cheio, mesmo que A não seja mais relevante. Para cenários de cache geral isso torna o LIFO a pior escolha, já que os dados recentes são frequentemente os mais valiosos.

Tamanho da Pilha e Gerenciamento de Memória

Para um LIFO Cache baseado em array, o tamanho é definido na criação e não muda dinamicamente. Se a pilha estiver cheia e ocorrer um push, o elemento do topo é sobrescrito. Para uma implementação com lista encadeada, a memória é alocada por elemento conforme necessário, mas quando o limite é atingido, o nó antigo é desanexado e pode ser coletado pelo coletor de lixo. Em aplicações móveis recomenda-se usar um array para LIFO Cache, pois ele não cria carga adicional no GC.

LIFO vs LRU e FIFO: Comparação de Estratégias

A escolha da estratégia de eliminação afeta diretamente a eficiência do cache. LIFO, LRU e FIFO representam diferentes abordagens para a mesma pergunta: qual elemento remover quando o cache está cheio. Cada abordagem é ótima para sua própria classe de tarefas.

LRU normalmente fornece a melhor taxa de acertos, mas requer mais memória e é mais complexo de implementar. FIFO é um compromisso entre desempenho e taxa de acertos, útil para dados em streaming. LIFO é o mais simples, mas com baixa taxa de acertos: deve ser usado apenas quando a semântica de “último a entrar, primeiro a sair” corresponde à lógica de negócios (navegação, operações de desfazer).

Onde o LIFO Cache é usado

Apesar de sua adequação limitada para cache geral, o LIFO Cache encontra uso em cenários específicos onde a ordem de processamento de dados é inversa à ordem de chegada. Vamos considerar os principais casos.

Pilhas de Navegação

Em aplicações móveis, usa-se uma pilha de navegação: quando uma nova tela é aberta, ela é colocada no topo da pilha; quando o botão “Voltar” é pressionado, ela é removida. Se a profundidade da pilha for limitada (por exemplo, máximo de 10 telas), o LIFO Cache eliminará automaticamente a tela mais recente quando o limite for excedido. Isso permite controlar o consumo de memória da pilha de navegação sem perder telas abertas anteriormente.

Pilhas de Desfazer/Refazer

O mecanismo de desfazer (Undo) é um exemplo clássico de LIFO. Cada ação do usuário é salva em uma pilha. Quando Undo é chamado, a última ação é desfeita e movida para a pilha de Refazer. Limitar o tamanho das pilhas via LIFO Cache garante que, quando o limite for excedido, as ações mais antigas (no fundo da pilha) permaneçam enquanto as mais recentes são descartadas — o que é lógico, já que o usuário normalmente desfaz ações recentes enquanto as antigas não são mais relevantes.

Armazenamento Temporário de Cálculos

Em cálculos recursivos com retrocesso (backtracking), os resultados das etapas intermediárias são salvos em ordem LIFO. Quando o buffer transborda, o último resultado é descartado — isso é aceitável porque o algoritmo pode recalcular se necessário. Esta abordagem é usada em analisadores sintáticos, compiladores e algoritmos de percurso de grafos com limites de profundidade.

Exemplos de Código LIFO Cache

Vamos ver uma implementação de LIFO Cache em Kotlin usando um array de tamanho fixo. Um array fornece o melhor desempenho e o mínimo consumo de memória para dispositivos móveis.

class LifoCache<V>(
    private val maxSize: Int
) {
    private val array = arrayOfNulls<V>(maxSize)
    private var top = -1

    fun push(value: V) {
        if (top == maxSize - 1) {
            top--  // discard oldest when full
        }
        array[++top] = value
    }

    fun pop(): V? {
        if (top == -1) return null
        val result = array[top]
        array[top--] = null
        return result
    }

    fun peek(): V? {
        return array[top]
    }
}

O índice top aponta para o topo da pilha. push incrementa top e escreve o valor; se o array estiver cheio (top == maxSize - 1), top é decrementado antes da escrita — o topo da pilha é sobrescrito, implementando a eliminação LIFO. O método pop retorna o elemento e decrementa top, enquanto peek simplesmente lê o elemento superior sem alterar a pilha.

Exemplo: Pilha de Navegação com LIFO Cache

Considere o uso do LIFO Cache para limitar a profundidade de navegação no Jetpack Compose. Quando uma nova tela é aberta, ela é adicionada à pilha e, quando o limite é excedido, a tela mais recente é eliminada.

class NavigationStack(maxDepth: Int = 10) {
    private val cache = LifoCache<Screen>(maxDepth)

    fun navigateTo(screen: Screen) {
        cache.push(screen)
    }

    fun goBack(): Screen? {
        return cache.pop()
    }

    fun currentScreen(): Screen? {
        return cache.peek()
    }
}

Neste exemplo, NavigationStack usa LIFO Cache para armazenar o histórico de telas. Quando navigateTo é chamado, a tela é adicionada à pilha; quando goBack é chamado, a última é removida. Se o usuário abriu 11 telas com um limite de 10, a mais recente (11ª) eliminará a anterior (10ª) — a primeira tela permanece na pilha, o que corresponde às expectativas do usuário ao navegar para trás. Esta estratégia é mais eficiente que LRU para navegação: remover telas abertas há muito tempo (“início”, “perfil”) levaria a um comportamento inesperado.