操作系统Stack实现LRU

LRU（Least Recently Used）是一种常用的页面置换算法，它根据页面最后一次被访问的时间来选择淘汰的页面，即淘汰最近最少使用的页面。

在操作系统中，为了实现LRU算法，我们可以使用栈（Stack）来保存已访问的页面。每当一个页面被访问时，我们将其从栈中删除，并将其放到栈顶。如果栈满了，那么我们就将栈底的页面淘汰掉。

下面是一个C++实现的LRU算法：

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

class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (cache.count(key)) {
            auto it = cache[key];
            int value = it->second;
            pages.erase(it);
            pages.push(key, value);
            cache[key] = --pages.end();
            return value;
        } else {
            return -1;
        }
    }
    
    void put(int key, int value) {
        if (cache.count(key)) {
            auto it = cache[key];
            pages.erase(it);
        } else if (pages.size() == capacity) {
            int key_to_remove = pages.front().first;
            pages.pop();
            cache.erase(key_to_remove);
        }
        pages.push(key, value);
        cache[key] = --pages.end();
    }
    
private:
    int capacity;
    unordered_map<int, list<pair<int, int>>::iterator> cache;
    list<pair<int, int>> pages;
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 1
    cache.put(3, 3);
    cout << cache.get(2) << endl; // -1
    cache.put(4, 4);
    cout << cache.get(1) << endl; // -1
    cout << cache.get(3) << endl; // 3
    cout << cache.get(4) << endl; // 4
    return 0;
}

在上面的代码中，我们使用了一个unordered_map来保存每个页面的迭代器，这个迭代器指向了该页面在栈中的位置。我们还使用了一个双向链表来保存已访问的页面，这个链表的头部表示最近访问的页面，尾部表示最久未访问的页面。当一个页面被访问时，我们将其从链表中删除，并将其放到链表的头部。如果链表满了，那么我们就将链表尾部的页面淘汰掉。