内存管理中有一种页面置换算法叫最近最少使用(LRU)算法，编写程序模拟LRU的运行过程，依次输入分配给某进程的缓存大小（页帧数）和该进程访问页面的次序，用-1作为输入结束标志，初始时缓存为空，要求我们输出使用LRU算法的缺页次数
TestCase 1：
Input：
4
4 3 2 1 4 3 5 4 3 2 1 5 4 -1
Expected Return Value：
9
TestCase 2：
Input：
3
1 2 3 3 2 1 4 3 2 1 -1
Expected Return Value：
7
LRU(Least Recently Used)，常翻译为最近最少使用算法，除了服务于虚拟页式存储管理的页面置换（淘汰）外，在其它方面也有广泛的应用。比如在Android中，对于优先级相同的进程，当内存不足时，系统会依据LRU算法决定杀死哪一个进程；Android系统中常用的图片加载框架也使用了LRU来对图片进行缓存。
根据LRU算法计算缺页中断次数的代码如下：
public class LRU {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
int cacheSize = scan.nextInt();
ArrayList<Integer> taskList = new ArrayList<>();
int page = scan.nextInt();
while (page != -1) { // 输入结束标志
taskList.add(page);
page = scan.nextInt();
}
System.out.println(getMissingNum(cacheSize, taskList));
}
scan.close();
}
public static int getMissingNum(int cacheSize, ArrayList<Integer> taskList) {
int[] cacheQueue = new int[cacheSize]; // 缓存队列，用数组模拟
int tail = -1; // 缓存队列的尾指针
int missingNum = 0; // 缺页次数
boolean isMissing; // 缺页标志
for (int page : taskList) {
isMissing = true;
for (int j = 0; j <= tail; j++) { // 从头到尾遍历缓存队列
if (cacheQueue[j] == page) { // 命中
isMissing = false;
for (int k = j + 1; k <= tail; k++) {
cacheQueue[k - 1] = cacheQueue[k];
}
cacheQueue[tail] = page; // 最近命中的页面移至队尾，使它最后一个被淘汰
break;
}
}
if (isMissing) { // 缺页
missingNum++;
if (tail == cacheSize - 1) { // 缓存已满
for (int k = 1; k <= tail; k++) {
cacheQueue[k - 1] = cacheQueue[k]; // 移出最久未使用的队首页面
}
cacheQueue[tail] = page; // 并将新页面加入到队尾
} else { // 缓存未满
cacheQueue[++tail] = page;
}
}
}
return missingNum;
}
}
