简 洁 冬冬

简 洁 冬冬

关注
发信
关注(28)粉丝(399)

008 数组队列(lua)

初步

array.lua


-- 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

修改(封装)

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脚本中的“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

循环队列

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
07-05 01:54
Powered by LMLPHP ©2024 简 洁 冬冬 0.004836