1. package Fifo; 2. 3. //LRU 最久未使用淘汰算法 4. public class MyLRU { 5. LinkNode first; 6. LinkNode last; 7. int maxSize = 10; // 缓存的尺寸 8. int currentSize = 0; public MyLRU(int maxSize) { 9. 10. this.maxSize = maxSize; 11. } 12. public void changePage(Page p) {// LRU 算法,每次读取新页都 重新调整缓存结构 13. LinkNode newItem = new LinkNode(); 14. newItem.page = p; 15. newItem.next = null; 16. 17. if (first == null) { 18. first = newItem; 19. last = first; 20. currentSize++; 21. } else { 22. LinkNode current = first; 23. LinkNode trailCurrent = first; 24. for (int i = 0; i < currentSize; i++) {// 先判断缓 存中有没有该页,有则删除 25. if (current.page.getNum() == p.getNum()) { 26. if (current == first) { //有该页且在队 头 27. first = first.next; 28. if (first == null) //删除后, 如果缓 存为空,重设 last 29. last = first; 30. } else { 31. trailCurrent.next = current.next; 32. if (current == last) { //如果删除的是 最后一个,重设 last 指针 33. last = trailCurrent; 34. } 35. } 36. currentSize--; 37. break; 38. } 39. trailCurrent = current;
current = current.next; } //删除完后,在队尾添加 if (currentSize < maxSize) {//缓存未满时的插入 if (first == null) { //如果缓存为空, 添加并重 设 first、last 指针 45. first = newItem; 46. last = first; 47. } else { //如果缓存不为空添加到 尾部 48. last.next = newItem; 49. last = newItem; 50. } 51. currentSize++; 52. } else { //缓存已满时,先删除队 头,再向队尾插入 53. first = first.next; 54. currentSize--; 55. last.next = newItem; 56. last = newItem; 57. currentSize++; 58. } 59. } 60. print(); 61. } 62. public void print() { 63. LinkNode current = first; 64. System.out.println(); 65. while (current != null) { 66. System.out.print(current.page.getNum() + ","); 67. current = current.next; 68. } 69. } 70. 71. public static void main(String[] args) { 72. MyLRU fifo = new MyLRU(10); 73. int arr[] = { 2, 2, 5, 3, 3, 7, 2, 5, 4, 7, 7, 4, 6, 9, 10, 3, 53, 45, 74. 56, 67, 89, 23, 53 }; 75. for (int i = 0; i < arr.length; i++) { 76. fifo.changePage(new Page(arr[i])); 77. } 78. } 79.}
40. 41. 42. 43. 44.