Stack

A stack is an abstract data type that follows LIFO (last in, first out) order: the last element inserted is the first one removed.

Conceptually it needs two operations:

• push(x): insert at the top.
• pop(): remove from the top.

In Python

A stack is normally represented with a list:

stack = []
stack.append(1)
stack.append(2)
stack.pop()  # 2

Both append() and pop() at the end of a list are $O(1)$ amortized.