PcoWSkbVqDnWTu_dm2ix
We use cookies on this site to enhance your user experience

Jul 30 2018, 1:33 PM PST 5 min

A stack is a Last-In-First-Out (LIFO) data structure. It is very commonly used in computer programming.

Visualization

A stack can easily be imagined as a stack of dinner plates. You start with one, and then you put another on top. In order to get to the very first plate, you must remove the plate(s) on top of it. So you remove the last plate first. The act of putting a plate on top of the stack is called pushing while removing a plate from the top is called popping.

Example

Implementation

Here is an implementation of stack in Lua with the help of some basic Articles/Object Oriented Programming|Object-Oriented Programming tools.

-- OOP boilerplate - create a class, add __index, then make a constructor
Stack = {}
Stack.__index = Stack
function Stack.new() return setmetatable({}, Stack) end

-- put a new object onto a stack
function Stack:push(input)
	self[#self+1] = input
end
-- take an object off a stack
function Stack:pop()
	assert(#self > 0, "Stack underflow")
	local output = self[#self]
	self[#self] = nil
	return output
end

Usage

Here’s how to use it:

Caveats

Overflows

A stack overflow is a common problem faced when using stacks. It occurs when the stack grows larger than the area it has been allocated.

However, in terms of the data structure implemented above, there is no need to worry about a stack overflow since Lua is dynamic and will allocate more memory to the stack as needed.

Underflows

A stack underflow is a problem relevant to our Lua implementation of a stack. It occurs when you attempt to pop() from the stack when it contains no values.

See Also

Tags:
  • coding
  • concept
  • lua