Stack

Stack is a data structure that allows to store and retrieve elements in a last-in-first-out (LIFO) order. The operations of a stack are:

• push: add an element to the top of the stack

• pop: remove the top element from the stack

• peek: return the top element of the stack without removing it

• is_empty: check if the stack is empty

Here are collected selected problems that use stacks as a data structure.

Valid Parentheses

is_valid(s: str) → bool

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Time complexity: \(O(n)\)

Space complexity: \(O(n)\)