public class Code_LRU {
	class LRUCache extends LinkedHashMap<Integer,Integer>{
		private int capacity;
		public LRUCache(int capacity) {
			super(capacity,0.75F,true);
			this.capacity = capacity;
		}
		
		public int get(int key) {
			return super.getOrDefault(key,-1);
		}
		public void put(int key,int value) {
			super.put(key, value);
		}
		
		// 重寫(xiě)淘汰策略
		protected boolean removeEldestEntry(Map.Entry<Integer, Integer> edlest) {
			return size()>capacity;
		}
	}
}

// 解題思路：雙向鏈表+hashmap來(lái)實(shí)現(xiàn)
	class LRUCache_2{
		// 雙向鏈表
		class DLinkedNode{
			int key;
			int value;
			DLinkedNode prev;
			DLinkedNode next;
			public DLinkedNode() {
				
			}
			public DLinkedNode(int key,int value) {
				this.key = key;
				this.value = value;
			}
		}
		
		// hashmap
		private HashMap<Integer,DLinkedNode> cache = new HashMap<>();
		// 定義私有變量
		private int size;
		private int capacity;
		private DLinkedNode head,tail;
		
		public LRUCache_2(int capacity) {
			this.size = 0;
			this.capacity = capacity;
			// 生成偽頭部和偽尾部結(jié)點(diǎn)
			head = new DLinkedNode();
			tail = new DLinkedNode();
			head.next = tail;
			tail.prev = head;
		}
		
		//獲得值
		public int get(int key) {
			DLinkedNode node = cache.get(key);
			if(node==null) {
				return -1;
			}else {
				// 如果key存在，哈希表定位 結(jié)點(diǎn)移動(dòng)到頭部
				moveToHead(node);
				return node.value;
			}
		}
		
		// 放入值的操作
		public void put(int key,int value) {
			DLinkedNode node = cache.get(key);
			// 如果key不存在
			if(node==null) {
				// 新創(chuàng)建一個(gè)結(jié)點(diǎn)
				DLinkedNode newNode = new DLinkedNode(key,value);
				// 添加
				cache.put(key,newNode);
				// 添加到頭部
				addToHead(newNode);
				++size;
				// 判斷容量
				if(size>capacity) {
					// 稱號(hào)出容量
					DLinkedNode tail = removeTail();
					// 刪除hash表中對(duì)應(yīng)的項(xiàng)
					cache.remove(tail.key);
					--size;
				}
				
			}else {
				node.value = value;
				// 移動(dòng)
				moveToHead(node);
			}
		}
		
		// 添加結(jié)點(diǎn)的操作
		private void addToHead(DLinkedNode node) {
			node.prev = head;
			node.next = head.next;
			head.next.prev = node;
			head.next = node;
		}
		
		// 刪除結(jié)點(diǎn)
		private void removeNode(DLinkedNode node) {
			node.prev.next = node.next;
			node.next.prev = node.prev;
		}
		
		// 移動(dòng)到頭結(jié)點(diǎn) 刪結(jié)點(diǎn) 填充結(jié)點(diǎn)
		private void moveToHead(DLinkedNode node) {
			removeNode(node);
			addToHead(node);
		}
		// 刪除尾部結(jié)點(diǎn)
		private DLinkedNode removeTail() {
			DLinkedNode res = tail.prev;
			removeNode(res);
			return res;
		}
	}