```lua
-- 双端队列类，支持对象缓存
local Deque = class("Deque")
function Deque:ctor()
self._head = 0 -- 队首索引
self._tail = 0 -- 队尾索引
self._size = 0 -- 当前元素数量
self._capacity = 0 -- 当前容量
self._elements = {} -- 存储元素的数组
self._cache = {} -- 对象缓存池
end
-- 获取队列大小
function Deque:size()
return self._size
end
-- 检查队列是否为空
function Deque:isEmpty()
return self._size == 0
end
-- 清空队列（元素放入缓存）
function Deque:clear()
for i = 1, self._size do
local idx = (self._head + i - 1) % self._capacity
table.insert(self._cache, self._elements[idx])
self._elements[idx] = nil
end
self._head = 0
self._tail = 0
self._size = 0
end
-- 确保容量足够
function Deque:_ensureCapacity(minCapacity)
if self._capacity >= minCapacity then
return
end
local newCapacity = math.max(minCapacity, math.floor(self._capacity * 1.5))
local newElements = {}
if self._size > 0 then
if self._head < self._tail then
-- 元素连续存储
for i = 0, self._size - 1 do
newElements[i] = self._elements[self._head + i]
end
else
-- 元素环绕存储
local firstPart = self._capacity - self._head
for i = 0, firstPart - 1 do
newElements[i] = self._elements[self._head + i]
end
for i = 0, self._tail - 1 do
newElements[firstPart + i] = self._elements[i]
end
end
end
self._elements = newElements
self._head = 0
self._tail = self._size
self._capacity = newCapacity
end
-- 从缓存获取或创建新对象
function Deque:_getOrCreateObject(value)
if #self._cache > 0 then
local obj = table.remove(self._cache)
-- 这里可以根据实际需求初始化对象
return obj
end
return value
end
-- 在队首添加元素
function Deque:addFirst(value)
self:_ensureCapacity(self._size + 1)
self._head = (self._head - 1 + self._capacity) % self._capacity
self._elements[self._head] = self:_getOrCreateObject(value)
self._size = self._size + 1
end
-- 在队尾添加元素
function Deque:addLast(value)
self:_ensureCapacity(self._size + 1)
self._elements[self._tail] = self:_getOrCreateObject(value)
self._tail = (self._tail + 1) % self._capacity
self._size = self._size + 1
end
-- 移除并返回队首元素（放入缓存）
function Deque:removeFirst()
if self:isEmpty() then
return nil
end
local result = self._elements[self._head]
table.insert(self._cache, result) -- 放入缓存
self._elements[self._head] = nil
self._head = (self._head + 1) % self._capacity
self._size = self._size - 1
if self._size == 0 then
self._head = 0
self._tail = 0
end
return result
end
-- 移除并返回队尾元素（放入缓存）
function Deque:removeLast()
if self:isEmpty() then
return nil
end
self._tail = (self._tail - 1 + self._capacity) % self._capacity
local result = self._elements[self._tail]
table.insert(self._cache, result) -- 放入缓存
self._elements[self._tail] = nil
self._size = self._size - 1
if self._size == 0 then
self._head = 0
self._tail = 0
end
return result
end
-- 获取队首元素（不移除）
function Deque:getFirst()
if self:isEmpty() then
return nil
end
return self._elements[self._head]
end
-- 获取队尾元素（不移除）
function Deque:getLast()
if self:isEmpty() then
return nil
end
local idx = (self._tail - 1 + self._capacity) % self._capacity
return self._elements[idx]
end
-- 获取指定索引的元素
function Deque:get(index)
if index < 0 or index >= self._size then
return nil
end
local idx = (self._head + index) % self._capacity
return self._elements[idx]
end
-- 设置指定索引的元素
function Deque:set(index, value)
if index < 0 or index >= self._size then
return false
end
local idx = (self._head + index) % self._capacity
self._elements[idx] = self:_getOrCreateObject(value)
return true
end
-- 获取缓存池大小
function Deque:cacheSize()
return #self._cache
end
-- 清空缓存池
function Deque:clearCache()
self._cache = {}
end
return Deque
```
使用示例：
```lua
local Deque = require("Deque")
-- 创建双端队列
local deque = Deque.new()
-- 添加元素
deque:addLast("A")
deque:addFirst("B")
deque:addLast("C")
print("队列大小:", deque:size()) -- 输出: 3
print("队首元素:", deque:getFirst()) -- 输出: B
print("队尾元素:", deque:getLast()) -- 输出: C
-- 移除元素（会自动放入缓存）
local first = deque:removeFirst() -- 移除B，放入缓存
local last = deque:removeLast() -- 移除C，放入缓存
print("当前队列大小:", deque:size()) -- 输出: 1
print("缓存池大小:", deque:cacheSize()) -- 输出: 2
-- 清空队列
deque:clear()
print("清空后队列大小:", deque:size()) -- 输出: 0
print("清空后缓存池大小:", deque:cacheSize()) -- 输出: 3
```
这个双端队列类具有以下特点：
1. 使用环形数组实现，支持高效的队首和队尾操作
2. 移除的元素会自动放入缓存池，避免频繁创建和销毁对象
3. 提供完整的双端队列操作接口
4. 支持索引访问和修改
5. 可以单独管理缓存池
6. 不依赖任何外部框架或库