Stack

Why it costs this much

Only the top changes, so push and pop touch one end and never shift other items.

Code

stack = []
stack.append(x)    # push: O(1) amortized
top = stack[-1]    # peek: O(1)
stack.pop()        # pop from the end: O(1)

Python is the baseline example used across the site.

Common pitfalls

Searching or reading from the middle is O(n). A Python list works well as a stack, but a plain list is a poor queue.

Operation by operation

Stack push, pop, peek. Backed by a dynamic array or linked list. Push is amortized O(1) with an array. Only the top is accessible.