Data Structure (3) - Stack

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

Tags:
# data structure
# computer science