LRU代表最近最少使用，当用户添加数据时应在缓存中删除最久没被使用的数据项，具体要求可以参考leetcode
https://leetcode-cn.com/problems/lru-cache/
算法实现
1. 使用数组记录时间戳
用一个数组记录所有元素的使用时间戳，每当一个元素插入或查找时置为零，并将其他所有元素加1，查找、添加时间复杂度均为O(n)
2. 使用双向链表
链表的添加、删除时间复杂度均为O(1)，但是查找时间未O(n)，可以使用链表的特性将最近使用的节点移动到队首，这样便可以空间满时直接删除最后一个元素
还可以结合哈希表将查找复杂度优化为O(1)，每次查找的时候到hash表中找到对应节点，但是移动它需要知道其前驱节点，因此使用双向链表会比较方便
class LRUCache {
class Node {
int key;
int value;
Node next;
Node pre;
public String toString() {
return "key = "+key +"value = "+value;
}
}
Map<Integer, Node> table = new HashMap<>();
int size = 0;
int capacity;
Node head;
Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
}
private void refresh(Node node) {
if(node != head) {
Node pre = node.pre;
pre.next = node.next;
if(node != tail) {
node.next.pre = pre;
} else {
tail = node.pre;
}
node.pre = null;
node.next = head;
head.pre = node;
head = node;
}
}
public int get(int key) {
if(table.containsKey(key)) {
Node node = table.get(key);
refresh(node);
return node.value;
} else {
return -1;
}
}
public void put(int key, int value) {
if(table.containsKey(key)) {
Node node = table.get(key);
node.value = value;
refresh(node);
} else {
if(capacity <= size) {
table.remove(tail.key);
if(head == tail) {
head = null;
tail = null;
} else {
tail = tail.pre;
tail.next = null;
}
} else {
size++;
}
Node node = new Node();
node.key = key;
node.value = value;
if(head != null) {
node.next = head;
head.pre = node;
} else {
tail = node;
}
head = node;
table.put(key, node);
head = node;
}
}
}