LIFO Cache: Essence, Stack Algorithm and How It Works

What Is LIFO Cache?

LIFO Cache (Last In First Out Cache) is a fixed-size cache implemented on top of a stack. When a new element is added to a full cache, the most recent (top) element is removed and the new element takes its place. The name “Last In First Out” means that the element that entered the cache last will be evicted first.

This policy differs radically from LRU and FIFO. While LRU tries to keep the most relevant data (by last access time) and FIFO preserves data “age,” LIFO deliberately sacrifices fresh data. This may seem counterintuitive for caching, but for certain scenarios LIFO turns out to be the optimal solution.

A classic LIFO Cache implementation uses a stack based on an array or a linked list. An array provides compact storage and cache locality but requires pre-allocating memory for maxSize. A linked list is more flexible, but each element requires additional memory for pointers (8–16 bytes per element).

Basic LIFO Cache Operations

The push(value) operation adds an element to the top of the stack. If the size reaches maxSize, the top is removed before insertion. The pop() operation removes and returns the top element — useful for “undo last action” scenarios. The peek() operation returns the top element without removing it — for viewing the last saved state without changing the stack.

How LIFO Cache Works

The working principle of LIFO Cache is extremely simple: all operations are performed on one end of the structure — the top of the stack. When a new element is added, it is placed on top. If the stack is full, the top element is popped (removed), and the new one takes its place. Eviction always affects only one element — the top — so the algorithm does not require iteration or searching.

This property makes LIFO Cache the fastest among all eviction policies: all operations run in O(1) without any additional data structures. No hash table for lookups, no doubly linked list for reordering — just a simple pointer to the top of the stack. Memory usage is minimal: only the storage of the elements themselves.

However, simplicity has a downside: LIFO Cache does not consider the frequency or last access time of data. If an application first requests data A, B, C, and then A again, C (the last added) will be evicted when the cache is full, even if A is no longer relevant. For general caching scenarios this makes LIFO the worst choice, since fresh data is often the most valuable.

Stack Size and Memory Management

For an array-based LIFO Cache, the size is set at creation and does not change dynamically. If the stack is full and a push occurs, the top element is overwritten. For a linked-list implementation, memory is allocated per element as needed, but when the limit is reached the old node is detached and can be collected by the garbage collector. In mobile applications it is recommended to use an array for LIFO Cache, as it does not create additional GC overhead.

LIFO vs LRU and FIFO: Strategy Comparison

The choice of eviction strategy directly affects caching efficiency. LIFO, LRU, and FIFO represent different approaches to the same question: which element to remove when the cache is full. Each approach is optimal for its own class of tasks.

LRU typically provides the best hit ratio but requires more memory and is more complex to implement. FIFO is a compromise between performance and hit ratio, useful for streaming data. LIFO is the simplest but has a low hit ratio: it should only be used when the “last in, first out” semantics match the business logic (navigation, undo operations).

Where LIFO Cache Is Used

Despite its limited suitability for general caching, LIFO Cache finds use in specific scenarios where the order of data processing is the reverse of the order of arrival. Let us consider the main cases.

Navigation Stacks

In mobile applications, a navigation stack is used: when a new screen is opened, it is placed on the top of the stack; when the “Back” button is pressed, it is removed. If the stack depth is limited (for example, a maximum of 10 screens), LIFO Cache will automatically evict the most recent screen when the limit is exceeded. This allows you to control memory consumption of the navigation stack without losing previously opened screens.

Undo/Redo Stacks

The undo mechanism (Undo) is a classic example of LIFO. Each user action is saved in a stack. When Undo is called, the last action is undone and moved to the Redo stack. Limiting the stack size via LIFO Cache ensures that when the limit is exceeded, the oldest actions (at the bottom of the stack) remain while the most recent are discarded — which is logical since the user typically undoes recent actions while old ones are no longer relevant.

Temporary Computation Buffering

In recursive computations with backtracking, the results of intermediate steps are saved in LIFO order. When the buffer overflows, the last result is discarded — this is acceptable because the algorithm can recompute it if necessary. This approach is used in parsers, compilers, and graph traversal algorithms with depth limits.

LIFO Cache Code Examples

Let us look at a LIFO Cache implementation in Kotlin using a fixed-size array. An array provides the best performance and minimal memory consumption for mobile devices.

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

The top index points to the stack top. push increments top and writes the value; if the array is full (top == maxSize - 1), top is decreased before writing — the stack top is overwritten, which implements LIFO eviction. The pop method returns the element and decrements top, while peek simply reads the top element without changing the stack.

Example: Navigation Stack with LIFO Cache

Consider using LIFO Cache to limit navigation depth in Jetpack Compose. When a new screen is opened, it is added to the stack, and when the limit is exceeded, the most recent screen is evicted.

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

In this example, NavigationStack uses LIFO Cache to store screen history. When navigateTo is called, the screen is added to the stack; when goBack is called, the last one is removed. If the user has opened 11 screens with a limit of 10, the most recent (11th) will evict the previous (10th) — the first screen remains in the stack, which matches user expectations when navigating back. This strategy is more efficient than LRU for navigation: removing long-opened screens (“home,” “profile”) would lead to unexpected behavior.