#include<iostream>
#include<map>

using namespace std;

typedef struct Node
{
int data;
struct Node *next;
struct Node(int element) :data(element),next(NULL) {};
}node;

node* inserts(node* proot, int data)
{
node *ptmp = new node(data);
ptmp->next = proot;
return ptmp;
}

node *deletenode(node* proot, int data)
{
node *res = proot;
if (proot->data =http://www.mamicode.com/= data)
{
node *ptmp = proot;
res = proot->next;
delete ptmp;

}
else if(proot->next!=NULL&&proot->next->data != data)
{
proot = proot->next;
}
else if(proot->next!=NULL&&proot->next->data=http://www.mamicode.com/=data)
{
node *ptmp = proot->next;
proot->next = ptmp->next;
delete ptmp;
}
return res;
}
node* pop(node *proot)
{
node* res = proot;
if (proot == NULL)
return res;
node *ptmp = proot->next;
while (ptmp->next)
{
proot = ptmp;
ptmp = ptmp->next;
}
if (ptmp->next == NULL)
{
proot->next = NULL;
delete ptmp;
}
return res;
}
void printfd(node *proot)
{
while (proot)
{
cout << proot->data << " ";
proot = proot->next;
}
cout << endl;
}

class LRU {
public:
LRU(int length) :root(NULL),len(length) {};
void insert(int data);
void printfs() {
printfd(root);
}
private:
node *root;
map<int, int> vec;
int len;
};

void LRU::insert(int data)
{
if (vec.count(data) > 0)
{
root = deletenode(root, data);
root = inserts(root, data);
}
else
{
if (vec.size() >= len)
{
root = pop(root);
root = inserts(root, data);
vec[data] = data;
}
else
{
root = inserts(root, data);
vec[data] = data;
}
}
}

int main()
{
LRU test(5);
test.insert(1);
test.insert(2);
test.insert(3);
test.printfs();
test.insert(4);
test.insert(5);
test.printfs();
test.insert(6);
test.printfs();
test.insert(7);
test.insert(8);
test.insert(9);
test.printfs();
}

c++初步实现的一个LRU