Description
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:getandset.
get(key)- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value)- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Finally, you need to return the data from each get
Example
Example1
Input:
LRUCache(2)
set(2, 1)
set(1, 1)
get(2)
set(4, 1)
get(1)
get(2)
Output: [1,-1,1]
Explanation：
cache cap is 2，set(2,1)，set(1, 1)，get(2) and return 1，set(4,1) and delete (1,1)，because （1,1）is the least use，get(1) and return -1，get(2) and return 1.
Example 2:
Input：
LRUCache(1)
set(2, 1)
get(2)
set(3, 2)
get(2)
get(3)
Output：[1,-1,2]
Explanation：
cache cap is 1，set(2,1)，get(2) and return 1，set(3,2) and delete (2,1)，get(2) and return -1，get(3) and return 2.
思路：
链表模拟
涉及删除和移动操作，使用链表，链表是有序的，一直维护，近期最多使用的放于尾部，那么每次缓存达到上限的时候，删除头部即可，其余为链表的基础操作模拟即可。
答案值得借鉴的是将node移到最后，还有删除头节点以及加入新节点用分开的函数实现，调用起来十分清晰，还有就是将前序节点存储在hash_map中，非常方便。
还要注意pop_front的时候要先把元素加进去再pop不然会报错。
代码：
