运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
class LRUCache {
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new Node();
tail = new Node();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node == null) {
Node newNode = new Node(key, value);
cache.put(key, newNode);
add(newNode);
size++;
if (size > capacity) {
Node removed = removeTail();
cache.remove(removed.key);
size--;
}
} else {
node.value = value;
moveToHead(node);
}
}
class Node {
int key;
int value;
Node pre;
Node next;
public Node() {
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, Node> cache = new HashMap<>();
private int size;
private int capacity;
private Node head, tail;
private void remove(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private Node removeTail() {
Node temp = tail.pre;
remove(temp);
return temp;
}
private void moveToHead(Node node) {
remove(node);
add(node);
}
private void add(Node node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
}