LRU（Least Recently Used）置换算法

 1 package test1;
 2 
 3 import java.util.Stack;
 4 
 5 public class LeastRecentPage
 6 {
 7   private static Stack<Integer> cache;
 8 
 9     // METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
10     public static int lruCountMiss(int max_cache_size, int[] pages) {
11         
12         int missCount = 0;
13         
14         if (cache == null) {
15             cache = new Stack<Integer>();
16         }
17 
18         int length = pages.length;
19         for (int j = 0;j < length; j++){
20             if(cache.contains(pages[j])){
21                 cache.removeElement(pages[j]);
22                 cache.push(pages[j]);
23             }else {
24                 if(cache.size() == max_cache_size){
25                     cache.remove(0);
26                     cache.push(pages[j]);
27                     missCount++;
28                 }else if(cache.size() < max_cache_size){
29                     cache.push(pages[j]);
30                     missCount++;
31                 }
32             }
33         }
34     
35         return missCount;
36     }
37   // METHOD SIGNATURE ENDS
38     
39     public static void main(String[] args) {
40         int count = lruCountMiss(2,new int[]{2,3,1,3,2,1,4,3,2});
41         System.out.println(count);
42     }
43 }