0 Replies - 1091 Views - Last Post: 30 December 2010 - 06:56 AM

#1 KYA  Icon User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3194
  • View blog
  • Posts: 19,220
  • Joined: 14-September 07

[LUA]Queue ADT

Posted 30 December 2010 - 06:56 AM

Description: Implement when you need a FIFO data structure in your Lua programs. Implementation of a FIFO queue in Lua. Uses an internal table that exposes "queue" functionality to the user.
--[[
12-30-10
KYA
Queue ADT

Keeps the Lua convention of indexes starting
at 1 rather then zero


In our internal table, we keep the number of elements
stored at "curIndex".
]]--


Queue = {}
function Queue:new()
	local storage = {}
	storage["curIndex"] = 1
	setmetatable(storage, {__index = Queue})
	return storage
end

function Queue:enqueue(val)
	curIndex = self["curIndex"]
	self[curIndex] = val
	curIndex = curIndex + 1
	self["curIndex"] = curIndex
	return
end

function Queue:dequeue()
	--pop and rotate "up"
	i = 1
	if #self == 0 then
		print("Queue is empty!")
		return
	end
	--print("table size: "..#self)
	temp = self[1]
	--print("temp val: "..temp)

	--[[
	iterate from the top, swapping elements
	set the last known position to nil, erasing it
	]]--
	while i < #self do
		self[i+1], self[i] = self[i], self[i+1]
		i = i + 1
	end
	self[#self] = nil
	curIndex = self["curIndex"] - 1
	self["curIndex"] = curIndex
	return temp
end

--useful for seeing table contents when
--unexpected behavior occurs
function Queue:debugPrint()
	for i, v in ipairs(self) do
	print(i.." "..v)
	end
end

function Queue:hasMoreElements()
	if #self == 0 then
		return false
	else
		return true
	end
end

--let's look at, but not remove
function Queue:peek()
	return self[1]
end


test = Queue:new()
test:enqueue(5)
test:enqueue("fifty")
test:enqueue("fourty")
test:enqueue(46)
test:enqueue(69)
test:enqueue('a')

--returns 5
print(test:peek())

--pop them all off, FIFO!
while test:hasMoreElements() do
	--[[
		5
		fifty
		fourty
		46
		69
		a
	]]--
	print(test:dequeue())
end

--returns nil [i.e. queue is empty]
print(test:peek())

--if you wanted to do it piecemeal
--[[
print(test:dequeue())
print(test:dequeue())
print(test:dequeue())
print(test:dequeue())
print(test:dequeue())]]--

-- illustrates that our Queue could be
-- traversed like a traditional array
--test:debugPrint()




Is This A Good Question/Topic? 0
  • +

Page 1 of 1