import java.util.*;
 
public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, V> cache;
    
    // 構(gòu)造函數(shù)，初始化容量并創(chuàng)建一個LinkedHashMap
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // LinkedHashMap 允許通過訪問順序來維護(hù)插入順序
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true);
    }
 
    // 獲取緩存中的值
    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;  // 如果緩存中沒有該項(xiàng)，返回null
        }
        return cache.get(key);  // 如果緩存中有該項(xiàng)，返回其值，并將其移動到末尾（表示最近使用）
    }
 
    // 將元素添加到緩存中
    public void put(K key, V value) {
        if (cache.size() >= capacity) {
            // 如果緩存已滿，移除最少使用的元素（即鏈表頭部的元素）
            Iterator<Map.Entry<K, V>> iterator = cache.entrySet().iterator();
            if (iterator.hasNext()) {
                iterator.next();
                iterator.remove();
            }
        }
        cache.put(key, value);  // 將新的元素放入緩存
    }
 
    // 打印緩存中的內(nèi)容
    public void printCache() {
        System.out.println(cache);
    }
 
    public static void main(String[] args) {
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);
        
        // 向緩存添加元素
        lruCache.put(1, "A");
        lruCache.put(2, "B");
        lruCache.put(3, "C");
        
        // 打印緩存內(nèi)容
        lruCache.printCache();  // 輸出: {1=A, 2=B, 3=C}
 
        // 訪問一些緩存項(xiàng)
        lruCache.get(1);  // 訪問了 1
        lruCache.put(4, "D");  // 插入新的元素，容量已滿
        
        // 打印緩存內(nèi)容
        lruCache.printCache();  // 輸出: {3=C, 1=A, 4=D}  (2 被移除，最少使用)
        
        // 繼續(xù)訪問一些緩存項(xiàng)
        lruCache.get(3);  // 訪問了 3
        lruCache.put(5, "E");  // 插入新的元素
        
        // 打印緩存內(nèi)容
        lruCache.printCache();  // 輸出: {1=A, 3=C, 5=E}  (4 被移除)
    }
}