LIFO Cache: esencia, algoritmo de pila y cómo funciona

¿Qué es LIFO Cache?

LIFO Cache (Last In First Out Cache) es una caché de tamaño fijo implementada sobre una pila. Cuando se añade un nuevo elemento a una caché llena, el elemento más reciente (la cima) se elimina y el nuevo elemento ocupa su lugar. El nombre “Last In First Out” significa que el elemento que entró último en la caché será expulsado primero.

Esta política difiere radicalmente de LRU y FIFO. Mientras que LRU intenta conservar los datos más relevantes (por tiempo de último acceso) y FIFO preserva la “edad” de los datos, LIFO sacrifica deliberadamente los datos recientes. Esto puede parecer contradictorio para el almacenamiento en caché, pero para ciertos escenarios LIFO resulta ser la solución óptima.

Una implementación clásica de LIFO Cache utiliza una pila basada en un array o una lista enlazada. Un array proporciona almacenamiento compacto y localidad de caché, pero requiere preasignar memoria para maxSize. Una lista enlazada es más flexible, pero cada elemento requiere memoria adicional para los punteros (8–16 bytes por elemento).

Operaciones Básicas de LIFO Cache

La operación push(value) añade un elemento a la cima de la pila. Si el tamaño alcanza maxSize, la cima se elimina antes de la inserción. La operación pop() elimina y devuelve el elemento superior — útil para escenarios de “deshacer última acción”. La operación peek() devuelve el elemento superior sin eliminarlo — para ver el último estado guardado sin modificar la pila.

Cómo funciona LIFO Cache

El principio de funcionamiento de LIFO Cache es extremadamente simple: todas las operaciones se realizan en un extremo de la estructura — la cima de la pila. Cuando se añade un nuevo elemento, se coloca en la cima. Si la pila está llena, el elemento superior se extrae (se elimina) y el nuevo ocupa su lugar. La expulsión siempre afecta solo a un elemento — la cima — por lo que el algoritmo no requiere iteración ni búsqueda.

Esta propiedad hace que LIFO Cache sea el más rápido entre todas las políticas de expulsión: todas las operaciones se ejecutan en O(1) sin necesidad de estructuras de datos adicionales. No se necesita una tabla hash para búsquedas, ni una lista doblemente enlazada para reordenar — solo un simple puntero a la cima de la pila. El consumo de memoria es mínimo: solo el almacenamiento de los propios elementos.

Sin embargo, la simplicidad tiene una desventaja: LIFO Cache no considera la frecuencia ni el tiempo del último acceso a los datos. Si una aplicación solicita primero los datos A, B, C y luego A nuevamente, C (el último añadido) será expulsado cuando la caché esté llena, incluso si A ya no es relevante. Para escenarios de caché general esto convierte a LIFO en la peor opción, ya que los datos recientes suelen ser los más valiosos.

Tamaño de la Pila y Gestión de Memoria

Para un LIFO Cache basado en array, el tamaño se define en la creación y no cambia dinámicamente. Si la pila está llena y se produce un push, el elemento superior se sobrescribe. Para una implementación con lista enlazada, la memoria se asigna por elemento según sea necesario, pero cuando se alcanza el límite, el nodo antiguo se desvincula y puede ser recolectado por el recolector de basura. En aplicaciones móviles se recomienda usar un array para LIFO Cache, ya que no genera carga adicional en el GC.

LIFO vs LRU y FIFO: Comparación de Estrategias

La elección de la estrategia de expulsión afecta directamente la eficiencia del caché. LIFO, LRU y FIFO representan diferentes enfoques para la misma pregunta: qué elemento eliminar cuando la caché está llena. Cada enfoque es óptimo para su propia clase de tareas.

LRU normalmente proporciona la mejor tasa de aciertos pero requiere más memoria y es más complejo de implementar. FIFO es un compromiso entre rendimiento y tasa de aciertos, útil para datos en streaming. LIFO es el más simple pero con una tasa de aciertos baja: solo debe usarse cuando la semántica de “último en entrar, primero en salir” coincide con la lógica de negocio (navegación, operaciones de deshacer).

Dónde se usa LIFO Cache

A pesar de su idoneidad limitada para el caché general, LIFO Cache encuentra uso en escenarios específicos donde el orden de procesamiento de datos es inverso al orden de llegada. Consideremos los casos principales.

Pilas de Navegación

En aplicaciones móviles, se utiliza una pila de navegación: cuando se abre una nueva pantalla, se coloca en la cima de la pila; cuando se presiona el botón “Atrás”, se elimina. Si se limita la profundidad de la pila (por ejemplo, un máximo de 10 pantallas), LIFO Cache expulsará automáticamente la pantalla más reciente cuando se supere el límite. Esto permite controlar el consumo de memoria de la pila de navegación sin perder pantallas abiertas anteriormente.

Pilas de Deshacer/Rehacer

El mecanismo de deshacer (Undo) es un ejemplo clásico de LIFO. Cada acción del usuario se guarda en una pila. Cuando se llama a Undo, la última acción se deshace y se mueve a la pila de Rehacer. Limitar el tamaño de las pilas mediante LIFO Cache garantiza que cuando se supere el límite, las acciones más antiguas (en el fondo de la pila) permanezcan mientras que las más recientes se descarten — lo cual es lógico ya que el usuario normalmente deshace acciones recientes mientras que las antiguas ya no son relevantes.

Búferes de Cálculos Temporales

En cálculos recursivos con retroceso (backtracking), los resultados de los pasos intermedios se guardan en orden LIFO. Cuando el búfer se desborda, el último resultado se descarta — esto es aceptable porque el algoritmo puede recalcularlo si es necesario. Este enfoque se utiliza en analizadores sintácticos, compiladores y algoritmos de recorrido de grafos con límites de profundidad.

Ejemplos de Código LIFO Cache

Veamos una implementación de LIFO Cache en Kotlin utilizando un array de tamaño fijo. Un array proporciona el mejor rendimiento y el mínimo consumo de memoria para dispositivos móviles.

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]
    }
}

El índice top apunta a la cima de la pila. push incrementa top y escribe el valor; si el array está lleno (top == maxSize - 1), top se decrementa antes de escribir — la cima de la pila se sobrescribe, lo que implementa la expulsión LIFO. El método pop devuelve el elemento y decrementa top, mientras que peek simplemente lee el elemento superior sin modificar la pila.

Ejemplo: Pila de Navegación con LIFO Cache

Considere el uso de LIFO Cache para limitar la profundidad de navegación en Jetpack Compose. Cuando se abre una nueva pantalla, se añade a la pila, y cuando se supera el límite, la pantalla más reciente es expulsada.

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()
    }
}

En este ejemplo, NavigationStack usa LIFO Cache para almacenar el historial de pantallas. Cuando se llama a navigateTo, la pantalla se añade a la pila; cuando se llama a goBack, la última se elimina. Si el usuario ha abierto 11 pantallas con un límite de 10, la más reciente (la 11.ª) expulsará a la anterior (la 10.ª) — la primera pantalla permanece en la pila, lo que coincide con las expectativas del usuario al navegar hacia atrás. Esta estrategia es más eficiente que LRU para la navegación: eliminar pantallas abiertas hace tiempo (“inicio”, “perfil”) provocaría un comportamiento inesperado.