Queues And Stacks - rFronteddu/general_wiki GitHub Wiki

Queues

Queues are FIFO, commonly used in Breadth First Search (BFS) such as finding the shortest path from the root to a target node.

BFS Templates

There are two main scenarios for using BFS, to traverse, or to find the shortest path.

Template 1:

int BFS (Node root, Node target) {
    //Find the shortest path from the root to the target
    Queue<Node> q; // stores nodes to process
    int step = 0;
    addRootTo q;

    while (q is not empty) {
        // iterate over nodes in q
        int size = q.size();
        for (int i = 0; i < size; i++) {
            Node curr = first node in q;
            return step if curr == target
            for (Node next : neighbors of curr) {
                add next to q;
            }
            remove the first node from q;
        }
        step = step  + 1;
    }
    return -1; // there is no path
}

Template 2:

Make sure you never visit a node to avoid getting stuck.

int bfs(Node root, Node target) {
    Queue<Node> q;
    Set<Node> visited;
    int step = 0;

    add root to q and visited

    while (q is not empty) {
        int size = q.size;
        for (int i = 0; i < size; i++) {
            Node curr = first node in q;
            return step if curr == target;

            for (Node next : curr neighborhood) {
                if (next is not in visited) {
                    add next to q and visited;
                }
            }
            remove first from q;
        }
        step++;
    }
    return -1;
}

Stacks

Stacks are LIFO. Elements are added at the end, however pop will remove the last element added (opposite to the queue).

Depth First Search: DFS

DFS

DFS can be used to find the path from root to target. In DFS, you backtrack only at the deepest node, as a result the path to a target may not be the shortest on.

When we reach the deepest node, we can pop back to trace back since we process the nodes in the opposite order.

Moving Average

⚠️ **GitHub.com Fallback** ⚠️