LRUCacheDeque.java

class LRUCache {
    
    class Data {
        int key;
        int value; 
        Data(int key, int value) {
            this.key = key; 
            this.value = value; 
        }
    }

    private int capacity; 
    private Map<Integer, Data> m = new HashMap<>(); 
    private Deque<Data> deque = new LinkedList<>(); 
    
    public LRUCache(int capacity) {
        this.capacity = capacity; 
    }
    
    public int get(int key) {
        if (!m.containsKey(key)) return -1;
        Data data = m.get(key);
        deque.remove(data);
        deque.push(data);
        return data.value;
    }
    
    public void put(int key, int value) {
        if (m.containsKey(key)) {
            m.get(key).value = value; 
            get(key);
            return; 
        }
        
        Data data = new Data(key, value);
        m.put(key, data);
        
        if (capacity > 0) {
            deque.push(data);
            capacity--; 
        } else {
            Data evict = deque.removeLast();
            m.remove(evict.key);
            deque.push(data);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */