74 lines
1.1 KiB
Lua
74 lines
1.1 KiB
Lua
Queue = {}
|
|
|
|
function Queue:New()
|
|
local o = {head = nil, tail = nil}
|
|
|
|
setmetatable(o, self)
|
|
self.__index = self
|
|
return o
|
|
end
|
|
|
|
function Queue:Enqueue(item)
|
|
local elem = {item = item}
|
|
if self.head == nil then
|
|
self.head = elem
|
|
self.tail = elem
|
|
return
|
|
end
|
|
|
|
elem.next = self.head
|
|
elem.next.prev = elem
|
|
self.head = elem
|
|
return
|
|
end
|
|
|
|
function Queue:Empty()
|
|
return self.tail == nil
|
|
end
|
|
|
|
function Queue:Dequeue()
|
|
if self:Empty() then
|
|
return nil
|
|
end
|
|
|
|
local newtail = self.tail.prev
|
|
local item = self.tail.item
|
|
if newtail then
|
|
newtail.next = nil
|
|
end
|
|
self.tail = newtail
|
|
return item
|
|
end
|
|
|
|
local tq1 = Queue:New()
|
|
tq1:Enqueue(5)
|
|
assert(tq1.head.item == 5)
|
|
assert(tq1:Dequeue() == 5)
|
|
|
|
-- queue that keeps a rolling tally of its arguments
|
|
AvgQueue = {}
|
|
|
|
function AvgQueue:New(n, initial)
|
|
local o = {}
|
|
|
|
o.n = n
|
|
o.queue = Queue:New()
|
|
o.avg = initial
|
|
|
|
|
|
local x = initial / n
|
|
for _ = 1,n do
|
|
o.queue:Enqueue(x)
|
|
end
|
|
|
|
setmetatable(o, self)
|
|
self.__index = self
|
|
return o
|
|
end
|
|
|
|
function AvgQueue:Push(item)
|
|
local x = item/self.n
|
|
self.avg = self.avg + x - self.queue:Dequeue()
|
|
self.queue:Enqueue(x)
|
|
return self.avg
|
|
end |