[Easy] Stack is a linear collection of items where items are inserted and removed in a particular order. Stack is also called a LIFO Data Structure because it follows the “Last In First Out” principle i.e. the item that is inserted in the last is the one that is taken out first.
Implement stack data structure and its relevant methods:
push()Add an element to the top of a stack.pop()Remove an element from a stack.peek()Return the value of the top element of a stack.isEmpty()Return if the stack is empty.
[Easy] Given a string s 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.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
s = "()" => true.
s = "()[]{}" => true.
s = "(]" => false. The brackets are not the same type.
s = "([)]" => false. The brackets are not closed in the correct order.
Use a stack to track open brackets. Iterate over the string: whenever an opening bracket is found, push it onto the stack. Whenever a closing bracket is found, check that the stack is not empty and that its top element is the matching opening bracket — if so, pop it, otherwise the string is invalid. After processing all characters, the string is valid only if the stack is empty, meaning every open bracket was matched and closed.