关于LRU(最近最少使用)算法的c++实现

关于LRU

最近最少使用算法, Least Recently Use, 是一种操作系统中内存调用的方式, 这种算法维护了一个有序列表, 将最近使用的放在前面, 最少使用的放在后面,是一种cache策

其实顺带说一句, 这道题在leetcode上我没能ac, 不过不是代码的问题, 是类型声明的问题

原理解析:

LRU的实现思路是这样的:

当插入数据的时候,先判断数据在队列中是否存在这个数据, 如果存在, 就将这个数据放到队列的顶端,并修改这个数据,如果不存在就在队列的顶端插入数据.

如果插入数据的时候导致长度超标了, 那么就将多出来的末尾元素删去.

查询数据的时候,如果这个数据存在并且被查询到了,则将这个数据移动到队列的前端.

实现思路:

使用哈希表来保存队列中都有什么,方便随时找到数据的地址

用一个双向链表来保存数据本身. 方便随时调整被调用的数据的位置;

代码实现

class Node{
public:
    int key;
    int value;
    Node* next=NULL;
    Node* prev=NULL;
    Node():key(0), value(0), prev(nullptr), next(nullptr){}
    Node(int key,int value):key(key),value(value),prev(nullptr), next(nullptr){

    }
 };

 class LRUCache{
    public:
    int num=0;
    int capacity://容量
    Node * head;//用于调整数据位置
    map<int,Node*> m;        //哈希表用于快速存取
    LRUCache(int capacity):capacity(capacity){
        //初始化容量
        head=new Node(0,0);
    }
    int get(int key){
        if(m.find(key)!=m.end()){//存在这个数据
            return m[key]->value;
        }else{//不存在这个数据
            return -1;

        }

    }
    void put(int key,int value){
        if(m.find(key)==m.end()){
            //没有这个数据的时候, 需要插入链表头部, 并且更新哈希表,长度+1,并检查是否需要消除一个尾部;
            Node* temp=new Node(key,value);
            //长度增加
            num++;
            //插入哈希表
            m[key]=temp;
            //插入头节点
            head->next->prev=temp;
            temp->next=head->next;
            head->next=temp;
            temp->prev=head;
            //如果长度超出
            if(num>capacity){
                //先找到最后一个节点
                Node* point=head->next;
                while(point->next){
                    point=point->next;
                }
                //从列表中删除尾部元素
                point->prev->next=NULL;
                point->prev=NULL;
                //从map中同步删除
                m.erase(point->key);
            }

        }else{
            //存在这个数据的时候
            //先从哈希表中找到这个节点
            Node* temp=m[key];
            //修改节点的数值
            temp->value=value;
            //将节点从之前的位置移动;
            if(temp->next){//如果存在下一个节点
                temp->prev->next=temp->next;
                temp->next->prev=temp->prev;
                temp->prev=NULL;
                temp->next=NULL;

            }else{         //如果这就是末尾的点
                temp->prev->next=NULL;
                temp->prev=NULL;
            }

            //插入头节点的后面
            head->next->prev=temp;
            temp->next=head->next;
            head->next=temp;
            temp->prev=head;

        }

    }
 }

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 xranudvilas@gmail.com