Stack

A stack is a data structure based on the Last In First Out principle. A common example is a stack of cards or CD-ROM’s, where the last item that was added to the stack will be the first one out when removing from the stack.

$\rightarrow$ In python, the default list class serves as an implementation of a stack; as you append to the end of the list, and the pop operation removes the last added item.

In this post, we saw a recursive implementation of pre-order traversal of a binary tree. We can convert it into a iterative algorithm using a stack as follows:

def pre_order_traversal(node):
    my_stack = [node]

    while my_stack:
        curr_node = my_stack.pop()
        print(curr_node.val)

        if curr_node.right is not None:
            my_stack.append(curr_node.right)
        if curr_node.left is not None:
            my_stack.append(curr_node.left)

Note that under the hood, recursive algorithms are evaluated using a stack. Whenever a recursive step is encountered, the corresponding function is pushed onto the stack. After the function has returned with some value, the item is popped out, so that the execution can proceed to the next step.

Given a string s containing just the characters $(, ), [, ], \{, \}$, determine if the input string is valid.

We maintain a stack to keep track of the latest paranthesis scope. Any time we encounter an open paranthesis, we push it onto the stack. When we encounter a closing paranthesis, we pop from the stack and check if the open-close pair matches or not. If it doesn’t match, then we have an invalid string.

def valid_paranthesis(s):
    my_stack = []

    pair_hashmap = {
        '[' : ']',
        '{': '}',
        '(', ')',
    }

    for char in s:
        if char in ['(', '[', '{']:
            my_stack.append(char)
        else:
            last_open = my_stack.pop()
            if pair_hashmap[last_open] != char:
                return False
    return True

Queue

A queue is a data structure that follows the First In First Out principle. A common example is people lined up in a queue at a bus stop. The person who came first will be the first to board the bus.

$\rightarrow$ In python, use deque from collections module for queue implementation.

In this post, we saw how a queue can be used to obtain a level-order traversal of a binary tree. In general, if we want to perform a BFS over an unweighted graph, we can use a queue. The following example demonstrates this:

Given a binary matrix, return the shortest path that starts from the top-left corner and ends in the bottom-right corner. Only cells with value 0 can be visited. From a cell you can move in any of the 4 directions sharing an edge.

The binary matrix can be thought of as a graph, with each cell as a node, sharing an edge with its adjacent cells. To find the shortest path from a source to destination, we can start a BFS from the start node. As stated above, we will use a queue for this task. We also need to make sure that we keep track of cells that we have already visited to avoid loops and to avoid going down a path that had(or is) already been(being) traversed.

Since we also want to explicitly print out the shortest path and not just the length, we need to, while visiting a node keep track of where we came from. To do this we will make a separate data structure for the node.

from dataclasses import dataclass

@dataclass
class Node:
    pos_x: int
    pos_y: int
    came_from: Node

def shortest_path_binary(grid):
    m, n = len(grid), len(grid[0])

    visited = set()
    
    # Start position
    start_node = Node(0, 0, None)
    if grid[0][0] == 1:  # edge case: start position itself can't be visited
        return None

    queue = deque([start_node])
    visited.add((0, 0))

    while queue:
        node = queue.popleft()

        # stopping criteria
        if (node.pos_x == m - 1) and (node.pos_y == n - 1):
            return node

        for (step_x, step_y) in directions:
            new_pos_x = node.pos_x + step_x
            new_pos_y = node.pos_y + step_y

            # criteria to visit connected nodes (cells)
            if ((new_pos_x >= 0) and (new_pos_x < m) and  
                (new_pos_y >= 0) and (new_pos_y < n) and 
                (grid[new_pos_x][new_pos_y] == 0) and 
                ((new_pos_x, new_pos_y) not in visited)):
                visited.add((new_pos_x, new_pos_y))
                next_node = Node(new_pos_x, new_pos_y, came_from=node)
                queue.append(next_node)

    # We only reach this if no path present 
    return None

Once we have the destination node returned using the above function, we can simply back-track using the came_from variable as follows:

curr_node = shortest_path_binary(grid)

res = []
while curr_node is not None:
    res.append((curr_node.pos_x, curr_node.pos_y))
    curr_node = curr_node.came_from
    
print(res[::-1])

Common data structures

Categories

Stack

Queue