如何实现频率栈

频率栈的适用场景

频率栈适合处理“高频优先、同频看最近”的取值需求。它常用于缓存淘汰、热点统计、任务调度等场景。和普通栈不同，它不是简单按入栈顺序出栈，而是会优先返回当前出现次数最高的元素；如果多个元素次数相同，就返回最近加入的那个。

实现频率栈的关键结构

常见做法是结合两个部分：一个哈希表记录每个元素当前出现的次数，一个按频次分组的栈结构记录元素的进入顺序。哈希表负责快速更新频率，分组栈负责在同一频率下保持最近插入的元素优先弹出。这样可以让入栈、出栈都维持较高效率。

同频情况下的选择规则

频率栈会把相同频率的元素放在同一个“频次组”里，并按加入顺序保存。弹出时，只需要查看当前最高频次对应的那一组栈顶元素，就能得到最近加入的值。这个机制天然满足“次数相同，最近的先出”的要求，不需要额外比较时间戳。

频率栈的性能表现

频率栈通常可以把 push 和 pop 都做到接近 O(1)。原因是它主要依赖哈希表和栈，频率更新、分组定位、元素弹出都不需要遍历全体数据。对于大规模数据处理，这种设计有较好的扩展性，也适合需要高频操作的业务场景。