题目：
设计和实现一个 LRU (最近起码应用) 缓存机制 。
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存。
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
void put(int key, int value) 如果关键字曾经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到下限时，它应该在写入新数据之前删除最久未应用的数据值，从而为新的数据值留出空间。
是否能够在 O(1) 工夫复杂度内实现这两种操作？
解决办法：
哈希表 + 双向链表
1、双向链表：节点凑近头部是最近应用的，凑近尾部是最久未应用的，在双向链表的头部增加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。
2、哈希表：通过缓存数据的键映射到其在双向链表中的地位（定位），查找节点工夫复杂度：o(1)。
3、为了在链表操作过程中更少的判断头尾节点是否为null，采纳哨兵机制，头尾都增加哨兵（与传统双向链表性能貌似无很大差异，只是判断nullptr较多容易出错）。
源码剖析：
//节点定义struct DLinkedNode{ int key, value; //节点在hash表里的键值和值 DLinkedNode* prev; //此节点的前驱节点 DLinkedNode* next; //此节点的后继节点 DLinkedNode() :key(0), value(0), prev(nullptr), next(nullptr) {} //构造函数，赋值key和value DLinkedNode(int _key, int _value) :key(_key), value(_value), prev(nullptr), next(nullptr) {} //带参构造函数（重载）}; //LRU 缓存类class LRUCache {private: unordered_map<int, DLinkedNode*> cache; //哈希映射表 DLinkedNode* head; //双向链表头结点 DLinkedNode* tail; //双向链表尾结点 int size; //以后节点个数 int capacity; //LRU缓存最大节点个数（容量） public: LRUCache(int _capacity) :capacity(_capacity), size(0){ head = new DLinkedNode(); //哨兵节点，造成环形链表 tail = new DLinkedNode(); head->next = tail; tail->prev = head; } //获取数据 int get(int key){ //判断是否缓存命中 if (!cache.count(key)){ return -1; } //因为最近拜访了，所以移到链表最前端 DLinkedNode* node = cache[key]; moveToHead(node); return node->value; } //插入数据 void put(int key, int value){ //如果缓存未命中，则创立新的节点，插入哈希，移到链表头部（最近拜访数据） //缓存区满的话，要移除链表尾部节点，因为是最久未拜访的数据 if (!cache.count(key)){ DLinkedNode* node = new DLinkedNode(key, value); cache[key] = node; addToHead(node); ++size; if (size > capacity){ DLinkedNode* removed = removeTail(); cache.erase(removed->key); delete removed; --size; } } else{ //取到此节点 DLinkedNode* node = cache[key]; //赋值新值 node->value = value; //移到链表头部，变为最近拜访的数据 moveToHead(node); } } private: void addToHead(DLinkedNode* node){ node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; } void removeNode(DLinkedNode* node){ node->prev->next = node->next; node->next->prev = node->prev; } //挪动节点到头部 void moveToHead(DLinkedNode* node){ //移除掉此节点 removeNode(node); //最近拜访数据放到头部 addToHead(node); } //移除尾部节点 DLinkedNode* removeTail(){ DLinkedNode* node = tail->prev; removeNode(node); return node; }}; /*测试数据：#include<iostream>#include<unordered_map>using namespace std; int main(){ LRUCache* lRUCache = new LRUCache(2); lRUCache->put(1, 1); // 缓存是 {1=1} lRUCache->put(2, 2); // 缓存是 {1=1, 2=2} lRUCache->get(1); // 返回 1 lRUCache->put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache->get(2); // 返回 -1 (未找到) lRUCache->put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache->get(1); // 返回 -1 (未找到) lRUCache->get(3); // 返回 3 lRUCache->get(4); // 返回 4 system("pause"); return 0;}*/