Hi! I'm learning about data structures and I'll post my notes here.

Abstract data types with the following operations:

Think of this data structure as a stack of books.

This data structure can be implemented in two ways. One of each has its disadvantages.

1. Implementation with Arrays

To implement a stack we can use an array. Define the max elements in the array and start storing elements.

Limitation

We can waste space if we define an array beforehand. We will have places available empty.

2. Implementation with Linked Lists

We implement a Singly Linked list under the hood to avoid the limitation of using an array which is the max items.

Now, the linked list allow us to growth our list dynamically without wasting space although we manage pointers.

Under the hood our stack call these methods of linked lists:

• Push() → PushFront()
• Pop() → PopFront()
• Empty() → Empty()

Use of Stacks

Stacks can help us to solve problems where we need to keep track of input occurrence. For instance:

Problem: Balanced Brackets

Input: A string str consisting of “(”, “)”, “[”, “] ” characters.

Output: Return whether or not the string’s parentheses and squares are balanced

Examples:

Link to LeetCode problem: https://leetcode.com/problems/valid-parentheses/description/?envType=problem-list-v2&envId=stack

Solution

Use a stack to keep track of parentheses order. We shall store only opening characters like: {, (, [

We should iterate over the string and validate if current character matches our list of opening characters. If we found one we keep it in our stack.

If the character is different we must validate whether our stack is empty, if true, means we don’t have a valid string. When our stack is not empty, we must POP the most recently-added element to verify if the current character matches with a closing character. ), ], } If so, we continue iterating over the string.

If character does not match we must say that our Input String is not valid (Balanced).

At the end if the stack has still items, it is clear that our string is also unbalanced. Why? because we iterate over the string and we never found a pair for the item in our stack (the closing character)

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        opening_chars = ["(", "[", "{"]
        for char in s:
            if char in opening_chars:
                stack.append(char)
            else:
                if len(stack) == 0:
                    return False
                top = stack.pop()
                if (
                    (top == "(" and char != ")")
                    or (top == "{" and char != "}")
                    or (top == "[" and char != "]")
                ):
                    return False

        return len(stack) == 0