题目：
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
LCR 031. LRU 缓存 - 力扣（LeetCode）
题解：
思路：
用一个哈希表和一个双端队列，队列里面存储key，哈希存value。get时把对应的key删除，放在队首。put时有旧的则删掉，size够了把队列的最后一个删掉。然后加入，并且覆盖哈希表里面的值。
代码：
class LRUCache {
private int capacity;
private Map<Integer,Integer> cache;
private Deque<Integer> queue;
public LRUCache(int capacity) {
this.capacity=capacity;
this.cache=new HashMap<>();
this.queue=new LinkedList<>();
}
public int get(int key) {
if(cache.containsKey(key)){
queue.remove(key);
queue.offerFirst(key);
return cache.get(key);
}
return -1;
}
public void put(int y, int value) {
if(cache.containsKey(y)){
queue.remove(y);
}
if(queue.size()==capacity){
Integer oldKey=queue.pollLast();
cache.remove(oldKey);
}
cache.put(y,value);
queue.offerFirst(y);
}
}class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
}
}
class MyDeque {
private Node front;
private Node rear;
private int size;
public MyDeque() {
front = null;
rear = null;
size = 0;
}
// 向队列前端添加元素
public void offerFirst(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
front = newNode;
rear = newNode;
} else {
newNode.next = front;
front.prev = newNode;
front = newNode;
}
size++;
}
// 移除指定元素
public void remove(int key) {
Node current = front;
while (current != null) {
if (current.data == key) {
if (current == front) {
pollFirst();
} else if (current == rear) {
pollLast();
} else {
current.prev.next = current.next;
current.next.prev = current.prev;
size--;
}
return;
}
current = current.next;
}
return;
}
// 从队列尾部移除元素
public int pollLast() {
if (isEmpty()) {
return -1;
}
int removedData = rear.data;
if (size == 1) {
front = null;
rear = null;
} else {
rear = rear.prev;
rear.next = null;
}
size--;
return removedData;
}
// 从队列前端移除元素
public int pollFirst() {
if (isEmpty()) {
return -1;
}
int removedData = front.data;
if (size == 1) {
front = null;
rear = null;
} else {
front = front.next;
front.prev = null;
}
size--;
return removedData;
}
// 判断队列是否为空
public boolean isEmpty() {
return size == 0;
}
// 获取队列大小
public int size() {
return size;
}
}完整的双端队列：
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
}
}
public class MyDeque {
private Node front;
private Node rear;
private int size;
public MyDeque() {
front = null;
rear = null;
size = 0;
}
// 向队列前端添加元素
public void addFirst(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
front = newNode;
rear = newNode;
} else {
newNode.next = front;
front.prev = newNode;
front = newNode;
}
size++;
}
// 向队列尾部添加元素
public void addLast(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
front = newNode;
rear = newNode;
} else {
rear.next = newNode;
newNode.prev = rear;
rear = newNode;
}
size++;
}
// 从队列前端移除元素
public int removeFirst() {
if (isEmpty()) {
throw new IllegalStateException("队列为空");
}
int removedData = front.data;
if (size == 1) {
front = null;
rear = null;
} else {
front = front.next;
front.prev = null;
}
size--;
return removedData;
}
// 从队列尾部移除元素
public int removeLast() {
if (isEmpty()) {
throw new IllegalStateException("队列为空");
}
int removedData = rear.data;
if (size == 1) {
front = null;
rear = null;
} else {
rear = rear.prev;
rear.next = null;
}
size--;
return removedData;
}
// 移除指定元素
public void remove(int key) {
Node current = front;
while (current != null) {
if (current.data == key) {
if (current == front) {
removeFirst();
} else if (current == rear) {
removeLast();
} else {
current.prev.next = current.next;
current.next.prev = current.prev;
size--;
}
return;
}
current = current.next;
}
throw new IllegalArgumentException("队列中没有该元素");
}
// 获取队列前端元素
public int getFirst() {
if (isEmpty()) {
throw new IllegalStateException("队列为空");
}
return front.data;
}
// 获取队列尾部元素
public int getLast() {
if (isEmpty()) {
throw new IllegalStateException("队列为空");
}
return rear.data;
}
// 判断队列是否为空
public boolean isEmpty() {
return size == 0;
}
// 获取队列大小
public int size() {
return size;
}
}
