题解 | #设计LRU缓存结构#

1.定义一个字典lru_dict，用来存缓存队列里的key，value数据，
2.定义一个数组lru_list，用来存缓存队列里的key。
3.缓存队列主要有2种操作

3.1 存操作，存的时候先通过字典判断存的数据是否在队列中

3.1.1 如果不在队列中，则需要新增，新增需要判断队列是否达到指定长度。

未达到指定长度，则将数据key存入lru_list，key,value存入lru_list。
达到指定长度，则lru_list中的第一位删除（第一位是最先放进去的，最近最少使用）。并将lru_dict中的key删除。然后存数据。

3.1.2 如果在队列中

将数据key从lru_list中删除，然后append到最后。并将数据写到lru_dict中（因为key对应的value有可能变化，所以这里dict要重新写）。

3.2 取数据

通过lru_dict取数据，并更新key在lur_list中的位置。

写在最后：

代码取数据是从字典取，时间复杂度O(1),
数据已在队列中时候，存数据需要遍历找到数据，时间复杂度是o(k)。
可以使用双向链表代替list，通过修改指针可以实现o(1)存数据。