FIFO(页面淘汰算法)和LRU(最近最少使用算法)

思路分析：

FIFO的思想是实现一个先进先出的队列，LRU的思想是在FIFO的基础上，将最近访问的节点转移到队列的头部

于是考虑可以用双向链表linkedList来实现，同时为了兼顾查询节点时的效率，结合HashMap来实现。

双向链表linkedList+HashMap的数据结构可以联想到LinkedHashMap，就不需要我们自己来实现了。LinkedHashMap存储数据是有序的，可以分为插入顺序和访问顺序，而且LinkedHashMap提供了删除最后一个节点的方法removeEldestEntry(Map.Entry eldest)，正好可以用来实现FIFO（LinkedHashMap按插入顺序存储数据）和LRU算法（LinkedHashMap按访问顺序存储数据）。

关注点：

1、removeEldestEntry方法默认返回false，需要重写

2、通过LinkedHashMap构造函数中的参数accessOrder来指定数据存储的顺序（false为插入顺序，true为访问顺序）

//LinkedHashMap构造函数
public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

代码实现：

//LRU算法 （FIFO算法只需要将LinkedHashMap的第三个参数true改为false）
public class LRUCache {
    
    private int capacity;
    
    private LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<Integer, Integer>(capacity,0.75f,true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    };
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        Integer res = cache.get(key);
        return res;
    }
    
    public void put(int key, int value) {
        cache.put(key, value);
    }
}