Design and implement a data structure for Least Recently Used (LRU) cache. It
should support the following
operations: get and set.
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.
struct Node { int key; int value; Node* left; Node* right; Node(){left=NULL;right=NULL;} }; class LRUCache{ private: map<int,Node*> hashmap; Node* head; Node* tail; int capacity; int size; void remove(Node* p) { if(p==tail) tail=tail->left; if(p==head) head=head->right; if(p->left!=NULL) p->left->right=p->right; if(p->right!=NULL) p->right->left=p->left; p->left=NULL; p->right=NULL; } void insertfront(Node* p) { //insert 1st location p->left=NULL; p->right=head; if(head!=NULL) head->left=p; head=p; if(tail==NULL) tail=head; } void insertback(Node* p) { //insert 1st location p->left=tail; p->right=NULL; tail=p; if(head==NULL) head=tail; } public: LRUCache(int capacity) { this->capacity=capacity; size=0; head=NULL; tail=NULL; } int get(int key) { map<int ,Node*>::iterator it; it=hashmap.find(key); if(it==hashmap.end()) return -1; Node* pnew=it->second; remove(pnew); insertfront(pnew); return pnew->value; } void set(int key, int value) { map<int ,Node*>::iterator it; it=hashmap.find(key); Node* pnew; if(it!=hashmap.end()) { pnew=it->second; pnew->value=value; remove(pnew); insertfront(pnew); } else { if(size<capacity) { pnew=new Node(); pnew->key=key; pnew->value=value; hashmap.insert(pair<int,Node*>(key,pnew)); insertfront(pnew); size++; } else { pnew=tail; hashmap.erase(hashmap.find(pnew->key)); pnew->key=key; pnew->value=value; hashmap.insert(pair<int,Node*>(key,pnew)); remove(pnew); insertfront(pnew); } } } };
原文：http://www.cnblogs.com/erictanghu/p/3759721.html