Data Structure (3) - Stack

• What is a Stack?
• When and where is a Stack used?
• Complexity
• Example - Brackets
• Leetcode problem
• Reference

What is a Stack?

A stack is a one-ended linear data structure which model a real world stack by having two primarily operations, namely push and pop.

When and where is a Stack used?

• Used by undo mechanism in text editors.
• Used in complier syntax checking for matching brackets and braces.
• Can be used to model pile of books or plates.
• Used behind the scenes to support recursion by keep tracking the previous function calls.
• Can be used to do a Depth First Search(DFS) on a graph.

Complexity

Action	Complexity
Pushing	$O(1)$
Popping	$O(1)$
Peeking	$O(1)$
Searching	$O(n)$
Size	$O(1)$

Example - Brackets

Given a string made up of the following brackets: {}()[], determine whether the brackets are properly match.

String	Result
[{}]	Valid
(()())	Valid
[()]}[	Invalid

Leetcode problem

Valid parentheses

• If current string is the left side of brackets, then append it into stack.
• If current string is the right side of brackets, then find the correspond left side and check whether the last element in stack is matched.
• Eliminate the pair brackets.

class Solution:
    def isValid(self, s: str) -> bool:

        n = len(s)        
        stack = []
        mappings = {
            ')':'(',
            '}':'{',
            ']':'[',
        }
        
        for i in range(n):
            rev = mappings.get(s[i])

            if s[i] in mappings.values():
                stack.append(s[i])

            else:
                if len(stack) == 0 or stack[-1] != rev:
                    return False
                else:
                    stack.pop()
        return len(stack) == 0

Reference

Data Structures - using lists ad stacks