This is the 24th day of my participation in Gwen Challenge

Stack: A first-in, last-out data structure

In the LIFO data structure, the latest element added to the queue is processed first. Unlike a queue, a stack is a LIFO data structure. Typically, an insert operation is referred to as a push on the stack. Like a queue, a new element is always added to the end of the stack. However, the delete operation, the unstack pop, will always remove the last element in the queue relative to it.

Simple implementation of stack

class MyStack {
    private List<Integer> data;// Store elements
    public MyStack(a) {
        data = new ArrayList<>();
    }
    /** push. */
    public void push(int x) {
        data.add(x);
    }
    / * * to * / empty
    public boolean isEmpty(a) {
        return data.isEmpty();
    }
    /** get the top element */
    public int top(a) {
        return data.get(data.size() - 1);
    }
    / * * the stack * /
    public boolean pop(a) {
        if (isEmpty()) {
            return false;
        }
        data.remove(data.size() - 1);
        return true; }};public class Main {
    public static void main(String[] args) {
        MyStack s = new MyStack();
        s.push(1);
        s.push(2);
        s.push(3);
        for (int i = 0; i < 4; ++i) {
            if(! s.isEmpty()) { System.out.println(s.top()); } System.out.println(s.pop()); }}}Copy the code

Stack and depth-first search

Similar to BFS, depth-first search (DFS) is another important algorithm for traversing/searching trees/graphs. It can also be used in more abstract scenarios.

There are three traversal modes in DFS: preorder traversal, mid-order traversal and post-order traversal. The three traversal modes have one common feature: they do not backtrack unless the deepest node is reached.

The first sequence traversal

A front-order traversal first visits the root node, then the left subtree, and finally the right subtree.

In the sequence traversal

Middle-order traversal traverses the left subtree, then visits the root node, and then traverses the right subtree.

After the sequence traversal

Back-order traversal traverses the left subtree, then the right subtree, and finally visits the root node of the tree.

It is important to note that when a node in the tree is deleted, the deletion is done in the order of a back-order traversal. That is, when you delete a node, you delete its left node and its right node first, and then delete the node itself.

Recursive depth-first search

When DFS is implemented recursively, it does not appear to use any stack, but rather the system-provided function call stack.

/* * Return true if there is a path from cur to target. */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) = =true; }}return false;
}
Copy the code

Shows depth-first search using a stack structure

Recursive schemes have the advantage of being easier to implement. However, there is a major drawback: when the recursion is too deep, it is prone to stack overflows. Using the display stack to implement depth-first can circumvent this problem.

/* * Return true if there is a path from cur to target. */
boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> s;
    add root to s;
    while (s is not empty) {
        Node cur = the top element in s;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to s;
                add next to visited;
            }
        }
        remove cur from s;
    }
    return false;
}
Copy the code