0 Replies - 1111 Views - Last Post: 30 December 2010 - 08:43 AM

#1 KYA  Icon User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3199
  • View blog
  • Posts: 19,230
  • Joined: 14-September 07

[LUA]Stack ADT

Posted 30 December 2010 - 08:43 AM

Description: Implement when you need a stack in your program. Lua implementation of the LIFO data structure. Same as other ADTs in Lua, utilizes a "hidden" table that acts as an array based implementation.
--[[
12-30-10
KYA
Stack ADT

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

Lua implementation of the LIFO data structure
]]--

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

function Stack:push(value)
	index = self["stackTop"]
	--print(value.." placed at index: "..index)
	self[index] = value
	self["stackTop"] = index + 1
end

function Stack:pop()
	--"StackTop" represents next free index
	--actual top item is next "below"
	index = self["stackTop"] - 1
	if index == 0 then
		print("Stack is empty!")
		return
	end
	temp = self[index]
	self[index]= nil
	self["stackTop"] = index --reset the "top"
	return temp
end


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

--make sure the next value isn't nil
--i.e. the list is empty
function Stack:peek()
	index = self["stackTop"]-1
	return self[index]
end

---------------------------------------------------------
-- SAMPLE IMPLEMENTATION
---------------------------------------------------------
test = Stack:new()
test:push(5)
test:push(6)
test:push(7)

--see the ipairs here
--test:debugPrint()

while test:peek() do --alternatively add a ~= nil for additional clarity
	print(test:pop())
end

--this debug print has no output, indicating the items have been
--actually been removed/freed from the table
--test:debugPrint()



Is This A Good Question/Topic? 0
  • +

Page 1 of 1