LIFO Cache: суть, алгоритм стека и как работает

Что такое LIFO Cache?

LIFO Cache (Last In First Out Cache) — это кэш ограниченного размера, реализованный на основе стека. При добавлении нового элемента в заполненный кэш удаляется самый свежий (верхний) элемент, а новый занимает его место. Название «Last In First Out» означает, что элемент, попавший в кэш последним, будет удалён первым.

Такая политика радикально отличается от LRU и FIFO. Если LRU пытается сохранить наиболее актуальные данные (по времени последнего обращения), а FIFO сохраняет «возраст» данных, то LIFO сознательно жертвует свежими данными. Это может показаться нелогичным для кэширования, но для определённых сценариев LIFO оказывается оптимальным решением.

Классическая реализация LIFO Cache использует стек на основе массива или связного списка. Массив обеспечивает компактное хранение и кэш-локальность, но требует предварительного выделения памяти под maxSize. Связный список гибче, но каждый элемент требует дополнительной памяти на указатели (8–16 байт на элемент).

Основные операции LIFO Cache

Операция push(value) добавляет элемент на вершину стека. Если размер достиг maxSize, перед вставкой вершина удаляется. Операция pop() удаляет и возвращает верхний элемент — полезно для сценариев «откат последнего действия». Операция peek() возвращает верхний элемент без удаления — для просмотра последнего сохранённого состояния без изменения стека.

Как работает LIFO Cache

Принцип работы LIFO Cache предельно прост: все операции выполняются с одним концом структуры — вершиной стека. При добавлении нового элемента он кладётся на вершину. Если стек заполнен, верхний элемент выталкивается (удаляется), а новый занимает его место. Вытеснение всегда затрагивает только один элемент — вершину, поэтому алгоритм не требует перебора или поиска.

Это свойство делает LIFO Cache самым быстрым среди всех политик вытеснения: все операции выполняются за O(1) без каких-либо дополнительных структур данных. Не нужна хеш-таблица для поиска, не нужен двусвязный список для перестановок — достаточно простого указателя на вершину стека. Память расходуется минимально: только на хранение самих элементов.

Однако простота имеет обратную сторону: LIFO Cache не учитывает частоту или время последнего обращения к данным. Если приложение сначала запрашивает данные A, B, C, а затем снова A — при переполнении вытеснится C (последний добавленный), даже если A уже не актуален. Для сценариев общего кэширования это делает LIFO худшим выбором, так как свежие данные часто наиболее ценны.

Размер стека и управление памятью

Для LIFO Cache на основе массива размер задаётся при создании и не меняется динамически. Если стек заполнен и происходит push — верхний элемент перезаписывается. Для реализации на связном списке память выделяется под каждый элемент по мере необходимости, но при достижении лимита старый узел отсоединяется и может быть собран сборщиком мусора. В мобильных приложениях рекомендуется использовать массив для LIFO Cache, так как он не создаёт дополнительной нагрузки на GC.

LIFO vs LRU и FIFO: сравнение стратегий

Выбор стратегии вытеснения напрямую влияет на эффективность кэширования. LIFO, LRU и FIFO представляют разные подходы к одному вопросу: какой элемент удалить при переполнении. Каждый подход оптимален для своего класса задач.

LRU обычно даёт наилучший hit-ratio, но требует больше памяти и сложнее в реализации. FIFO — компромисс между производительностью и hit-ratio, полезен для потоковых данных. LIFO — самый простой, но с низким hit-ratio: его следует применять только тогда, когда семантика «последний пришёл — первый ушёл» соответствует бизнес-логике (навигация, отмена операций).

Где применяется LIFO Cache

Несмотря на ограниченную пригодность для общего кэширования, LIFO Cache находит применение в конкретных сценариях, где порядок обработки данных обратен порядку поступления. Рассмотрим основные случаи.

Навигационные стеки

В мобильных приложениях используется стек навигации: при открытии нового экрана он помещается на вершину стека, при нажатии «Назад» — снимается. Если ограничить глубину стека (например, максимум 10 экранов), LIFO Cache будет автоматически вытеснять самый последний экран при превышении лимита. Это позволяет контролировать потребление памяти навигационным стеком без потери ранее открытых экранов.

Undo/Redo стеки

Механизм отмены действий (Undo) — классический пример LIFO. Каждое действие пользователя сохраняется в стеке. При вызове Undo последнее действие отменяется и перемещается в Redo-стек. Ограничение размера стеков через LIFO Cache гарантирует, что при превышении лимита самые старые действия (на дне стека) останутся, а самые свежие будут отброшены — что логично, так как пользователь обычно отменяет недавние действия, а старые уже неактуальны.

Буферизация временных вычислений

При рекурсивных вычислениях с возвратом (backtracking) результаты промежуточных шагов сохраняются в LIFO порядке. Когда буфер переполняется, последний результат отбрасывается — это допустимо, так как алгоритм может пересчитать его при необходимости. Такой подход используется в парсерах, компиляторах и алгоритмах обхода графов с ограничением глубины.

Примеры кода LIFO Cache

Рассмотрим реализацию LIFO Cache на Kotlin с использованием массива фиксированного размера. Массив обеспечивает наилучшую производительность и минимальное потребление памяти для мобильных устройств.

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

Индекс top указывает на вершину стека. push увеличивает top и записывает значение; если массив заполнен (top == maxSize - 1), перед записью top уменьшается — вершина стека перезаписывается, что и реализует LIFO-вытеснение. Метод pop возвращает элемент и уменьшает top, а peek просто читает верхний элемент без изменения стека.

Пример: навигационный стек с LIFO Cache

Рассмотрим использование LIFO Cache для ограничения глубины навигации в Jetpack Compose. При открытии нового экрана он добавляется в стек, а при превышении лимита самый поздний экран вытесняется.

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

В данном примере NavigationStack использует LIFO Cache для хранения истории экранов. При вызове navigateTo экран добавляется в стек, при goBack — удаляется последний. Если пользователь открыл 11 экранов при лимите 10, самый поздний (11-й) вытеснит предыдущий (10-й) — первый экран останется в стеке, что соответствует ожиданиям пользователя при возврате назад. Такая стратегия эффективнее, чем LRU, для навигации: удаление давно открытых экранов («домашний», «профиль») привело бы к неожиданному поведению.