前言：

LRU就是Least Recently Used，即最近最少使用，是一种常用的页面置换算法，将最近长时间未使用的页面淘汰，其实也很简单，就是要将不受欢迎的页面及时淘汰，不让它占着茅坑不拉shit，浪费资源。
其核心就是利用栈，进行操作，其中主要有两项操作，get和put

  1. get

get时，若栈中有值则将该值的key提到栈顶，没有时则返回null

  1. put
  • 栈未满时，若栈中有要put的key，则更新此key对应的value，并将该键值提到栈顶，若无要put的key，直接入栈
  • 栈满时，若栈中有要put的key，则更新此key对应的value，并将该键值提到栈顶；若栈中没有put的key 时，去掉栈底元素，将put的值入到栈顶

JS:

  1. var LRUCache = function(capacity) {
  2.   this.capacity = capacity;
  3.   this.cache = [];
  4. }
  6. LRUCache.prototype.get = function(key) {
  7.   for (let i = 0; i < this.cache.length; i++) {
  8.     if (this.cache[i].key === key) {
  9.       let el = null;
  10.       el = this.cache.splice(i, 1);
  11.       this.cache.push(el[0]);
  13.       return el[0].val;
  14.     }
  15.   }
  17.   return -1;
  18. }
  20. LRUCache.prototype.put = function(key, value) {
  21.   var ca = {
  22.     'key': key,
  23.     'val': value
  24.   };
  26.   // 当缓存中存在键值时，更新键值，并将键值放在栈顶
  27.   for (let i = 0; i < this.cache.length; i++) {
  28.     if (this.cache[i].key === key) {
  29.       this.cache[i].val = value;
  30.       let el = this.cache.splice(i, 1);
  31.       this.cache.push(el[0]);
  33.       return null;
  34.     }
  35.   }
  37.   // 此时缓存中没有键值
  38.   if (this.cache.length < this.capacity) {
  39.     // 当缓存中未满时，直接插入
  40.     this.cache.push(ca)
  41.   } else {
  42.     // 当缓存满时，去掉栈底元素，将新元素放在栈顶
  43.     this.cache.shift();
  44.     this.cache.push(ca);
  45.   }
  46. }