1、思路：LRU算法的思想这里就不介绍了，重点说一下实现方法。使用双向循环链表保存当前驻留集中的页面，使用unordered_map<int, LinkNode*>记录页面值page与节点地址的映射关系（方便根据page查找结点在链表中是否存在）。

当访问某个页面上时，先查看链表中是否有指定的页面，如果没有，则将此页面插入到双向循环链表头部，并将page和节点地址保存到unordered_map中；

如果链表中已经存在指定的页面，则通过unordered_map查找到指定节点地址，并将节点从链表中摘下并插入到链表头部。

每次访问，都需要对链表进行检查，如果链表长度超过了驻留集大小，则删除链表尾结点并删除unordered_map中的对应节点地址和page值；

2、代码：

#include<iostream>
#include<unordered_map>
using namespace std; 

struct LinkNode{
    int page;
    LinkNode *pre, *next;
    LinkNode(){
        pre = nullptr;
        next = nullptr;
        page = -1;
    }
};

class LRU{
    private:
        LinkNode *head;
        unordered_map<int, LinkNode*> addr;
        int LEN; 
    public:
        LRU(int len){
            head = new LinkNode;
            head -> next = head;
            head -> pre = head;
            LEN = len;
        }
        //访问某个页面 
        void read(int page);
        //显示当前驻留集中的页面 
        void display();
        //更新驻留集中的页面，如果当前页面过多，则删除链表尾部节点 
        void update();
        ~LRU(){
            delete head;
        }
};

void LRU::update(){
    if(addr.size() > LEN){
        //删除尾结点
        LinkNode *p = head -> pre;
        p -> pre -> next = head;
        head -> pre = p -> pre;  
        addr.erase(p -> page);
        delete p;
    }
}

void LRU::read(int page){
    //在链表中没有发现，则将当前访问的数据插入链表首部 
    if(addr.find(page) == addr.end()){
        LinkNode *now = new LinkNode;
        now -> page = page;
        now -> next = head -> next;
        head -> next -> pre = now;
        head -> next = now;
        //记录下当前page的地址 
        addr[page] = now;
    }else{
        //将当前访问的页面摘下放到头部
        LinkNode *now = addr[page];
        addr[page] -> pre -> next = addr[page] -> next;
        addr[page] -> next -> pre = addr[page] -> pre; 
        now -> next = head -> next; 
        head -> next -> pre = now;
        head -> next = now; 
    }
    //更新链表
    update(); 
}

void LRU::display(){
    LinkNode *p = head -> next;
    while(p != head){
        cout << p -> page << " ";
        p = p -> next;
    }
    cout << endl;
}

int main(){
    cout << "请输入驻留集大小：";
    int mem;
    cin >> mem;
    LRU lru(mem);
    cout << "\n请输入访问页面(-1退出)：";
    int key;
    cin >> key;
    while(key != -1){
        lru.read(key);
        cout << "当前驻留集页面："; 
        lru.display();
        cout << endl;
        cout << "请输入访问页面(-1退出)：";
        cin >> key;
    }
    return 0;
}

3、运行截图：