lua lru算法

-- 定义一个双向链表节点
local Node = {}
Node.new = function(key, value)
    local node = {}
    node.key = key
    node.value = value
    node.prev = nil
    node.next = nil
    return node
end

-- 定义 LRU 缓存类
local LRUCache = {}
LRUCache.new = function(maxSize)
    local cache = {}
    cache.capacity = maxSize or 10 -- 缓存容量，默认为 10
    cache.size = 0 -- 当前缓存项数
    cache.head = nil -- 缓存头部节点
    cache.tail = nil -- 缓存尾部节点
	cache.map = {} -- 缓存映射表（用于快速查找）

    -- 获取缓存中指定 key 的值
    function cache:get(key)
        local node = self.map[key]
        if node then
            self:moveToHead(node) -- 如果 key 存在，将其移到链表头部
            return node.value
        end
        return nil
    end

    -- 向缓存中插入新的 key-value 对
    function cache:put(key, value)
        local node = self.map[key]
        if node then
            node.value = value -- 如果 key 存在，更新其 value，并将其移到链表头部
            self:moveToHead(node) 
        else
            node = Node.new(key, value) -- 如果 key 不存在，创建一个新的节点
            self.map[key] = node
            if self.size == self.capacity then
                self:removeTail() -- 如果缓存已满，移除尾部节点（最近最少使用的）
            else
                self.size = self.size + 1
            end
            self:addToHead(node) -- 将新节点添加到链表头部（最近使用的）
        end
    end

    -- 从缓存中移除指定 key 的节点
    function cache:remove(key)
        local node = self.map[key]
        if node then
            if node == self.head then
                self.head = node.next -- 如果要移除的节点是头部节点，将头部指针移动到下一个节点
            elseif node == self.tail then
                self.tail = node.prev -- 如果要移除的节点是尾部节点，将尾部指针移动到上一个节点
            else
                node.prev.next = node.next -- 如果要移除的节点在中间，将其前后节点连接起来
                node.next.prev = node.prev 
            end
            self.size = self.size - 1
            self.map[key] = nil
        end
    end

    -- 将节点移到链表头部
    function cache:moveToHead(node)
        if node == self.head then return end
        if node == self.tail then
            self.tail = node.prev
            node.prev = nil
        else
            node.prev.next = node.next
            node.next.prev = node.prev
        end
        node.next = self.head
        node.prev = nil
        self.head = node
        if self.tail == nil then
            self.tail = self.head
        end
    end

    -- 将节点添加到链表头部
    function cache:addToHead(node)
        node.next = self.head
        node.prev = nil
        if self.head then
            self.head.prev = node
        else
            self.tail = node
        end
        self.head = node
        if self.tail == nil then
            self.tail = self.head
        end
    end

    -- 移除尾部节点
    function cache:removeTail()
        local tail = self.tail
        if tail then
            self.tail = tail.prev
            if self.tail then
                self.tail.next = nil
            else
                self.head = nil
            end
            self.size = self.size - 1
            self.map[tail.key] = nil
        end
    end

    return cache
end

local lruCache = LRUCache.new(3)

-- 添加元素
lruCache:put(1, "value1")
lruCache:put(2, "value2")
lruCache:put(3, "value3")

-- 获取元素
print(lruCache:get(2))

-- 添加一个已存在的元素
lruCache:put(2, "newValue")

-- 获取元素
print(lruCache:get(2))

-- 添加一个新元素，超过容量限制
lruCache:put(4, "value4")

-- 获取元素
print(lruCache:get(1))

在上述代码中，我们定义了一个双向链表节点Node和一个 LRU 缓存类LRUCache。LRUCache类有capacity（容量）、size（当前项数）、head（头部节点）、tail（尾部节点）和map（用于快速查找）等属性，以及get、put、remove、moveToHead和addToHead等方法。get方法用于获取缓存中指定 key 的值，如果 key 存在，将其移到链表头部并返回 value；如果 key 不存在，则返回 nil。put方法用于向缓存中插入新的 key-value 对，如果 key 存在，更新其 value，并将其移到链表头部；如果 key 不存在，创建一个新的节点，并将其添加到链表头部。如果缓存已满，put方法还会移除尾部节点。remove方法用于从缓存中移除指定 key 的节点。moveToHead方法用于将节点移到链表头部。addToHead方法用于将节点添加到链表头部。removeTail方法用于移除尾部节点。

在测试代码中，我们首先创建一个容量为 3 的 LRU 缓存，然后依次添加三个元素，分别是1、2和3。接着，我们通过get方法获取2的值，输出其 value。然后，我们通过put方法更新2的值，并再次通过get方法获取2的值，输出其最新的 value。最后，我们通过put方法添加一个新的元素4，此时缓存已满，会移除尾部节点1，然后通过get方法获取1的值，输出为 nil。