What is the time complexity of stack?

Worst case O(1) push/pop/peek. Space complexity is O(n).

Stack

easy

Push and pop both touch the top, so nothing underneath ever moves. The call stack is one of these, which is why any recursion can be rewritten with an explicit stack.

Worst O(1) push/pop/peekSpace O(n)

Loading the stack engine…

Where to go next

Queue

easy

First in, first out - and why list.pop(0) is a bug.

Monotonic stack

hard

Next greater element in one linear pass.

Recursion and the call stack

easy

Watch fib(n) build an exponential tree, then memoise it away.