第一模块：5-6FIFO实现
讲师姓名：咚咚呛
第二模块：课程内容（内容概述）from computer_principle.DoubleLinkedList import DoubleLinkedList


class FIFOCache(object):
    """先进先出缓存置换算法"""
    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.map = {}  # 保存key与val的映射关系
        self.list = DoubleLinkedList(self.capacity)
        
    def get(self, key):
        """获得cache中key的值"""
        if key not in self.list:
            return -1
        else:
            node = self.map.get(key)
            return node.val
    
    def put(self, key, value):
        """向cache中添加字块"""
        if self.capacity == 0:  # 若缓存容量为0，则直接返回
            return
        if key in self.map:  # 若该关键字已经存在，则替换其value
            node = self.map.get(key)
            self.list.remove(node)
            node.val = value
            self.list.append(node)
        else:
            if self.size == self.capacity:  # 判断缓存是否溢出，若溢出，则删除头部的字块
                node = self.list.pop()
                def sefl.map[node.key]
                self.size -= 1
            node = Node(key, value)  # 将新字块添加到尾部
            self.list.append(node)
            self.map[key] = node
            self.size += 1

    def print(self):
        self.list.print()