LRU缓存

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int capacity = scanner.nextInt();
        String[] commands = new String[n];
        LRUCache lru = new LRUCache(capacity);
        //因为第一行输入的命令和第二行输入的命令是换行的
        //所以我们要多加一个nextLine()去吸收那个空格
        scanner.nextLine();
        for(int i = 0; i < n; i++){
            commands[i] = scanner.nextLine();
        }
        
        for(String command : commands){
            String[] s = command.split(" ");
            if(s.length == 2){
                System.out.println(lru.get(Integer.parseInt(s[1])));
            }
            else{
                lru.put(Integer.parseInt(s[1]),Integer.parseInt(s[2]));
            }
        }                
    }
}

class LRUCache{
    
    static class BinaryListNode{
        int key;
        int val;
        BinaryListNode next;
        BinaryListNode prev;
        BinaryListNode(){}
        BinaryListNode(int key, int val){this.key = key; this.val = val;}
    }
    
    private int size;
    private int capacity;
    private BinaryListNode dummyHead;
    private BinaryListNode dummyTail;
    private Map<Integer, BinaryListNode> cache = new HashMap<>();
    
    public LRUCache(int capacity){
        this.size = 0;
        this.capacity = capacity;
        dummyHead = new BinaryListNode();
        dummyTail = new BinaryListNode();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    public int get(int key){
        if(!cache.containsKey(key)){
            return -1;
        }
        BinaryListNode node = cache.get(key);
        removeToHead(node);
        return node.val;
    }
    
    public void put(int key, int value){
        if(!cache.containsKey(key)){
            BinaryListNode newNode = new BinaryListNode(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            size++;
            if(size > capacity){
                BinaryListNode node = removeTail();
                cache.remove(node.key);
                size--;
            }
        }
        else{
            BinaryListNode node = cache.get(key);
            node.val = value;
            removeToHead(node);
        }
    }
    
    public void addToHead(BinaryListNode node){
        node.next = dummyHead.next;
        node.prev = dummyHead;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }
    
    public void removeNode(BinaryListNode node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
    
    public void removeToHead(BinaryListNode node){
        removeNode(node);
        addToHead(node);
    }
    
    public BinaryListNode removeTail(){
        BinaryListNode tail = dummyTail.prev;
        removeNode(tail);
        return tail;
    }    
}

import java.util.*;
public class Main {

    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        String line = input.nextLine();
        String[] nums = line.split(" ");
        int N=Integer.parseInt(nums[0]);
        int M=Integer.parseInt(nums[1]);
        LRUCache cache = new LRUCache(M);
        for(int i=0;i<N;i++){
            String str=input.nextLine();
            String[] s = str.split(" ");
            if(str.startsWith("PUT")){
                cache.put(Integer.parseInt(s[1]),Integer.parseInt(s[2]));
            }else {
                System.out.println(cache.get(Integer.parseInt(s[1])));
            }
        }
    }

    static class LRUCache extends LinkedHashMap<Integer,Integer>{
        private int capacity;

        public LRUCache(int capacity) {
            //第三个参数代表可以按访问元素的顺序排序
            super(capacity,0.75F,true);
            this.capacity=capacity;
        }


        public int get(int key) {
            return super.getOrDefault(key,-1);
        }


        public void put(int key, int value) {
            super.put(key,value);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    }

}