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

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

To use it:

-- Make a new stack
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

See Also

• Linked lists
• Arrays
• The Wikipedia article on Stacks