008 数组队列(lua)

2024-07-05 07:18:22

文章目录

  • 初步
    • 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
上一篇：C# Halcon目标检测算法

下一篇：qt经典界面框架-目的