Making a stack

Stack data structure can be defined in the Lua language as a closure that always returns a new table. This table contains two functions defined by keys, push and pop. Both operations run in constant time.

Getting ready

Code from this recipe will be probably used more than once in your project so that it can be moved into the Lua module file with similar algorithms. The module file can use the following structure:

-- algoritms.lua

-- Placeholder for a stack data structure code 

return {
  stack = stack,
}

This module structure can be used with algorithms from other recipes as well to keep everything organized.

How to do it…

The following code contains a local definition of the stack function. You can remove the local statement to make this function global or include it as part of the module:

local function stack()
  local out = {}
  out.push = function(item)
    out[#out+1] = item
  end
  out.pop = function()
    if #out>0 then
      return table.remove(out, #out)
    end
  end
  out.iterator = function()
    return function()
      return out.pop()
    end
  end
  return out
end

This stack data structure can be used in the following way:

local s1 = stack()
-- Place a few elements into stack
for _, element in ipairs {'Lorem','ipsum','dolor','sit','amet'} do
  s1.push(element)
end

-- iterator function can be used to pop and process all elements
for element in s1.iterator() do
     print(element)
end

How it works…

Calling the stack function will create a new empty table with three functions. Push and pop functions use the property of the length operator that returns the integer index of the last element. The iterator function returns a closure that can be used in a for loop to pop all the elements. The out table contains integer indices and no holes (without empty elements). Both the functions are excluded from the total length of the out table.

After you call the push function, the element is appended at the end of the out table. The Pop function removes the last element and returns the removed element.