数据结构与算法（栈）~ 介绍栈以及力扣上几道栈题目的方法和套路
✿栈的概念以及特点：是限制在表的一端进行插入和删除操作的线性表。特点:后进先出
1，栈的数据结构：
（1）早期 java.util.Stack 是 继承 Vector 的子类，后期官网不推荐啦
实现栈特点（使用 双端队列 Deque 的子类 LinkedList 双向链表 便可完美实现 栈 的功能特性）】
（2）栈主要的功能（增删改查）：定义一些接口方法：
2，栈的力扣算法题：
总结一些小套路吧 （没有通用的套路，就讲一下方法哈）：
（1）150_逆波兰表达式求值 的方法和套路 ：
方法一： 题意：给的逆波兰表达式就只有 数字和运算符呀， 所以自己写一个方法判断是否非数字即可呀。
■ 后缀表达式：
* 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），
* 并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
（2）20_有效的括号 的方法和套路 ：
方法一：判断是左括号就入栈，右边括号就出栈左括号与之进行匹配验证（一旦不匹配，返回失败结果）（套路就是：添加哈希表【左括号，右括号】，进行匹配判断）
（3）224_基本计算器 的方法和套路 ：
方法一：思路：展开。对数据（带上符号）进行累加。默认数据的符号是‘+’ ，遇到：
● ‘+’ ：与原符号相同（即栈顶）
● ‘-’： 与原符号相反（即负 栈顶）
● ‘（’：入栈当前符号，（当前符号会影响（的每一个数据的原符号））（入栈当前符号）
● ‘）’：出栈当前符号（结束当前符号对（的每个数据的原符号）的影响。）
（4）856_括号的分数 的方法和套路 ：
方法一：官网的栈的解法（写得太精简了，没看懂）~改为模拟法：
public int scoreOfParentheses(String s) { Stack<String> stack = new Stack<String>(); for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); String ch2 = Character.toString(ch); if (ch2.equals("(")) { // 一开始遇到左括号，都是直接入栈 stack.push(ch2); } else { // 分类：一开始直接是右括号，匹配一对，得一分； 如果遇到是数字，开始计算深度 if (ch2.equals(")")) {//这里要加以判断栈顶是否为（，才能匹配 if(stack.peek().equals("(")) { stack.pop(); stack.push("1"); }else { //逻辑是找到第一对之后才有机会有，进入了此状态后，才有后边的计算，☆☆☆找到第一对 是后边的情况发生前提 int depth = 0; String tmp_top = stack.pop(); while (!("(".equals(tmp_top))) { depth += Integer.parseInt(tmp_top); tmp_top = stack.pop(); } // 跳出循环，说明是遇到左括号了 // stack.pop(); 跳出时就pop() 掉了 stack.push(Integer.toString(2 * depth)); } } } } int sum = 0; while (!stack.empty()) { sum += Integer.parseInt(stack.pop()); } return sum; }
