设计LRU缓存结构

#include <bits/stdc++.h>
using namespace std;

struct P{
    int k, v;
};

class LRU{
public:
    int K;
    list<P> cache;
    unordered_map<int, list<P>::iterator> M;
    LRU(int k){
        K = k;
    }
    int get(int k){
        if(M.find(k) == M.end())
            return -1;
        P p = *M[k];
        cache.erase(M[k]);
        cache.push_front(p);
        return p.v;
    }
    void put(int k, int v){
        if(M.find(k) == M.end()){
            if(cache.size() == K){
                P p = cache.back();
                M.erase(p.k);
                cache.pop_back();
            }
            cache.push_front(P{k,v});
            M[k] = cache.begin();
        }else{
            cache.erase(M[k]);
            cache.push_front(P{k,v});
            M[k] = cache.begin();
        }
    }
};

int main(){
    int n, k, opt, x, y;
    scanf("%d%d", &n, &k);
    LRU lru(k);
    for(int i=0;i<n;i++){
        scanf("%d", &opt);
        if(opt==1){
            scanf("%d%d", &x, &y);
            lru.put(x, y);
        }else if(opt==2){
            scanf("%d", &x);
            printf("%d\n", lru.get(x));
        }
    }
    return 0;
}

思路：将LRU设置为一个双向链表的结构。

如果有新的元素加入，则往双向链表的尾节点中插入；
如果删除最近最少的节点，则删除双向链表的头节点。
为了方便操作双向链表，我们设置了2个头尾的哑节点dummyHead和dummyTail。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    private int capacity; // LRU最大容量
    private Map<Integer, Node> map = new HashMap<>(); // 映射表用于获取元素
    private Node dummyHead = new Node(0, 0); // 哑节点（头）
    private Node dummyTail = new Node(0, 0); // 哑节点（尾）

    /**
     * LRU的节点是一个双向链表中的一个节点
     */
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 初始化最大容量
     * @param capacity LRU最大容量
     */
    public Main(int capacity) {
        this.capacity = capacity;
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    /**
     * 往LRU中添加元素
     * @param key
     * @param value
     */
    public void set(int key, int value) {
        // 如果映射表已包含该key，则要从中删除
        if (map.containsKey(key)) {
            remove(map.get(key));
        }
        // 如果当前元素数量已经达到最大值，要删除LRU的头节点
        if (map.size() == capacity) {
            remove(dummyHead.next);
        }
        Node node = new Node(key, value);
        add(node);
    }

    /**
     * 从LRU中查数据
     * @param key
     * @return
     */
    public int get(int key) {
        // 如果映射表中包含该key，则要先从LRU中删除该节点，再将该节点插入到LRU尾部
        if (map.containsKey(key)) {
            Node node = map.get(key);
            remove(node);
            add(node);
            return node.value;
        }
        return -1;
    }

    /**
     * 删除一个节点
     * @param node
     */
    public void remove(Node node) {
        map.remove(node.key);
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    /**
     * 添加一个节点
     * @param node
     */
    public void add(Node node) {
        map.put(node.key, node);
        node.next = dummyTail;
        node.prev = dummyTail.prev;
        dummyTail.prev = node;
        node.prev.next = node;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Main lruCache = new Main(k);
        while (n-- > 0) {
            int operation = sc.nextInt();
            if (operation == 1) {
                int key = sc.nextInt();
                int value = sc.nextInt();
                lruCache.set(key, value);
            } else if (operation == 2) {
                int value = sc.nextInt();
                System.out.println(lruCache.get(value));
            }
        }
    }
}