# 146

這題想要考 LRU 這種資料結構的實現，要想實作，我們就要先了解 LRU 的行為。

Concept:

用deque來存所有的key，每次get或set某個key就把它從deque拿出來，從end塞回去

用Map來存key和value的mapping

1. set: 確認key有沒有存在map中，若有就在map裡改值，若沒有就看目前deque的大小有沒有超過capacity，若沒超過，就加進deque和map，若超過了，就呼叫deque.poll()，最後把新的key從end塞進去
2. get: 在map裡面找key，若不存在，return -1，若存在，更新deque並return value。

public class LRUCache {
    Deque<Integer> deque;
    Map<Integer, Integer> map;
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        deque = new LinkedList<>();
        map = new HashMap<>();
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }else{
            deque.remove(key);
            deque.addLast(key);
            return map.get(key);
        }
    }

    public void set(int key, int value) {
        if(map.containsKey(key)){
            map.put(key, value);
            deque.remove(key);
            deque.addLast(key);
        }else{
            if(deque.size()<capacity){
                deque.addLast(key);
                map.put(key,value);
            }else{
                int tmpKey = deque.poll();
                map.remove(tmpKey);
                deque.addLast(key);
                map.put(key,value);
            }
        }
    }
}