第一模块：5-7LRULRU缓存置换算法
讲师：咚咚呛
第二模块：内容
借用MAP实现一个缓存,避免搜索链表
添加时: 1. 判断是否在缓存中
如果在缓存中: 取出缓存,更新值, 删除链表, 添加到头部
如果不存在缓存中: 判断是否容量满了.
如果满了:则删除尾部元素, 添加到头部
如果没有满: 则添加到头部.
from computer_principle.DoubleLinkedList import DoubleLinkedList, Node


class LRUCache(object):
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.size = 0
        self.list = DoubleLinkedList(self.capacity)
    
    def get(self, key):
        if key in sefl.map:
            node = sefl.map[key]
            self.list.remove(node)
            self.list.append_front(node)
            return node.value
        else:
            return -1
            
    def put(self, key, value):
        if key in self.map:  # 若key在map中，则更新value
            node = self.map.get(key)
            self.list.remove(node)
            node.value = value
            self.list.append_front(node)
        else:
            node = Node(key, value)
            if self.list.size >= self.list.capacity:  # 缓存已经满了
                old_node = self.list.remove()
                self.map.pop(old_node.key)

            self.list.append_front(node)
            self.map[key] = node
    
    def print(self):
        self.list.print()