LRU(Least recently used)，最近最少被使用。该算法根据历史访问记录淘汰缓存数据，其理论依据是最近很少被使用的，以后使用的概率也不会太大。

最简单的LRU

实现:底层数据结构采用单链表。查询时，首先检查缓存是否命中，若命中，则将命中的元素插入到链表的头，若未命中，则从原始存储中查找数据，然后将数据插入到链表的头。在将新元素插入到链表的头部时，若此时空间已满，则淘汰末尾的元素。

点评:实现简单，对于热点数据的访问，效果很好，但对于周期性的数据访问，效果很差

LRU-K

实现:底层实现采用两个链表，分别是历史队列和缓存队列。查询时，首先查看缓存队列，若命中，则将访问数据插入到缓存队列的头部。若未命中，则查看历史队列，若命中，则增加该数据的访问次数，若达到k，则将该数据从历史队列移到缓存队列(此时若缓存队列已满，则会淘汰末尾数据)。若扔未命中，则从原始存储中查找数据，然后将数据插入到历史队列的头。

点评:实际使用中，k经常被设置为2。实现较复杂，使用两个队列来实现一个优先级队列。

扩展

LRU-2使用两个队列来实现，一个历史队列，一个缓存队列，其中历史队列是FIFO，缓存队列是LRU。

LRU算法也可以使用多个队列来实现多优先级的队列。