以下是基于Lua原生方法实现的双端队列类，包含缓存功能：
```lua
local Deque = {}
Deque.__index = Deque
-- 构造函数
function Deque.new()
local obj = {
_head = 0, -- 队列头部索引
_tail = 1, -- 队列尾部索引
_size = 0, -- 当前队列大小
_items = {}, -- 队列存储表
_pool = {} -- 对象池缓存
}
return setmetatable(obj, Deque)
end
-- 从对象池获取对象
function Deque:getFromPool(itemKey)
if self._pool[itemKey] and #self._pool[itemKey] > 0 then
return table.remove(self._pool[itemKey])
end
return nil
end
-- 添加对象到对象池
function Deque:addToPool(itemKey, item)
if not self._pool[itemKey] then
self._pool[itemKey] = {}
end
table.insert(self._pool[itemKey], item)
end
-- 从头部入队（支持缓存）
function Deque:pushFront(item, itemKey)
self._head = self._head - 1
self._items[self._head] = item
self._size = self._size + 1
return item
end
-- 从头部出队（放入缓存）
function Deque:popFront(itemKey)
if self._size == 0 then return nil end
local item = self._items[self._head]
self._items[self._head] = nil
self._head = self._head + 1
self._size = self._size - 1
if itemKey and item then
self:addToPool(itemKey, item)
end
return item
end
-- 从尾部入队（支持缓存）
function Deque:pushBack(item, itemKey)
self._tail = self._tail + 1
self._items[self._tail - 1] = item
self._size = self._size + 1
return item
end
-- 从尾部出队（放入缓存）
function Deque:popBack(itemKey)
if self._size == 0 then return nil end
self._tail = self._tail - 1
local item = self._items[self._tail]
self._items[self._tail] = nil
self._size = self._size - 1
if itemKey and item then
self:addToPool(itemKey, item)
end
return item
end
-- 获取队列大小
function Deque:size()
return self._size
end
-- 判断队列是否为空
function Deque:isEmpty()
return self._size == 0
end
-- 清空队列（可选择是否放入缓存）
function Deque:clear(itemKey)
if itemKey then
for i = self._head, self._tail - 1 do
if self._items[i] then
self:addToPool(itemKey, self._items[i])
end
end
end
self._head = 0
self._tail = 1
self._size = 0
self._items = {}
end
-- 移除指定索引的元素到缓存
function Deque:removeToPoolAt(index, itemKey)
if index < 0 or index >= self._size then return end
local actualIndex = self._head + index
local item = self._items[actualIndex]
-- 移动后续元素
for i = actualIndex, self._tail - 2 do
self._items[i] = self._items[i + 1]
end
self._items[self._tail - 1] = nil
self._tail = self._tail - 1
self._size = self._size - 1
if itemKey and item then
self:addToPool(itemKey, item)
end
return item
end
-- 移除指定元素到缓存
function Deque:removeToPool(item, itemKey)
for i = self._head, self._tail - 1 do
if self._items[i] == item then
-- 移动后续元素
for j = i, self._tail - 2 do
self._items[j] = self._items[j + 1]
end
self._items[self._tail - 1] = nil
self._tail = self._tail - 1
self._size = self._size - 1
if itemKey then
self:addToPool(itemKey, item)
end
return true
end
end
return false
end
-- 移除范围元素到缓存
function Deque:removeRangeToPool(beginIndex, endIndex, itemKey)
if beginIndex < 0 then beginIndex = 0 end
if endIndex < 0 or endIndex >= self._size then endIndex = self._size - 1 end
if beginIndex > endIndex then return end
local start = self._head + beginIndex
local finish = self._head + endIndex
-- 将移除的元素放入缓存
if itemKey then
for i = start, finish do
if self._items[i] then
self:addToPool(itemKey, self._items[i])
end
end
end
-- 计算需要移动的元素数量
local moveCount = (self._tail - 1) - finish - 1
if moveCount > 0 then
for i = 0, moveCount - 1 do
self._items[start + i] = self._items[finish + 1 + i]
end
end
-- 清理尾部空间
local newTail = start + moveCount
for i = newTail, self._tail - 1 do
self._items[i] = nil
end
self._tail = newTail
self._size = self._size - (endIndex - beginIndex + 1)
end
return Deque
```
**使用示例：**
```lua
local Deque = require("Deque")
-- 创建队列
local deque = Deque.new()
-- 从对象池获取或创建新对象
local function getOrCreateItem(key, defaultData)
local item = deque:getFromPool(key)
if not item then
item = defaultData or {}
end
return item
end
-- 使用队列
deque:pushBack(getOrCreateItem("player", {name = "玩家1"}), "player")
deque:pushBack(getOrCreateItem("player", {name = "玩家2"}), "player")
-- 移除元素到缓存
local item = deque:popFront("player") -- 移除到"player"缓存池
-- 再次使用时可从缓存获取
local newItem = getOrCreateItem("player", {name = "新玩家"})
deque:pushBack(newItem, "player")
-- 批量移除到缓存
deque:removeRangeToPool(0, 2, "player") -- 移除索引0-2的元素到缓存
```
这个双端队列类提供了：
1. 标准的双端队列操作（pushFront/popFront/pushBack/popBack）
2. 对象池缓存机制，移除的元素可以存入缓存重复使用
3. 支持按索引、按元素、按范围移除到缓存
4. 完全基于Lua原生table实现，不依赖外部框架