LRU算法

leetcode 146
最近最久未使用页面置换算法

• 系统上选择距离当前页面使用时间最长的页面予以淘汰
• 局部性原理：较长时间未使用的页面，可能不会马上用到
  通常使用栈来组织各个驻留页，栈底放最常时间未使用的，栈顶放最近使用的。当加入的元素超过缓存数量，即页框长度时，选择将栈底的元素换出，将新放入的元素放在栈顶.
  | 页号 |7|0|1|2|0|3|0|4|
  | 帧1 |7|0|1|2|0|3|0|4|
  | 帧2 | |7|0|1|2|0|3|0|
  | 帧3 | | |7|0|1|2|2|3|
  就算不发生缺页中断，即当前页面在帧中存在，也需要调整栈的位置，即调整页面出现的顺序
  要将元素从栈底删除，从栈顶插入，考虑用双向链表实现该功能，这样删除和插入都可以在O(1)的时间内完成.

class Node
{
public:
    Node(int key = 0, int val = 0, Node* pre = nullptr, Node* next = nullptr) :key(key), val(val), pre(pre), next(next)//构造函数
    {

    }

    int key;//当前节点的键
    int val;//当前节点的值
    Node* pre;//前指针
    Node* next;//后指针
};

class LRUCache {
public:

    Node* head;//双向链表头
    Node* tail;//双向链表尾
    int capacity;//缓存大小
    int now;//当前元素个数
    map<int, Node*> maps;//通过输入的key,定位到对应的节点，得到对应的value值;并且可以移动定位得到的节点，将其放到头部去.
    LRUCache(int capacity) {
        head = new Node();
        tail = new Node();//将头尾两个指针创建出来
        head->next=tail;
        tail->pre=head;
        this->capacity = capacity;
        this->now = 0;
    }
    //在双向链表中删除节点
    void remove(Node* Toremove)
    {
        Toremove->next->pre = Toremove->pre;//删除节点的下一个节点的pre指向删除节点的上一个节点
        Toremove->pre->next = Toremove->next;//删除节点的上一个节点的next指向删除节点的下一个节点
    }
    //在头部插入
    void addtohead(Node* Toadd)
    {
        Toadd->next=head->next;
        head->next->pre=Toadd;
        head->next=Toadd;
        Toadd->pre=head;
        /*Toadd->pre = head;
        Toadd->next = head->next;
        head->next->pre = Toadd;
        head->next = Toadd;*/
    }
    int removeintail()
    {
        Node* removet = tail->pre;
        remove(removet);
        return removet->key;
    }

    void move(Node* Toadd)
    {
        remove(Toadd);
        addtohead(Toadd);

    }
    int get(int key) {
        if (maps.count(key))
        {
            move(maps[key]); //取值的时候调整位置，取值之后将让该节点移动到链表尾
            return maps[key]->val;
        }
        return -1;
    }

    void put(int key, int value)
    {
        if (!maps.count(key))//不存在当前key
        {
            now++;
            Node* temp = new Node(key, value);
            maps[key] = temp;
            addtohead(temp);
            if (now > capacity)//大于缓存数量
            {
                int k = removeintail();
                maps.erase(k);
                now--;
            }
        }
        else
        {
            move(maps[key]);
            maps[key]->val = value;
        }
    }
};