难度：中等 题目来源：力扣（LeetCode） https://leetcode-cn.com/problems/lru-cache

    说明：
    运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
    获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
    写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

    进阶:
    你是否可以在 O(1) 时间复杂度内完成这两种操作？

    示例：
    LRUCache cache = new LRUCache( 2 / 缓存容量 / );
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1); // 返回 1
    cache.put(3, 3); // 该操作会使得密钥 2 作废
    cache.get(2); // 返回 -1 (未找到)
    cache.put(4, 4); // 该操作会使得密钥 1 作废
    cache.get(1); // 返回 -1 (未找到)
    cache.get(3); // 返回 3
    cache.get(4); // 返回 4

    解法：

    1. type Node struct {
    2.     key, value int
    3.     prev, next *Node
    4. }
    5. type LRUCache struct {
    6.     capacity   int
    7.     head, tail *Node
    8.     cache      map[int]*Node
    9. }
    11. func Constructor(capacity int) LRUCache {
    12.     head, tail := &Node{}, &Node{}
    13.     head.next = tail
    14.     tail.prev = head
    15.     return LRUCache{
    16.         capacity: capacity,
    17.         head:     head,
    18.         tail:     tail,
    19.         cache:    make(map[int]*Node),
    20.     }
    21. }
    23. func (t *LRUCache) Get(key int) int {
    24.     node, exist := t.cache[key]
    25.     if !exist {
    26.         return -1
    27.     }
    28.     t.remove(node)
    29.     t.insert(node)
    30.     return node.value
    31. }
    33. func (t *LRUCache) Put(key int, value int) {
    34.     if node, exist := t.cache[key]; exist {
    35.         t.remove(node)
    36.         t.insert(&Node{
    37.             key:   key,
    38.             value: value,
    39.         })
    40.         return
    41.     }
    42.     if len(t.cache) == t.capacity {
    43.         t.remove(t.head.next)
    44.     }
    45.     t.insert(&Node{
    46.         key:   key,
    47.         value: value,
    48.     })
    49. }
    51. func (t *LRUCache) insert(node *Node) {
    52.     node.prev = t.tail.prev
    53.     node.next = t.tail
    54.     t.tail.prev.next = node
    55.     t.tail.prev = node
    56.     t.cache[node.key] = node
    57. }
    59. func (t *LRUCache) remove(node *Node) {
    60.     node.prev.next = node.next
    61.     node.next.prev = node.prev
    62.     delete(t.cache, node.key)
    63. }