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.
Key Idea:
1. Here we need a queue to dequeue the least recently item. However as we need the randomly access of the items for set and get, queue in C++ STL will not meet the standard. Then, we need a doubly linked list to build the queue.
2. In the doubly linked list, we should have key, value, pre, and nxt in the list node.
3. In order to find the node via the key each time fast, we need a hashmap, in C++, we could use
map<int, QNode*>.
4. When get(key) called, the position of the node if existed should moved to the last as well.
5. When set(key, val) called, if existed, then change value and move to the last, pay attention for one node list and if current is on front or rear node; if not existed, check if full or not, if full, dequeue; then insert to the last node.
SHOULD ALWAYS PAY ATTENTION TO THE SPECIAL CASES: only one node, current is front or last.
struct QNode{
int key;
int value;
QNode* pre;
QNode* nxt;
QNode(int k, int val){key = k; value = val;}
};
struct Queue{
// current count of contents.
int count;
// total capacity
int numofnode;
QNode* front;
QNode* rear;
Queue(int n){
count = 0;
numofnode = n;
front = rear = NULL;
}
bool IsQueueFull(){
return count == numofnode;
}
bool IsQueueEmpty(){
return rear == NULL;
}
void Dequeue(){
if(IsQueueEmpty()) return;
//if only one node in the queue
if(front == rear){
delete front;
front = NULL;
rear = NULL;
count = 0;
return;
}
QNode* temp = front;
front = temp->nxt;
front->pre = NULL;
delete temp;
--count;
}
void Enqueue(QNode* node){
if(IsQueueFull())
Dequeue();
if(IsQueueEmpty()){
node->nxt = NULL;
node->pre = NULL;
front = node;
rear = node;
count = 1;
return;
}
rear->nxt = node;
node->pre = rear;
node->nxt = NULL;
rear = node;
++count;
}
};
class LRUCache{
public:
LRUCache(int capacity) {
LRUqueue = new Queue(capacity);
}
int get(int key) {
QNode* cur = LRUmp[key];
//if current key is not in the map
if(!cur) return -1;
else{
if(LRUqueue->front != LRUqueue->rear){
if(cur == LRUqueue->rear){
return cur->value;
}
if(cur == LRUqueue->front){
LRUqueue->front = cur->nxt;
}else{
cur->pre->nxt = cur->nxt;
cur->nxt->pre = cur->pre;
}
LRUqueue->rear->nxt = cur;
cur->pre = LRUqueue->rear;
cur->nxt = NULL;
LRUqueue->rear = cur;
}
return cur->value;
}
}
void set(int key, int value) {
QNode* cur = LRUmp[key];
// if not in the map, we need to insert to the queue and the map.
if(!cur){
cur = new QNode(key, value);
//check if the queue is full
if(LRUqueue->IsQueueFull()){
LRUmp.erase(LRUqueue->front->key);
//enqueue the current value.
LRUqueue->Enqueue(cur);
LRUmp[key] = cur;
}else{
LRUqueue->Enqueue(cur);
LRUmp[key] = cur;
}
}else{
// if the key->node is in the map and queue
if(LRUqueue->front != LRUqueue->rear){
if(cur == LRUqueue->rear){
cur->value = value;
LRUmp[key] = cur;
return;
}
if(cur == LRUqueue->front){
LRUqueue->front = cur->nxt;
}else{
cur->pre->nxt = cur->nxt;
cur->nxt->pre = cur->pre;
}
LRUqueue->rear->nxt = cur;
cur->pre = LRUqueue->rear;
cur->nxt = NULL;
LRUqueue->rear = cur;
}
cur->value = value;
LRUmp[key] = cur;
}
}
private:
Queue* LRUqueue;
map<int, QNode*> LRUmp;
};
