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