LRU（Least Recently Used）即最近最少使用算法，在操作系统内存管理中，有一类很重要的算法就是内存页面置换算法，
包括：FIFO 、LRU 、LFU常见的几种页面置换算法，其核心思想是：都是在给定一个限定大小空间的前提下，设计一个原则如何来更新和访问其中的元素。
LRU 和 LFU区别：
LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。LRU（Least Recently Used）.
注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。举个简单的例子：
假设缓存大小为3，数据访问序列为set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4)，
则在set(4,4)时对于LFU算法应该淘汰(3,3)，而LRU应该淘汰(1,1)。
LRU算法设计原则：
如果一个数据在最近一段时间没有被访问到，那么在将来他被访问的可能性也很小。也就是说，当限定空间数据已满的情况下，应当把最久没有访问到的数据淘汰。
LRU数据结构
利用链表和HashMap。其中：
链表存放着数据，链表头存放着最新被访问的数据，链表尾存放着最近没有被访问的数据。
而哈希表中则存放数据key和数据地址的映射。
思想
插入数据：
- 如果该数据已经存在链表中，则将该数据移动到链表头部。
- 如果链表数据空间没有满，则直接插入到链表头
- 如果链表数据空间已满，则将链表尾部的数据删除，再将新数据插入到链表头；
获取数据：
- 首先查找hashmap，查看是否存在该数据，如果没有，则返回-1；
- 如果存在该数据，通过哈希表获取该数据存放的地址，将该数据从链表中删除，并插入到链表头部，然后返回数据；
C++实现：
#include <algorithm>
#include <list>
#include <unordered_map>
using namespace std;
struct Node {
int key;
int value;
};
class LRUCache{
private:
int maxSize;
list<Node> cacheList;
unordered_map<int, list<Node>::iterator> hashmap;
public:
LRUCache(int capacity) : maxSize(capacity) {}
void set(int key, int value) {
auto it = hashmap.find(key);
if(it == hashmap.end() && maxSize == hashmap.size()) {
hashmap.erase(cacheList.back().key);
cacheList.pop_back();
--maxSize;
}
Node node{key, value};
cacheList.push_front(node);
hashmap[key] = cacheList.begin();
++maxSize;
}
int get(int key) {
auto it = hashmap.find(key);
if(it == hashmap.end())
return -1;
else {
auto temp = hashmap[key];
/* 如果该数据不再链表头部，则从链表中删除该节点，再插入
* 到链表头*/
if(temp !=cacheList.begin()) {
cacheList.erase(temp);
cacheList.push_front({key, temp->value});
}
return temp->value;
}
}
};
