用java模拟页面置换算法LRU

LRU（Least Recently Used）是一种页面置换算法，它总是选择最近最少使用的页面予以淘汰。下面是用Java模拟LRU算法的示例代码：

import java.util.*;

public class LRU {
    private int capacity; // 缓存容量
    private Map<Integer, Integer> map; // 存储缓存
    private Deque<Integer> deque; // 存储缓存的使用情况

    public LRU(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        deque = new LinkedList<>();
    }

    public int get(int key) {
        if (map.containsKey(key)) { // 如果缓存中存在该页面
            deque.remove(key); // 先将页面从使用情况中删除
            deque.offerFirst(key); // 再将该页面插入到队头，表示最近使用过
            return map.get(key);
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) { // 如果缓存中已经存在该页面
            deque.remove(key); // 先将页面从使用情况中删除
        } else if (map.size() == capacity) { // 如果缓存已满
            int removedKey = deque.pollLast(); // 淘汰最近最少使用的页面
            map.remove(removedKey);
        }
        deque.offerFirst(key); // 将新页面插入到队头
        map.put(key, value); // 更新缓存
    }
}

在这个示例中，我们使用了HashMap存储缓存，使用Deque（双端队列）存储缓存的使用情况。当需要获取某个页面时，我们先判断缓存中是否存在该页面，如果存在，我们将该页面从使用情况中删除，并将其插入到队头；如果不存在，返回-1。当需要插入新页面时，我们先判断缓存中是否已经存在该页面，如果存在，我们将其从使用情况中删除；如果缓存已满，我们淘汰最近最少使用的页面，并将新页面插入到队头。最后，我们更新缓存，并返回结果。