0x01:先进先出算法
先进先出，先进先出。实际上，在操作系统的设计理念中，FIFO的思想被用在很多地方，比如作业调度(先到先得)。为什么很多地方都用这个原理？因为这个原理简单，符合人们的惯性思维，公平，实现简单，可以直接利用数据结构中的队列来实现。
在先进先出缓存的设计中，核心原则是如果一条数据先进入缓存，就应该先将其消除。也就是说，当缓存已满时，首先进入缓存的数据应该被清除。先进先出缓存应支持以下操作；
Get(key):如果key存在于Cache中，则返回对应的值；否则，返回-1；
Set(key，value):如果key存在于Cache中，则重置value值；如果密钥不存在，密钥将被插入缓存。如果缓存已满，最早进入缓存的数据将被删除。
例如，如果缓存大小为3，则访问数据序列为set (1，1)、set (2，2)、set (3，3)、set (4，4)、get (2)和set (5，5)
然后，缓存中的数据会发生如下变化：
(1，1)集(1，1)
(1，1) (2，2)集合(2，2)
(1，1) (2，2) (3，3)集合(3，3)
(2，2) (3，3) (4，4)集合(4，4)
(2，2) (3，3) (4，4) get(2)
(3，3) (4，4) (5，5)组(5，5)
那么用什么数据结构来实现呢？
下面提供了一个实现思路：
双向链表用于存储数据，当新数据进来时，它被添加到链表的末尾。如果缓存中充满数据，则删除链表头部的数据，然后将新数据添加到链表的末尾。当访问数据时，如果数据存在于缓存中，则返回相应的值；否则，返回-1。如果想提高访问效率，可以使用hashmap保存链表中每个键的对应位置。
00-1010 LFU(最少使用)最近最少使用的算法。它基于“如果一条数据在最近一段时间内不经常使用，它就不太可能在未来使用”的思想。
注意LFU算法和LRU算法的区别。LRU的淘汰规则是基于准入时间，LFU是基于准入时间。举个简单的例子：
假设缓存大小为3，数据访问顺序为set (2，2)，set (1，1)，get (2)，get (1)，get (2)，set (3，3)，set (4，4)，
那么在集合(4，4)处，LFU算法应该被消除(3，3)，LRU应该被消除(1，1)。
那么LFU缓存应该支持以下操作：
Get(key):如果key存在于Cache中，则返回对应的值；否则，返回-1；
Set(key，value):如果key存在于Cache中，则重置value值；如果该键不存在，则将该键插入缓存，如果缓存已满，则删除最少访问的数据。
为了消除最少使用的数据，LFU算法最简单的设计思想是用一个数组来存储数据项，用hashmap来存储每个数据项在数组中的对应位置，然后为每个数据项设计一个访问频率。当数据项被命中时，访问频率会自动增加，访问频率最低的数据在被消除时会被消除。这样，在插入数据和访问数据时，可以达到O(1)的时间复杂度。在剔除数据时，可以通过选择算法得到数组中应该剔除的数据项的索引，索引位置的内容可以用新的数据内容替换。这样，消除数据的时间复杂度为O(n)。
另一种实现思路是使用hashmap，在插入和删除小的顶部堆时可以达到O(logn)的时间复杂度，所以效率比第一种实现方法更高效。
如果有朋友有更高效的实现方法(比如O(1)时间复杂度)，请讨论一下，不胜感激。
0x02：LFU算法
LRU算法的设计原则是，如果一条数据最近没有被访问过，将来就不太可能被访问。也就是说，当有限的空间充满数据时，最长时间没有被访问的数据应该被消除。采用什么数据结构实现LRU算法？大多数人可能会想到使用数组来存储数据，为每个数据项标记访问时间戳，递增数组中数据项的时间戳，并将新数据项的时间戳设置为0，并在每次插入新数据项时将其插入数组中。每次访问数组中的数据项时，被访问数据项的时间戳被设置为0。当数组空间已满时，删除时间戳最大的数据项。
这个实现思路很简单，但是有哪些缺陷呢？需要不断维护数据项的访问时间戳。另外，在插入数据、删除数据、访问数据时，时间复杂度为O(n)。
那么有没有更好的方法实现呢？
那就是使用链表和hashmap。当需要插入新数据项时，如果新数据项存在于链表中(通常称为命中)，则节
点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。总结一下：根据题目的要求，LRU Cache具备的操作：
1）set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除，并移动到链表的头部；若果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除即可。
2）get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。