题解 | #设计LRU缓存结构#

import java.io.*;
import java.util.*;
public class Main{
    static Node head;
    static Node tail;
    static Map<Integer,Node> map;
    static int size = 0;
    public static void main(String[] args) throws IOException{
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
        map = new HashMap<>();
        BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int k = Integer.parseInt(s1[1]);
        int i = 0;
        while(i < n){
            String[] s2 = br.readLine().split(" ");
            if(s2[0].equals("1")){
                int key = Integer.parseInt(s2[1]);
                int value = Integer.parseInt(s2[2]);
                set(key,value,k);
            }else if(s2[0].equals("2")){
                int key = Integer.parseInt(s2[1]);
                System.out.println(get(key));
            }
            i++;
        }
    }
    public static void set(int key,int value,int k){
        Node a = map.get(key);
       if(a == null){
            Node node = new Node(key,value);
            size++;
           if(size > k){
              Node b = removetail();
              map.remove(b.key);
               size--;
           }
           map.put(key,node);
            addhead(node);
       }else{
           a.value = value;
           tohead(a);
       }
       
    }
     public static int get(int key){
            Node a = map.get(key);
            if(a == null){
                return -1;
            }
            tohead(a);
            return a.value;
        }
    public static void addhead(Node node){
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }
    public static Node removetail(){
        Node a = tail.pre;
        a.pre.next = tail;
        a.next = null;
        tail.pre = a.pre;
        a.pre = null;
        return a;
    }
    public static void tohead(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
    }
}
class Node{
    int key;
    int value;
    Node pre;
    Node next;
    public Node(int key,int value){
        this.key = key;
        this.value = value;
    }
    public Node(){
        
    }
}