LRU简单实现C++
#include <iostream>#include <assert.h>using namespace std;typedef struct node{int num; //页面编号node *next;//node *pre;}node;typedef struct lru_queue{lru_queue(int n, int max){this->n=n;this->max=max;l=NULL;}int n;//当前个数 int max; //最大内存容量node *l; }lru_queue;void print(lru_queue q){node *p=q.l;while(p!=NULL){cout<<p->num<<"\t";p=p->next;}cout<<endl;}void print2(node *p){while(p!=NULL){cout<<p->num<<"\t";p=p->pre;}cout<<endl;}//lru队列l最大容量为max, 调入页面i, 返回调出页面 int insert(lru_queue &q, int i){node *p=q.l;node *pre=NULL;while(p!=NULL && p->num!=i){pre=p;p=p->next;}int res=-1;if(p==NULL){if(q.n == q.max){pre->pre->next=NULL;res=pre->num;delete pre;node *tmp=new node;tmp->num=i;tmp->pre=NULL;tmp->next=q.l;q.l->pre=tmp;q.l=tmp;}else{node *tmp=new node;tmp->num=i;tmp->pre=NULL;tmp->next=q.l;if(q.l!=NULL)q.l->pre=tmp;q.l=tmp;q.n++;}}else{if(p->pre!=NULL){p->pre->next=p->next;}if(p->next!=NULL){p->next->pre=p->pre;}delete p;node *tmp=new node;tmp->num=i;tmp->pre=NULL;tmp->next=q.l;q.l->pre=tmp;q.l=tmp;}return res;}int main(void){lru_queue q(0,3);print(q);assert(-1 == insert(q, 3));print(q);assert(-1 == insert(q, 5));print(q);assert(-1 == insert(q, 1));print(q);assert(-1 == insert(q, 5));print(q);assert(3 == insert(q, 4));print(q);assert(-1 == insert(q, 1));print(q);system("pause");return 0;}
?
?
