Stacks in Python

A standard data type list can be used as a Stack in Python:

>>> s = []

>>> s.append(1)
>>> s.append(2)
>>> s.append(3)

>>> s.pop()
3
>>> s.pop()
2

>>> s
[1]
>>> len(s)
1

>>> s[-1]  # top of the stack
1

Both append and pop are $O(1)$, whereas looking for an element is $O(n)$, where $n$ is the size of the stack.

The deque can be used as well (even if I prefer the standard list). You can also notice that the methods are actually the same and only the initialization is different:

>>> from collections import deque

>>> s = deque()

>>> s.append("a")
>>> s.append("b")

>>> s.pop()
'b'

>>> s
deque(['a'])
>>> len(s)
1

>>> s[-1]
'a'