using namespace std
int size
int *w
//定义一个动态数组
struct mem
{
int num
int count
}memBlock[3]={0,0,0,0,0,0}
void LRU()
{
for( int i = 0i <sizei++ )
{
int maxCount = memBlock[0].count
int maxPos = 0
int j = 0
bool bFind = false
for( j = 0j <3j++ )
{
// 标记出count值最大的位置
if( maxCount <memBlock[j].count )
{
maxCount = memBlock[j].count
maxPos = j
}
// 将所有的count值都+1
memBlock[j].count++
// 如果命中，将其count值置为0
if( w[i] == memBlock[j].num )
{
memBlock[j].count = 0
bFind = true
}
}
// 未命中，将count最大的拿来替换
if( !bFind )
{
memBlock[maxPos].num = w[i]
memBlock[maxPos].count = 0
}
for(j = 0j <3j++) //输出
cout <<memBlock[j].num <<" "
cout <<" "<<endl
}
}
int main() //主函数
{
cout<<"请输入需访问的页面数量:"<<endl
cin>>size
w = new int[size]
cout<<"请输入需要访问的页面"<<endl
for(int a=0a<sizea++)
{
cin>>w[a]//输入数组
}
cout<<endl<<"(LRU)"<<endl
LRU()
return 0
}
引用 ： 回答者： floxer | 三级
#include <stdio.h>#include <conio.h>
#include <stdlib.h>
#define MAINMEM 3//主存可存储的页面个数
#define QUEUEMAXLEN 30 //队列最大长度
struct LRUQueue //定义一个特殊的队列
{
int number
int data[MAINMEM]
}lru
void Init()//初始化操作
void Add(int pageID) //加入队列
int Find(int pageID) //查找页面是否在主存中
void Update(int pos) //更新页所在的地址
void PrintQueue() //输出主存内容
int main()
{
int i
int queuelength
int queue[QUEUEMAXLEN]
Init() //初始化操作
printf("请输入队列的长度：")
scanf("%d",&queuelength)
printf("请以此输入队列的页号：")
for(i=0i<queuelengthi++)
{
scanf("%d",&queue[i])
Add(queue[i])
PrintQueue()
}
system("pause")
return 0
}
void Init()
{
lru.number = 0
int i
for(i = 0i<MAINMEMi++)
{
lru.data[i] = -1
}
}
int Find(int pageID)
{
int i
for (i=0i<MAINMEMi++)
{
if(lru.data[i] == pageID)
{
return i
}
}
return 0
}
void Update(int pos)
{
int tmp = lru.data[pos]
int i
for(i = posi<lru.number++i)
{
lru.data[i] = lru.data[i+1]
}
lru.data[lru.number-1] = tmp //将被访问的页放在最后一位，其他的页前移，因为置换时删掉的是主存中第一块放置的页面
}
void PrintQueue()
{
printf("当前内存中的页号:\n")
int i
putch('|')
for(i = 0i<MAINMEMi++)
{
if(lru.data[i] == -1)
printf(" |")
else
printf("%d |",lru.data[i])
}
putch('\n')
}
void Add(int pageID)
{
printf("当前访问的页面：%d\n",pageID)
if(lru.number<MAINMEM) //如果主存没有填满
{
int pos = Find(pageID)
if(pos)
{
Update(pos)
}
else
{
lru.data[lru.number++]=pageID
}
}
else
{
int pos = Find(pageID)
if(pos)
{
Update(pos)
}
else
{
int i
for(i=0i<MAINMEM-1i++)
{
lru.data[i]=lru.data[i+1] //数据左移一个单位
}
lru.data[i]=pageID//加入新数据
}
}
}
LRU是Least Recently Used的缩写，即最近最少使用算法，应用面非常的广泛，比如redis当中的内存淘汰策略。因为计算机的内存都是有限的，当用户访问的数据如果存在内存当中直接返回的给用户的话，效率会非常快，但是如果内存不存在，在去磁盘里面查找的，效率会大打折扣。所以我们希望在有限的内存空间当中，多存放点热点数据，用户不经常访问的数据，尽量淘汰掉，避免占用内存空间。
使用双向链表来实现LRU 这篇文章已经用双向链表来实现过LRU算法了，但是基于双向链表的特性，使得该算法的时间复杂度为O(n)，显然不是最优的算法，那么有没有算法，可以达到O(1)，当然是有的，早早的计算机科学家已经想到，并且已经实现了。
在笔者介绍接下来的内容时，还是希望先了解一下两篇博文：
一、 图解HashMap原理
二、 图解LinkedHashMap
之前使用双向链表去实现LRU算法时，时间复杂度没有达到O(1)，主要原因在于遍历结点时，带来的时间开销，那么换句话说，要实现遍历结点时，时间复杂度为O(1)，第一时间想到的应该是hash数组，但是hash算法可能会存在不同的key值，产生相同的hash值，那么可以将不同key，但是相同hash值的结点，以单链表的形式存放。这样仅仅是实现了存取时间复杂度为O(1)，如何实现数据能够按访问顺序存放呢？并且增删的时间复杂度为O(1)，这个可以使用双向链表来实现，所以综合来讲，就是实现散列数组+双向链表来使用LRU，可以达到时间复杂度为O(1)。
逻辑视图如下:
咋一看这个图乱的很，稍微解释一下，如果感觉理解上有点困难，可以先去了解一下之前推荐的两篇博文，那里会介绍的更加详细一点。
1.最左侧其实就是一个普通的数组，数组的大小必须是2的倍数，这个原因是什么呢？因为这个数组的存放方式是散列的，意思就是需要key.hashcode & (length -1)才能得出存放位置的方式，hash的好处是可以根据key值，在时间复杂度为O(1)的前提找到对应的存放位置，这也是我们的初衷，说到这里其实还没有解释为什么一定要是2的倍数，因为2的倍数-1，这个数的二进制，一定全是1，比如16-1=15，二进制表示就是1111，&运算符其实就是将值全部化成二进制逐位与，比如10111011 &1111 = 1011 = 11，但是如果不是2的倍数，比如7-1=6，化成二进制就是0110，由于末位是0，不管什么二进制值与0110做&运算，一定是偶数，这样会导致散列分布不均匀。
2.不同key值，相同hash值，如何存放呢？相同的hash值做与运算一定能够得到相同的数组脚标，这些结点，以单链表的形式存在，就是图中数组右侧的单链表。
3.如何实现按访问顺序？上图除去数组和挂在数组右侧的单链表，还有绿色和黄色的单向箭头，在右上角还有一个双向链表的头指针。其实这些箭头就是维护不同结点的访问顺序，即双向链表。
总上所述，这种数据结构定义的结构体如下：
class Node{
Object key//存放key值，用于计算存放数组脚标位置
Object value//存放元素值
int hash//存放key.hashcode
Node next//维护单链表顺序
Node before//维护双向链表顺序
Node after
}
笔者用java实现如下，感兴趣可以用自己喜欢的语言去实现一遍，加深理解：
其实以上实现底层原理就是LinkedHashMap的实现原理，只不过笔者做了一些简化，去掉了繁琐的继承，扩容等，突出了算法核心，如果读者感兴趣也可以去研究一下LinkedHashMap的源码。
使用LinkedHashMap来实现LRU算法：
看起来是不是简单了很多，因为LinkedHashMap底层已经封装好了，我们直接调用就好，但是作为一个想要变优秀的码农，一定要知其然知其所以然。
使用散列+双向链表的方式是如何实现O(1)复杂度的？在实现LRU算法过程中，无非两种操作，查找和修改，使用散列数组实现查找时间复杂度为O(1)，使用双向链表实现修改复杂度为O(1)，并且双向链表还可以维护访问顺序，所以使用这种方式，可以达到O(1)。
