数据结构与算法5-栈

算法题：括号匹配

看一个算法题，也是我们提到的括号匹配问题，是力扣的原题哦~

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    每个右括号都有一个对应的相同类型的左括号。

我们用栈来实现一下，就用我们自己实现的栈来实现

 
/**
 * @author create by YanXi on 2022/9/6 6:18
 * @email best.you@icloud.com
 * @Description: 括号匹配测试
 */
public class StackTest {
 
    public static void main(String[] args) {
        String need = "(){}[]";
        System.out.println(String.format("isMatch(\"%s\") = %s" , need, isMatch(need)));
        String need1 = "[(){}[]";
        System.out.println(String.format("isMatch(\"%s\") = %s" , need1, isMatch(need1)));
    }
 
    public static boolean isMatch(String reg) {
        AyyayStack stack = new AyyayStack<>(15);
        char[] chars = reg.toCharArray();
        Character pop;
        
        for (char aChar : chars) {
switch (aChar){
                case '(':
                case '[':
                case '{':
                    stack.push(aChar);
                    break;
                case ')':
                    if (stack.isEmpty()) {
                        return false;
                    }
                    pop = stack.pop();
                    if (null == pop) {
                        return false;
                    } else if ('(' == (pop.charValue())) {
                        break;
                    } else {
                        return false;
                    }
                case ']':
                    if (stack.isEmpty()) {
                        return false;
                    }
                    pop = stack.pop();
                    if (null == pop) {
                        return false;
                    } else if ('[' == (pop.charValue())) {
                        break;
                    } else {
                        return false;
                    }
                case '}':
                    if (stack.isEmpty()) {
                        return false;
                    }
                    pop = stack.pop();
                    if (null == pop) {
                        return false;
                    } else if ('{' == (pop.charValue())) {
                        break;
                    } else {
                        return false;
                    }
                default:
                    return false;
            }
        }
        return stack.isEmpty();
    }
    
}

 时间复杂度为O(n)

栈的应用

想一想，哪些地方和栈类似

最常用的，是不是方法调用，比如A方法调用了B，然后再调用了C，是不是A方法是最后结束的？

在数学上，计算是不是也是这样，比如 1 + 2*2 - 4/2

所以说，也可以用栈实现一个简易的计算器

创建两个栈，一个存数字，一个存运算符

只要是数字，就入栈，如果是运算符，分为两种情况

        1、当前运算符和运算符栈顶运算符比较，如果比栈顶运算符的优先级高，那就直接入栈

        2、当前运算符和运算符栈顶运算符比较，如果比栈顶运算符的优先级低或者相同，不入栈，并且数字栈出栈两个，这两个数字按照当前运算符运算，运算完成，再将数字结果和后续符号入栈

仔细想想，是这么个道理不？代入上面写的例子

1，入数字栈

+，入符号栈

2，入数字栈

*，优先级比+高，入符号栈

2，入数字栈

-，比*优先级低，不入栈，取出数字栈两个，也就是2-2，执行，2*2=4,4入数字栈，-入符号栈

往后的类似

是不是？

我们上面还说过，用栈也可以实现浏览器的前进和后退功能，如何实现呢？

假设浏览网页A，点击B，再点击C，点击D

可以每次点击都入栈，后退的时候，入另一个栈

比如我现在在C，栈1应该是ABC，我现在点击后退，C从栈1挪到栈2，页面就到了B

当我在B，点击前进，栈2出栈，C

当然，还有一个现象，那就是在B页面，直接点击D，D返回不是C，而是B，所以，当点击了新的地方， 就应该清空栈2

说白了， 就是用两个栈，来严格维护网页的前面和后面

这就是栈大概的总结，栈是一个很神奇的结构，也是一个很好用的结构，用的好的话，能给我们一些场景简化很多，带来很多便利