LIFO缓存：本质、栈算法及其工作原理

什么是 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 通常提供最佳命中率，但需要更多内存且实现更复杂。FIFO — 性能和命中率之间的折衷，适合流式数据。LIFO — 最简单，但命中率低：仅当“最后进来——第一个出去”的语义与业务逻辑相符时应用（导航、操作撤销）。

LIFO Cache 应用场景

尽管对于通用缓存适用性有限，LIFO Cache 在数据处理顺序与到达顺序相反的特定场景中有其应用。让我们来看看主要情况。

导航栈

在移动应用中使用导航栈：打开新屏幕时，它被放在栈顶，按下“返回”按钮时被删除。如果栈的深度受到限制（例如最多 10 个屏幕），LIFO Cache 将在超过限制时自动删除最新的屏幕。这使得能够在不丢失之前打开的屏幕的情况下控制导航栈的 内存消耗。

Undo/Redo 栈

撤销操作的机制（Undo）— LIFO 的经典例子。用户的每个操作都保存在栈中。调用 Undo 时，最后一个操作被撤销并移动到 Redo 栈。通过 LIFO Cache 限制栈大小确保在超过限制时，最早的操作（在栈底）保留，最新的操作被丢弃——这是合理的，因为 用户 通常撤销最近的操作，而旧的操作已不再有效。

临时计算缓冲

在带有回溯（backtracking）的递归计算中，中间步骤的结果按 LIFO 顺序保存。当缓冲区溢出时，最后一个结果被丢弃——这是可以接受的，因为算法可以在必要时重新计算。这种方法应用于 解析器、编译器和带深度限制的图遍历算法。

LIFO Cache 代码示例

让我们看看在 Kotlin 中使用固定大小数组实现 LIFO Cache。数组为移动设备提供了最佳性能和最小内存消耗。

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--  // 当满时丢弃最早的
        }
        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 的导航栈

让我们看看在 Jetpack Compose 中使用 LIFO Cache 限制导航深度。打开新屏幕时，它被添加到栈中，超过限制时，最新的屏幕被淘汰。

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 时删除最后一个。如果用户在限制为 10 的情况下打开了 11 个屏幕，最新的（第 11 个）将淘汰前一个（第 10 个）——第一个屏幕保留在栈中，这符合用户返回时的期望。这种策略在导航方面比 LRU 更有效：删除早已打开的屏幕（“首页”、“个人资料”）将导致意料之外的行为。