我应该使用什么数据结构来跟踪最近使用过的物品？

Question

我需要类似于有界队列的东西,我只能插入10个元素.新元素应覆盖最后插入的元素. 应该只有n个不同的元素

顺便说一下,我正在寻找Java中的建议.

Answer 1

ITYM 一种 LRU 算法的实现。

• 如何使用 LinkedHashMap 设置简单的 LRU 缓存

• 带过期的简单 LRU 缓存

Answer 2

这是队列数据结构的经典应用程序.大小为10的堆栈将跟踪您添加到其中的前 10个元素,而大小为10的队列将跟踪10个最新元素.如果您正在查找"最近项目"列表,如问题标题所示,则可以使用队列.

编辑:以下是一个示例,用于可视化目的:

假设您要跟踪最近的4个项目,并按以下顺序访问8个项目:

四十二

以下是您的数据结构随时间变化的样子:

access  item      queue          stack
  1      F     [ F . . . ]    [ . . . F ]
  2      O     [ O F . . ]    [ . . O F ]
  3      R     [ R O F . ]    [ . R O F ]
  4      T     [ T R O F ]    [ T R O F ]
  5      Y     [ Y T R O ]    [ Y R O F ]
  6      T     [ T Y T R ]    [ T R O F ]
  7      W     [ W T Y T ]    [ W R O F ]
  8      O     [ O W T Y ]    [ O R O F ]

从堆栈中删除顶部元素将删除最近添加的项目,而不是最旧的项目.

从队列中删除一个元素会删除最旧的项目,因此您的队列将自动保存最新的项目.

编辑:感谢Adam Jaskiewicz,这里有一些关于Java的Queue实现的文档.