6.5 实例4
最近最少使用缓存

设计和实现最近最少使用缓存（LRUCache）的数据结构，使其支持以下操作。

❑get（key）：如果key存在于缓存中，则获取key的值（始终为正），否则返回-1。

❑put（key，value）：如果key不存在，则插入该组（key，value）。当缓存达到其容量时，它应在插入新项目之前使最近最少使用缓存的项目无效。

思路：主要利用一个列表和哈希表来实现。列表用来保存cache节点，为了使得计算复杂度达到 O （1），使用哈希表来搜索。

对于函数get（key），如果找不到key就返回-1；要么把列表中的元素从当前位置删除，同时把这个元素插入到列表的末端。

对于函数put（key，value），如果列表中已经有key，那么更新其值为value。如果没有key，首先判断列表是不是已经满了。如果满了，需要把列表中第一个元素移出来，同时把（key，value）加入到列表的最后面；如果列表没满，直接把（key，value）加入到列表的最后面。图6-3为LRUCache图解说明。

该方法的时间复杂度为 O （1），空间复杂度为 O （ n ）。示例代码如下。