0-栈的特点
- 🤺 栈就是操作受限的线性表，主要特点：先进后出
- 栈的常用操作：
push()入栈；pop()栈顶元素出栈；peek()查看栈顶元素；empty()栈判空 Java中直接提供了java.util.Stack栈的实现。如果自己实现栈，可以通过：数组、链表和Java提供的LinkedList这三种基本方式
1-栈经典题
1.1 括号匹配问题
括号匹配，表达式计算，这些问题都离不开栈，比如编译器检查代码文件里括号是否匹配时，就利用了左括号进栈，右括号与栈顶元素匹配来进行检查。力扣题目：20. 有效的括号 22. 括号生成 32. 最长有效括号 301. 删除无效的括号 856. 括号的分数
- 🧠 解题思路
有效括号最简单，左括号入栈，右括号与栈顶元素匹配就行。检查结束，栈未空或栈提前为空都表示不匹配......剩余题目先略
1.2 最大/小栈
题目：155. 最小栈 （难点在于常数时间内找到栈内最小的元素）
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
- 🧠 思路演进
- 栈不管是数组还是链表实现的，要找到最小元素，遍历的时间复杂度都是 O(n)
- 时间和空间是相对的，既然选择快，所以应该考虑“用空间换时间”
- 栈的特性，先进后出，所以，如果a进栈时已经有了b、c、d三个元素，那只有a还在栈里，这三个元素也在。所以申请一个辅助栈，记录最小元素即可，每次元素入栈时，辅助栈和自己的栈顶元素判断，比较后将最小元素入栈
Tips：用数组实现时，ArrayList是用数组实现的，便于查找，但不便增删，LinkedList是用双链表实现的，便于增删，不便查找。以上查找用得不多，主要是增删操作
1.3 计算器问题
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
- 🧠 思路演进
1>首先找约束，乘除的顺序必须按序计算，数据的范围可能是多位数，所以遍历字符串的时候需要把数据还原出来2>遍历的时候，① 还原出真实数据（多位） ② 遇到乘或除，可以直接计算 ③ 减法可以变成加法 ④ 最后将堆栈里的所有数据相加就是最后结果
代码如下：
import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public static int calculate(String s) {
Deque<Integer> stack = new ArrayDeque<Integer>(); // 堆栈
char preSign = '+';
int num = 0; // 用来辅助复原多位数
int n = s.length();
for (int i = 0; i < n; ++i) {
if (Character.isDigit(s.charAt(i))) {
num = num * 10 + s.charAt(i) - '0';
}
if (!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ' || i == n - 1) {
switch (preSign) { // 判断的是上一次的运算符
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
stack.push(stack.pop() * num);
break;
default:
stack.push(stack.pop() / num);
}
preSign = s.charAt(i); // 记录本次的运算符
num = 0;
}
}
int ans = 0;
while (!stack.isEmpty()) {
ans += stack.pop();
}
return ans;
}
}