题目地址
LRU(Least Recently Used)是一种常见的页面置换算法,在计算中,所有的文件操作都要放在内存中进行,然而计算机内存大小是固定的,所以我们不可能把所有的文件都加载到内存,因此我们需要制定一种策略对加入到内存中的文件进项选择。
一、hash+双向链表
我们使用一个哈希表来维护,值和链表节点关系。用一个双向链表来模拟LRU缓存,该双向链表需要以下几个功能:
- 删除尾部节点(代表最久未使用的数据)
- 插入一个节点到头部位置(新使用了一个数据值)
- 移动一个节点到首部(使用过的数据再次使用)
struct DLinkedNode
{
int key, value;
DLinkedNode* pre;
DLinkedNode* nex;
DLinkedNode() :key(0), value(0), pre(nullptr), nex(nullptr) {};
DLinkedNode(int _key,int _value) :key(_key), value(_value), pre(nullptr), nex(nullptr) {};
};
class LRUCache {
unordered_map<int, DLinkedNode*> cache;
DLinkedNode* head;
DLinkedNode* tail;
int size;//目前缓存中的数据数量
int v;//最大容量
private:
void add_to_head(DLinkedNode* node)
{
node->pre = head;
node->nex = head->nex;
head->nex->pre = node;
head->nex = node;
}
void removenode(DLinkedNode* node)//移除节点
{
node->pre->nex = node->nex;
node->nex->pre = node->pre;
}
void movehead(DLinkedNode* node)
{//移动到头部
removenode(node);
add_to_head(node);
}
int remove_tail()
{
DLinkedNode* tail_node;
tail_node = tail->pre;
tail_node->pre->nex = tail;
tail->pre = tail_node->pre;
int key = tail_node->key;
delete tail_node;
return key;
}
public:
LRUCache(int capacity) {
size = 0;
v=capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head->nex = tail;
tail->pre = head;
}
int get(int key) {
if (!cache.count(key))
{
return -1;
}
DLinkedNode* node = cache[key];
movehead(node);
return node->value;
}
void put(int key, int value) {
if (!cache.count(key))
{
DLinkedNode* node = new DLinkedNode(key, value);
add_to_head(node);
cache[key] = node;
size++;
if (size > v)
{
int key=remove_tail();
cache.erase(key);
size--;
}
}
else
{
DLinkedNode* node = cache[key];
node->value = value;
movehead(node);
}
}
};