使用C++编写先进先出页面置换算法

以下是使用C++编写的先进先出页面置换算法的示例代码：

#include <iostream>
#include <queue>
#include <unordered_set>

using namespace std;

int main() {
    int n; // 总共有 n 个页面
    cout << "请输入页面总数: ";
    cin >> n;

    int m; // 内存中可以容纳 m 个页面
    cout << "请输入内存页面容量: ";
    cin >> m;

    int page_seq[n]; // 页面序列
    cout << "请输入页面序列: ";
    for (int i = 0; i < n; i++) {
        cin >> page_seq[i];
    }

    queue<int> fifo; // 先进先出队列
    unordered_set<int> s; // 用于判断页面是否在内存中

    int page_faults = 0; // 页面缺页次数

    for (int i = 0; i < n; i++) {
        int page = page_seq[i];
        if (s.find(page) == s.end()) { // 页面不在内存中
            page_faults++;
            if (fifo.size() == m) { // 内存已满
                int oldest_page = fifo.front(); // 最先进入内存的页面
                fifo.pop();
                s.erase(oldest_page);
            }
            fifo.push(page);
            s.insert(page);
        }
    }

    cout << "页面缺页次数: " << page_faults << endl;

    return 0;
}

示例输入：

请输入页面总数: 12
请输入内存页面容量: 3
请输入页面序列: 1 2 3 4 1 2 5 1 2 3 4 5

示例输出：

页面缺页次数: 9

这里的先进先出页面置换算法使用队列来存储内存中的页面，每次有页面访问时，如果页面不在内存中，则将其加入队列并加入哈希表中，如果内存已满，则弹出队首的最先进入内存的页面并从哈希表中移除，然后将新页面加入队尾和哈希表中。由于队列是先进先出的，所以最先进入内存的页面一定是队首的页面，也就是最先被弹出的页面。