文章目录
- 初步
- array.lua
- arrayqueue.lua
- 修改(封装)
- array.lua
- arrayqueue.lua
- 测试（直接在 arrayqueue.lua 文件的末尾添加）
- 修改(本身就是动态扩容)
- array.lua
- arrayqueue.lua
- 循环队列
- LoopQueue.lua
初步
array.lua
Java是一种静态类型、面向对象的编程语言，而Lua是一种动态类型、脚本语言。在Lua中，没有类（class）的概念，但有表（table）来模拟对象的行为和存储数据。
-- array.lua
local Array = {}
Array.__index = Array
function Array.new(capacity)
capacity = capacity or 10
local self = setmetatable({
data = {},
size = 0,
capacity = capacity
}, Array)
return self
end
function Array:addLast(e)
if #self.data >= self.capacity then
self:resize(2 * self.capacity)
end
self.data[self.size + 1] = e
self.size = self.size + 1
end
function Array:removeFirst()
if self:isEmpty() then
error("Attempt to remove from an empty array")
end
local first = self.data[1]
for i = 1, self.size - 1 do
self.data[i] = self.data[i + 1]
end
self.data[self.size] = nil
self.size = self.size - 1
if self.size == self.capacity / 4 and self.capacity / 2 ~= 0 then
self:resize(self.capacity / 2)
end
return first
end
function Array:getFirst()
if self:isEmpty() then
error("Attempt to get first element from an empty array")
end
return self.data[1]
end
function Array:getSize()
return self.size
end
function Array:isEmpty()
return self.size == 0
end
function Array:resize(newCapacity)
local newData = {}
for i = 1, self.size do
newData[i] = self.data[i]
end
self.data = newData
self.capacity = newCapacity
end
-- 可能还需要添加其他方法，如addFirst, get等
return Array
arrayqueue.lua
接下来，我们使用array.lua模块来定义ArrayQueue。
-- arrayqueue.lua
local Array = require("array") -- 假设array.lua在同一目录下
ArrayQueue = {}
ArrayQueue.__index = ArrayQueue
function ArrayQueue.new(capacity)
local self = setmetatable({
array = Array.new(capacity)
}, ArrayQueue)
return self
end
function ArrayQueue:enqueue(e)
self.array:addLast(e)
end
function ArrayQueue:dequeue()
return self.array:removeFirst()
end
function ArrayQueue:getFront()
return self.array:getFirst()
end
function ArrayQueue:isEmpty()
return self.array:isEmpty()
end
function ArrayQueue:getSize()
return self.array:getSize()
end
function ArrayQueue:toString()
local res = "Queue: front ["
for i = 1, self.array:getSize() do
res = res .. tostring(self.array.data[i])
if i ~= self.array:getSize() then
res = res .. ", "
end
end
res = res .. "] tail"
return res
end
-- 测试代码
local queue = ArrayQueue.new()
for i = 1, 9 do
queue:enqueue(i)
print(queue:toString())
if i % 3 == 2 then
queue:dequeue()
print(queue:toString())
end
end
Lua脚本中的Array和ArrayQueue都使用表（table）和元表（metatable）来模拟对象和方法。
Lua中数组索引默认从1开始，而Java从0开始。
Lua没有静态类型检查，所以在运行时需要更仔细地处理错误和异常情况。
Lua脚本中的模块（如array.lua）用于封装和重用代码。
Lua的require函数用于加载和执行Lua文件。这里假设array.lua和arrayqueue.lua在同一目录下。
在 ArrayQueue:toString() 方法中直接访问 self.array.data 并不是最佳实践，因为这破坏了封装性。Array 类应该负责其内部数据的所有操作，包括如何遍历和展示这些数据。
修改(封装)
array.lua
local Array = {}
Array.__index = Array
function Array.new(capacity)
capacity = capacity or 10
local self = setmetatable({
data = {},
size = 0,
capacity = capacity
}, Array)
return self
end
function Array:addLast(e)
if self.size >= self.capacity then
self:resize(2 * self.capacity)
end
self.data[self.size + 1] = e
self.size = self.size + 1
end
function Array:removeFirst()
if self:isEmpty() then
error("Attempt to remove from an empty array")
end
local first = self.data[1]
for i = 1, self.size - 1 do
self.data[i] = self.data[i + 1]
end
self.data[self.size] = nil
self.size = self.size - 1
if self.size == self.capacity / 4 and self.capacity / 2 ~= 0 then
self:resize(self.capacity / 2)
end
return first
end
function Array:getFirst()
if self:isEmpty() then
error("Attempt to get first element from an empty array")
end
return self.data[1]
end
function Array:getSize()
return self.size
end
function Array:isEmpty()
return self.size == 0
end
function Array:resize(newCapacity)
local newData = {}
for i = 1, self.size do
newData[i] = self.data[i]
end
self.data = newData
self.capacity = newCapacity
end
function Array:toString()
local res = "Array: ["
for i = 1, self.size do
res = res .. tostring(self.data[i])
if i ~= self.size then
res = res .. ", "
end
end
res = res .. "]"
return res
end
return Array
arrayqueue.lua
local Array = require("array")
ArrayQueue = {}
ArrayQueue.__index = ArrayQueue
function ArrayQueue.new(capacity)
local self = setmetatable({
array = Array.new(capacity)
}, ArrayQueue)
return self
end
function ArrayQueue:enqueue(e)
self.array:addLast(e)
end
function ArrayQueue:dequeue()
return self.array:removeFirst()
end
function ArrayQueue:getFront()
return self.array:getFirst()
end
function ArrayQueue:isEmpty()
return self.array:isEmpty()
end
function ArrayQueue:getSize()
return self.array:getSize()
end
function ArrayQueue:toString()
local res = "Queue: front [" .. self.array:toString() .. "] tail"
return res
end
return ArrayQueue
测试（直接在 arrayqueue.lua 文件的末尾添加）
-- 测试代码
local queue = ArrayQueue.new()
for i = 1, 9 do -- 注意这里从 1 开始迭代
queue:enqueue(i)
print(queue:toString())
if i % 3 == 0 then -- 注意条件也做了相应调整
queue:dequeue()
print(queue:toString())
end
end
修改(本身就是动态扩容)
在Lua中，数组（实际上是表）本身就是动态扩容的，不需要像Java那样手动管理容量和进行resize操作。
可以省略与容量管理相关的所有方法。
注意，Lua脚本中的“Array”将不再需要容量管理，而ArrayQueue将直接使用这个简化的“Array”。
array.lua
-- array.lua
local Array = {}
Array.__index = Array
function Array.new()
local self = setmetatable({
data = {}
}, Array)
return self
end
function Array:addLast(e)
table.insert(self.data, e)
end
function Array:removeFirst()
if #self.data == 0 then
error("Attempt to remove from an empty array")
end
return table.remove(self.data, 1)
end
function Array:getFirst()
if #self.data == 0 then
error("Attempt to get first element from an empty array")
end
return self.data[1]
end
function Array:getSize()
return #self.data
end
function Array:isEmpty()
return #self.data == 0
end
function Array:toString()
local res = "Array: ["
for i, v in ipairs(self.data) do
res = res .. tostring(v)
if i ~= #self.data then
res = res .. ", "
end
end
res = res .. "]"
return res
end
return Array
arrayqueue.lua
-- arrayqueue.lua
local Array = require("array")
ArrayQueue = {}
ArrayQueue.__index = ArrayQueue
function ArrayQueue.new()
local self = setmetatable({
array = Array.new()
}, ArrayQueue)
return self
end
function ArrayQueue:enqueue(e)
self.array:addLast(e)
end
function ArrayQueue:dequeue()
return self.array:removeFirst()
end
function ArrayQueue:getFront()
return self.array:getFirst()
end
function ArrayQueue:isEmpty()
return self.array:isEmpty()
end
function ArrayQueue:getSize()
return self.array:getSize()
end
function ArrayQueue:toString()
local res = "Queue: front [" .. self.array:toString() .. "] tail"
return res
end
-- 测试代码
local queue = ArrayQueue.new()
for i = 1, 10 do
queue:enqueue(i)
print(queue:toString())
if i % 3 == 0 then
queue:dequeue()
print(queue:toString())
end
end
在这个Lua脚本中，Array类现在只负责管理一个Lua表，并使用Lua内建的table.insert和table.remove方法来添加和删除元素。ArrayQueue类则使用这个简化的Array类来模拟队列的行为。测试代码部分展示了如何使用这个队列，包括入队、出队和打印队列状态。
dequeue() 方法的复杂度实际上是 O(n)，尽管它看起来像是直接操作数组（在Lua中是表）的第一个元素。然而，这里的关键是Lua表并不总是以数组的形式存储数据，特别是在涉及到删除表的前端元素时。
在Lua中，表是通过哈希表实现的，这意味着它们可以非常高效地通过键来访问元素（对于整数键，Lua内部可能会使用一种类似于数组的结构来优化访问，但这取决于Lua引擎的具体实现和表的使用方式）。然而，当从表的前端删除元素时（即删除键为1的元素），Lua表不会自动地“压缩”或重新索引剩余的元素以填补被删除元素留下的空白。相反，它会留下这个空白，并简单地更新表的大小（即#table操作的结果）。
因此，从性能的角度来看，虽然删除操作本身可能是O(1)的（即直接设置table[1] = nil并将表的内部大小标记减1），但如果你之后想要迭代这个表并期望它按照索引顺序来迭代（比如使用ipairs），那么实际上你会遇到一个“空洞”，因为ipairs会从1开始迭代，直到遇到第一个不是整数的键或nil值为止。在这种情况下，虽然删除操作本身是快速的，但表现在逻辑上不再是一个紧凑的数组，这可能会影响后续操作的性能，特别是那些依赖于索引连续性的操作。
然而，如果你只关心删除操作的直接成本，并且不担心表内部结构的变化对后续操作的影响，那么可以说删除操作（在这个上下文中是dequeue()方法）是O(1)的。但在实际应用中，通常需要考虑这些后续影响，因此从更广泛的角度来看，将其视为O(n)（其中n是表中剩余元素的数量，考虑到后续可能需要重新组织或处理表）可能更为准确。
但请注意，这里的“O(n)”并不是指删除操作本身需要遍历整个表；而是指删除操作可能间接导致后续操作（如迭代）需要更多的工作来“跳过”表中的空洞。如果表的使用方式不涉及对空洞的敏感性（比如总是通过键直接访问元素），那么这种影响可能就不那么重要了。
另外，值得注意的是，Lua 5.3及更高版本引入了对表压缩的支持（通过table.pack和table.unpack函数，尽管它们与ipairs和直接操作表的方式不完全相同），但标准的表操作（如添加和删除元素）并不自动压缩表。如果你需要一个紧凑的数组结构，你可能需要自己实现这种压缩逻辑。
在Lua中，当你从表中删除第一个元素（即设置table[1] = nil），表并不会自动地重新组织，使得后面的元素都往前挪动来填补这个空白。Lua的表是基于哈希表的实现，它并不保证元素的物理顺序与插入顺序一致，除非这些元素都是使用连续的整数键插入的，并且没有使用过非整数键或删除了中间的元素。
即使所有的元素都是用连续的整数键插入的，Lua也不会在删除第一个元素后自动调整后续元素的键。相反，它会留下一个“空洞”，即键1对应的值为nil，而表的长度（通过#table获得的）会相应减少，但表的实际内存占用可能并不会立即减少，因为Lua的垃圾收集器会负责回收不再使用的内存空间。
因此，从这个角度来看，删除第一个元素的操作本身是O(1)的，因为它只需要设置一个键的值为nil并更新表的长度（尽管这个长度更新对于Lua用户来说可能是不可见的，因为它通常是通过#table这样的操作间接感知的）。但是，如果你之后需要以某种方式迭代这个表，并且你希望忽略掉这些空洞，那么你可能需要使用一种能够跳过nil值的迭代方法，比如编写自己的迭代函数，或者使用pairs而不是ipairs（但请注意pairs的迭代顺序是不确定的）。
然而，如果你确实需要一个在删除元素后能够自动重新组织，使得所有剩余元素都保持连续索引的数组结构，那么Lua标准库并不直接提供这样的功能。你需要自己实现这样的逻辑，比如在删除元素后遍历表，将所有后续元素都向前移动一位。这样的操作将是O(n)的，其中n是表中剩余元素的数量。
总结来说，Lua表在删除第一个元素时不会自动重新组织，删除操作本身是O(1)的，但后续操作（如迭代）可能会受到表中空洞的影响，而如果你需要保持元素的连续索引，则可能需要手动实现O(n)的重新组织逻辑。
循环队列
我们需要注意Lua与Java在数组（或表）处理、类型系统和内存管理方面的差异。Lua表是动态数组和哈希表的混合体，它们会自动扩容，但在这里我们将模拟Java中的固定容量数组行为，并通过手动调整front和tail指针来实现循环队列。
LoopQueue.lua
-- LoopQueue.lua
local LoopQueue = {}
LoopQueue.__index = LoopQueue
function LoopQueue.new(capacity)
capacity = capacity or 10
local self = setmetatable({
data = {},
front = 1,
tail = 1,
size = 0,
capacity = capacity
}, LoopQueue)
-- 初始化data表，预留capacity+1个空间（Lua索引从1开始）
for _ = 1, capacity + 1 do
table.insert(self.data, nil)
end
return self
end
function LoopQueue:isEmpty()
return self.size == 0
end
function LoopQueue:getSize()
return self.size
end
function LoopQueue:getCapacity()
return self.capacity
end
function LoopQueue:enqueue(e)
if (self.tail + 1) % (self.capacity + 1) == self.front then
error("Queue is full")
end
self.data[self.tail] = e
self.tail = (self.tail + 1) % (self.capacity + 1)
self.size = self.size + 1
end
function LoopQueue:dequeue()
if self:isEmpty() then
error("Cannot dequeue from an empty queue.")
end
local ret = self.data[self.front]
self.data[self.front] = nil -- Lua中的nil相当于Java中的null，用于标记空位
self.front = (self.front + 1) % (self.capacity + 1)
self.size = self.size - 1
return ret
end
function LoopQueue:getFront()
if self:isEmpty() then
error("Queue is empty.")
end
return self.data[self.front]
end
function LoopQueue:toString()
local res = "Queue: size = " .. self.size .. ", capacity = " .. self.capacity .. "\n"
res = res .. "front ["
local i = self.front
while i ~= self.tail do
res = res .. tostring(self.data[i])
i = (i + 1) % (self.capacity + 1)
if i ~= self.tail then
res = res .. ", "
end
end
res = res .. "] tail"
return res
end
-- 测试代码
local queue = LoopQueue.new()
for i = 0, 9 do -- Lua中的for循环与Java类似(不过Lua索引从1开始）
queue:enqueue(i + 1) -- 我们需要显式地加1来匹配索引
print(queue:toString())
if (i + 1) % 3 == 0 then -- 同样地，我们需要对i+1取模，因为i是从0开始的
queue:dequeue()
print(queue:toString())
end
end
Lua中的表索引默认从1开始，但在这个实现中，我们仍然模拟了Java中从0开始的“逻辑索引”（尽管在enqueue和dequeue操作中我们使用了从1开始的物理索引）。
Lua没有像Java那样的泛型类型，所以我们使用Lua的动态类型系统。
Lua表是动态扩容的，但在这个实现中，我们手动管理了容量（通过capacity字段），并在达到容量限制时抛出了错误。在Lua中，通常不需要这样做，因为表的自动扩容特性可以处理大多数情况。
Lua中的错误处理是通过error函数实现的，它会中断当前的执行流，并抛出一个错误。这与Java中的异常处理不同。
