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

simwhi · September 2016

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.

SinisterSoft · September 2016

Useful, thanks.

n1cke · September 2016

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

keszegh · September 2016

just a simple table t and
table.insert for push
and
x=t[#t] t[#t]=nil for pop
wouldn't be good enough?

n1cke · September 2016

Actually Lua 'table.remove(t)' function pops last element, so no need to set last element position.

keszegh · September 2016

you are right,
table.insert and table.remove does it.

simwhi · 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!!

simwhi · September 2016

@keszegh Sure, that'll work. I like OOP though!!

Howdy, Stranger!

Categories

In this Discussion

Top Posters

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

Comments

Howdy, Stranger!

Quick Links

Categories

In this Discussion

Top Posters

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

Comments