题目

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

在 O(1) 时间复杂度内完成这两种操作？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache

LRU 的简单实现

简单的说,就是使用队列,新数据插入到链表头部；
当链表满的时候，将链表尾部的数据丢弃.
每当取缓存时，就将数据移到链表头部.

image.png

使用单个QUEUE就可以简单实现,但为了达到O(1) 时间复杂度,可以使用双向链表(记录数据状态)和哈希表(获取缓存,时间复杂度从O(n)到O(1))来实现.
以下是代码实现,已经有详细注释.

Go实现

type LRUCache struct {
    capacity int
    cache    map[int]*list.Element
    list     *list.List
}

// 数据结构,修改一下,可以把key改为string或其他,
// 但不能是结构体!因为go中map的键的不能是struct
type Pair struct {
    key   int
    value int
}

// 初始化
func Constructor(capacity int) LRUCache {
    return LRUCache{
        capacity,
        make(map[int]*list.Element, capacity),
        list.New(),
    }
}

// 获取值
// 从map中检查是否存在,存在则将其移动到list头
func (l *LRUCache) Get(key int) int {
    if elem, ok := l.cache[key]; ok {
        l.list.MoveToFront(elem)
        return elem.Value.(Pair).value
    }
    return -1
}

//存值
// 先判断是否已存在key
//      存在则将其移动到头部,并更新此值 return
//      不存在,则判断List或map长度是否大于等于capacity
//          list或Map(二者的长度是一样的)已满,则list删除最后一个元素,map也删除该key的元素
//          直接加入到list头部,map添加该元素
//          return
func (l *LRUCache) Put(key int, value int) {
    if elem, ok := l.cache[key]; ok {
        l.list.MoveToFront(elem)
        elem.Value = Pair{key,
            value}
    } else {
        if l.list.Len() >= l.capacity {
            delete(l.cache, l.list.Back().Value.(Pair).key)
            l.list.Remove(l.list.Back())
        }
        l.list.PushFront(Pair{key, value})
        l.cache[key] = l.list.Front()
    }
}

输出结果:

func main() {
    cache := Constructor(2)

    cache.Put(1, 11)
    cache.Put(2, 22)
    fmt.Println(cache.Get(1)) // 返回  1
    cache.Put(3, 33)    // 该操作会使得密钥 2 作废
    fmt.Println(cache.Get(2)) // 返回  -1
    cache.Put(4, 44)    // 该操作会使得密钥 1 作废
    fmt.Println(cache.Get(1))
    fmt.Println(cache.Get(3))
    fmt.Println(cache.Get(4))
}
//result:完全正确
//11
//-1
//-1
//33
//44
```8