定义：

LRU是Least Recently Used的缩写，即最近最少使用页面置换，是为虚拟页式存储管理服务的，是根据页面调入内存后的使用情况进行决策了。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU算法就是将最近最久未使用的页面予以淘汰。

可以用一个特殊的栈来保存当前正在使用的各个页面的页面号。当一个新的进程访问某页面时，便将该页面号压入栈顶，其他的页面号往栈底移，如果内存不够，则将栈底的页面号移除。这样，栈顶始终是最新被访问的页面的编号，而栈底则是最近最久未访问的页面的页面号。

 

实现代码：

1 import java.util.HashSet;  2 import java.util.Set;  3   4 public class LRU2
     
       {  5       6     private Node
      
        head;  7       8     private Node
       
         tail;  9  10     private int maxcapacity = 3; 11      12     private int count = 0; 13      14     private final Set
        
          valueSet = new HashSet
         
          (); 15      16     LRU2(int maxcapacity){ 17         this.maxcapacity = maxcapacity; 18     } 19      20     LRU2(){ 21     } 22      23     public boolean add(E e) { 24         Node newNode = new Node(e); 25         if(count == 0) { 26             this.head = newNode; 27             this.tail = newNode; 28             valueSet.add(e); 29             count++; 30             return true; 31         } 32          33         if(valueSet.contains(e)) { 34             if(count == 1) { 35                 return false; 36             }else if(e == head.value) { 37                 head.next.before = null; 38                 head = head.next; 39                 tail.next = newNode; 40                 newNode.before = tail; 41                 tail = newNode; 42                 return false; 43             }else if( e == tail.value) { 44                 return false; 45             }else { 46                 Node temp = head.next; 47                 while(temp != null) { 48                     if(e == temp.value) { 49                         Node b = temp.before; 50                         b.next = temp.next; 51                         temp.next.before = temp.before; 52                         temp.next = null; 53                         tail.next = temp; 54                         temp.before = tail; 55                         tail = temp; 56                         return false; 57                     }else { 58                         temp = temp.next; 59                     } 60                 } 61             } 62         }else { 63             tail.next = newNode; 64             newNode.before = tail; 65             tail = newNode; 66             count++; 67             valueSet.add(e); 68             if(count > maxcapacity) { 69                 E v = head.value; 70                 Node h = head.next; 71                 h.before = null; 72                 head = h; 73                 count--; 74                 valueSet.remove(v); 75             } 76             return true; 77         } 78          79         return false; 80     } 81      82     class Node
          
            { 83 Node
           
             before ; 84 Node
            
              next ; 85 E value; 86 87 Node(E e){ 88 this.value = e; 89 } 90 91 } 92 93 94 public void printNodes() { 95 Node temp = head; 96 while(null != temp) { 97 System.out.print(temp.value + " "); 98 temp = temp.next; 99 }100 System.out.println();101 }102 103 104 public static void main(String[] args) {105 LRU2
             
               l = new LRU2
              
               (4);106 l.add(1);107 l.printNodes();108 l.add(2);109 l.printNodes();110 l.add(3);111 l.printNodes();112 l.add(3);113 l.printNodes();114 l.add(4);115 l.printNodes();116 l.add(3);117 l.printNodes();118 l.add(5);119 l.printNodes();120 }121 }