最佳页面置换算法代码实现

最佳页面置换算法（Optimal Page Replacement Algorithm），又称为Least Recently Used (LRU) 算法，是一种理想化的内存管理策略，它假设我们总是能预测出下次将访问的页面。在实际编程中，由于这种预测不可能准确，所以通常不会直接用于操作系统中，但在某些应用场景下会被模拟。

在大多数语言中，包括C++，我们会通过维护一个链表或者哈希表来实现LRU。这里是一个简单的基于单链表的C++伪代码实现：

class Node {
public:
    int page;
    Node* next;
};

class LRUCache {
private:
    Node* head;
    Node* tail;
    int capacity;
    // 使用哈希表存储页编号和对应的节点
    std::unordered_map<int, Node*> map;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    // 添加新页面并处理替换
    void addPage(int page) {
        if (map.find(page) != map.end()) {
            Node* node = map[page];
            removeAndAddToHead(node);
        } else {
            if (size() >= capacity) {
                Node* leastUsed = tail; // 尾部是最久未使用的
                remove(leastUsed->page); // 移除并更新哈希表
            }
            Node* newNode = new Node{page, head};
            head->next = newNode;
            head = newNode;
            map[page] = newNode;
        }
    }

    // 删除指定页面
    void remove(int page) {
        auto it = map.find(page);
        if (it != map.end()) {
            Node* node = it->second;
            if (node == head) { // 如果是头结点
                head = head->next;
            } else {
                Node* prev = node->prev;
                prev->next = node->next;
            }
            delete node;
            map.erase(it);
        }
    }

    // 移动节点到链表头部
    void removeAndAddToHead(Node* node) {
        if (node == tail) { // 如果是尾部
            tail = tail->prev;
        }
        node->next = head;
        head->prev = node;
        head = node;
    }

    // 获取页面并更新最近使用状态
    int getPage(int page) {
        auto it = map.find(page);
        if (it == map.end()) return -1;
        Node* node = it->second;
        removeAndAddToHead(node);
        return node->page;
    }
};