Quick Links: Download Gideros Studio | Gideros Documentation | Gideros Development Center | Gideros community chat
How to implement a simple last in first out (LIFO) stack in Lua - Gideros Forum

How to implement a simple last in first out (LIFO) stack in Lua

simwhisimwhi Member
edited September 2016 in Step by step tutorials
Hi all,

I've been researching and tinkering around with data structures and algorithms on and off for some time so I thought I would write a little tutorial on creating a simple stack. Let me know if you think of any suggestions to improve it. I hope you enjoy it.
--[[
  stack.lua
 
  This Lua class implementation of a stack data structure was based on Mário Kašuba's function 
  in the book, Lua Game Development Cookbook (2015)
 
]]
 
Stack = Core.class()
 
function Stack:init(list)
 
  if not list then
    -- create an empty stack
    self.stack = {}
  else
    -- initialise the stack
    self.stack = list
  end
end
 
function Stack:push(item)
  -- put an item on the stack
  self.stack[#self.stack+1] = item
end
 
function Stack:pop()
  -- make sure there's something to pop off the stack
  if #self.stack > 0 then
    -- remove item (pop) from stack and return item
    return table.remove(self.stack, #self.stack)
  end
end
 
function Stack:iterator()
  -- wrap the pop method in a function
  return function()
    -- call pop to iterate through all items on a stack
    return self:pop()
  end
end
Here is how to use it:
  -- main.lua
 
  local stack = Stack.new({"one","two", "three", "four", "five"})
 
  stack:push("six")
  stack:push("seven")
  print ("Remove an item from the stack: "..stack:pop())
 
  for item in stack:iterator() do
    print("Item: ".. item)
  end
I think this implementation is self explanatory, but if you need any further information I can provide a step by step guide.
+1 -1 (+5 / -0 ) Share on Facebook

Comments

  • n1cken1cke Maintainer
    Accepted Answer
    It is not effective implementation because for each new Stack instance it creates it's own functions instead of using Stack metatable. For example:
      function self:push(item)
        -- put an item on the stack
        self.stack[#self.stack+1] = item
      end
    is syntax sugar for `self.push = function(self, item) ...`.
    You can check it with something like `print(stack1.pop == stack2.pop)`.
    You need to put all Stack functions outside `function Stack:init(list)`, for example:
      function Stack:push(item)
        -- put an item on the stack
        self.stack[#self.stack+1] = item
      end
  • just a simple table t and
    table.insert for push
    and
    x=t[#t] t[#t]=nil for pop
    wouldn't be good enough?
  • n1cken1cke Maintainer
    Actually Lua 'table.remove(t)' function pops last element, so no need to set last element position.
  • you are right,
    table.insert and table.remove does it.
  • simwhisimwhi Member
    edited September 2016
    @n1cke Thanks for the feedback and efficiency tip.

    The main purpose of this tutorial was to demonstrate some fundamental data structures for game programming using OOP. Speed is crucial for a lot of games, I know, so where ever performance improvements can be made all the better!!

    Likes: antix, n1cke

    +1 -1 (+2 / -0 ) Share on Facebook
  • simwhisimwhi Member
    edited September 2016
    @keszegh Sure, that'll work. I like OOP though!!
Sign In or Register to comment.