LRU实现缓存，O(1)复杂度
queue如果使用LinkedList，移除的方法，不是O1复杂度，需要遍历链表去找到包装的Node节点才可以移除。

class LRUCache {
        // 实现lru,o1复杂度，get-> o1 肯定要使用hashmap去存储
//        HashMap<Integer, Integer> map;   // map的value要存Node节点，否则获取队列中的node不是o1复杂度
        HashMap<Integer, Node> map;
        DoubleNodeList queue;
        int capacity;

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

        public int get(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }
            Node node = map.get(key);
            queue.remove(node);
            queue.addFirst(node);

            return node.value;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                queue.remove(node);
            }
            // 替换node
            Node newNode = new Node(key, value);
            queue.addFirst(newNode);
            map.put(key, newNode);

            if (queue.size > capacity) {
                // 超出容量，清空最后一个
                Node node = queue.removeLast();
                map.remove(node.key);
            }

        }
        class DoubleNodeList{
            Node head;
            Node tail;
            int size;

            DoubleNodeList(){
                head = new Node(-1, -1);
                tail = new Node(-1, -1);
                head.next = tail;
                tail.prev = head;
            }
            void remove(Node node){
                Node prev = node.prev;
                if (prev != null) {
                    prev.next = node.next;
                    node.next.prev = prev;
                }
                size--;
            }

            void addFirst(Node node) {
                Node next = head.next;
                head.next = node;
                node.next = next;   //    head  ---> nextNode       --->>       head ---> newNode ---> nextNode
                next.prev = node;   //          <---                                 <---         <---
                node.prev = head;
                size++;
            }

            Node removeLast() {
                Node prev = tail.prev;
                remove(prev);
                return prev;
            }

            int size(){
                return size;
            }

        }
        class Node{
            int key;
            int value;
            Node prev;
            Node next;
            Node(int key, int value){
                this.key = key;
                this.value = value;
            }
        }
    }