3、手写基于LinkedList的栈容器和基于LinkedHashMap的缓存容器（LRU算法）

LinkedList和ArrayList

LinkedList 底层结构：底层是双向链表 默认初始容量：无，新增节点时直接插入 扩容：无 特性：1、两端效率高 如果仅在两端操作数据，使用 LinkedList add(数据) 尾部增加数据 addFirst() 头部增加数据 removeFirst() 移除头部数据 removeLast() 移除尾部数据 push() 头部增加数据，相当于 addFirst() pop() 头部移除数据，相当于removeFirst()

基于LinkedList的栈（先进后出）

package pers.yezi.test; import java.util.LinkedList; /** * @ClassName : stack * @Description : 基于LinkedList的栈（先进后出） * @Author : Yezi * @Date: 2020-07-04 23:16 */ public class Stack<T>{ private LinkedList stack; public Stack() { this.stack = new LinkedList(); } //入栈 public void push(T t) { stack.addFirst(t); } //出栈 public T pop(){ T t = (T) stack.getFirst(); stack.removeFirst(); return t; } @Override public String toString() { return "Stack" + stack; } }

基于LinkedHashMap的缓存容器（LRU算法）

LRU算法 Least Recently Used，即最近最久未使用 LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰 LinkedHashMap LinkedHashMap分为：保持插入顺序（默认）和保持访问顺序 标志位accessOrder (值为true时，表示按照访问顺序迭代；值为false时，表示按照插入顺序迭代)

package pers.yezi.test; import java.util.LinkedHashMap; import java.util.Map; /** * @ClassName : Cache * @Description : 基于LinkedHashMap的缓存容器 * @Author : Yezi * @Date: 2020-07-04 23:48 */ public class Cache<K, V> extends LinkedHashMap<K, V> { private Integer maxsize; public Cache(Integer length) { super(length, 0.75f, true); this.maxsize = length; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return this.size() > this.maxsize; } public Integer getMaxsize() { return maxsize; } }

线程安全

package pers.yezi.test; import java.util.LinkedHashMap; import java.util.Map; /** * @ClassName : Cache * @Description : 基于LinkedHashMap的缓存容器 * @Author : Yezi * @Date: 2020-07-04 23:48 */ public class Cache<K, V>{ private Integer maxsize; private LinkedHashMap<K,V> map; public Cache(Integer length) { this.maxsize = length; map = new LinkedHashMap<K,V>(length,0.75f,true){ @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return this.size() > length; } }; } public Integer size() { return map.size(); } public synchronized V put(K key, V value) { return map.put(key, value); } public synchronized V get(Object key) { return map.get(key); } @Override public String toString() { return "Cache" + map; } public static void main(String[] args){ Cache<String,Integer> cache = new Cache<>(3); cache.put("1",1); cache.put("2",2); cache.put("3",3); System.out.println(cache);//123 cache.get("1"); System.out.println(cache);//231 cache.put("4",4); System.out.println(cache);//314 } }

参考文档 1、https://blog.csdn.net/elricboa/article/details/78847305 2、https://blog.csdn.net/justloveyou_/article/details/71713781