import?java.util.linkedList;

public?class?LRU?{

????private?linkedList?stack;//模擬頁面‘寄存器‘
????private?int?size;//寄存器大小表示一共可裝入多少頁面
????
????public?LRU（int?size）?{
????????stack?=?new?linkedList<>（）;
????????this.size?=?size;
????}

????//LRU算法簡單實現返回一共未命中的次數
????public?int?lru（int[]?pageNumbers）
????{
????????if（size?<=?0?||?pageNumbers?==?null）
????????????throw?new?IllegalArgumentException（“illegal?arugments“）;
????????
????????if（pageNumbers.length?<=?size）
????????????return?pageNumbers.length;
???????
????????int?unhit?=?0;
????????????
????????for（int?i?=?0;?i?????????{
????????????int?index?=?isHit（pageNumbers[i]）;
????????????if（index?==?-1）
????????????{
????????????	unhit?=?processUnHit（pageNumbers[i]?unhit）;
????????????	System.out.println（“??“+pageNumbers[i]+“??“+“缺頁“）;
????????????}
????????????else
????????????{
????????????????ifHit（pageNumbers[i]?index）;
????????????????System.out.println（“??“+pageNumbers[i]+“??“+“命中“）;
????????????}
????????}
????????return?unhit;
????}
????
????/**
?????*?
?????*?@param?pageNumber?判斷?pageNumber是否hit
?????*?@return?-1?表示?unhit?其他表示hit
?????*/
????private?int?isHit（int?pageNumber）{
????????return?stack.indexOf（pageNumber）;
????}
????
????/**
?????*?當棧未滿時未命中的頁面號直接入棧;棧滿時需要替換頁面先選中一個頁面（棧底）刪除然后Push新頁面
?????*?@param?pageNumber?未命中的頁面號
?????*?@param?count?當前未命中次數
?????*?@return?更新后的未命中的次數
?????*/
????private?int?processUnHit（int?pageNumber?int?count）{
????????if（isFull（））
????????????stack.removeLast（）;//刪除最久未訪問的頁面
????????stack.push（pageNumber）;//放入最近訪問的頁面
????????count++;//未命中的次數加1
????????return?count;
????}
????
????//命中更換
????private?void?ifHit（int?pageNumber?int?index）{
????????????stack.push（stack.remove（index））;
????}
????
????//判斷‘寄存器‘棧是否已經滿了
????private?boolean?isFull（）
????{
????????if（stack.size（）?????????????return?false;
????????else
????????????return?true;
????}
????
????//test
????public?static?void?main（String[]?args）?{
????????int[]?pageNumbers?=?{47117245718};
????????int?size?=?3;
????????for（int?i?=?0;?i?????????	System.out.print（“??“+pageNumbers[i]+“??“）;
????????System.out.println（）;
????????LRU?lru?=?new?LRU（size）;
????????System.out.println（“缺頁率：“+lru.lru（pageNumbers）+“/“+pageNumbers.length）;
????}
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2016-11-11?14:06??squid\
?????文件?????????301??2016-11-11?10:07??squid\.classpath
?????文件?????????381??2016-11-11?10:07??squid\.project
?????目錄???????????0??2016-11-11?14:06??squid\.settings\
?????文件?????????598??2016-11-11?10:07??squid\.settings\org.eclipse.jdt.core.prefs
?????目錄???????????0??2016-11-11?14:06??squid\bin\
?????文件????????2503??2016-11-11?11:37??squid\bin\LRU.class
?????目錄???????????0??2016-11-11?14:06??squid\src\
?????文件????????2712??2016-11-11?11:37??squid\src\LRU.java