Stack

A visual representation of a stack

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 OOP 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()
	local output = self[#self]
	self[#self] = nil
	return output
end

Usage

Here's how to use it:

-- Note: Don't forget to copy/paste the code from above!
-- Make a new stack
local s = Stack.new()

-- Do stuff       Resulting stack
s:push(1)      -- {1}
s:push(5)      -- {1, 5}
s:push(10)     -- {1, 5, 10}
print(s:pop()) -- {1, 5}
print(s:pop()) -- {1}
s:push(20)     -- {1, 20}
print(s:pop()) -- {1}
print(s:pop()) -- {}

10 5 20

1

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 read/write from an area "behind" the stack. In our example above, this might result from attempting to pop() from the stack when it contains no values in it.

You could add the this line to the above example to debug your script if you believe a stack underflow might be a problem:

-- Insert this after line 11, inside Stack:pop()
assert(#self > 0, "Stack underflow")

This will cause an error and create a stack traceback, which can help you locate the source of the problem.

See Also

• Linked lists
• Arrays
• The Wikipedia article on Stacks