废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【栈的使用】，使用【栈】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。
有效括号序列【EASY】
非常适合栈这种数据结构的一道题
题干
解题思路
括号的匹配规则应该符合先进后出原理：最外层的括号即最早出现的左括号，也对应最晚出现的右括号，即先进后出，因此可以使用同样先进后出的栈：遇到左括号就将相应匹配的右括号加入栈中，后续如果是合法的，右括号来的顺序就是栈中弹出的顺序
- step 1：创建辅助栈，遍历字符串。
- step 2：每次遇到小括号的左括号、中括号的左括号、大括号的左括号，就将其对应的右括号加入栈中，期待在后续遇到。
- step 3：如果没有遇到左括号但是栈为空，说明直接遇到了右括号，不合法。
- step 4：其他情况下，如果遇到右括号，刚好会与栈顶元素相同，弹出栈顶元素继续遍历。
- step 5：理论上，只要括号是匹配的，栈中元素最后是为空的，因此检查栈是否为空即可最后判断是否合法。
代码实现
给出代码实现基本档案
基本数据结构：数组
辅助数据结构：哈希表
算法：迭代
技巧：哈希查找
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */ public boolean isValid (String s) { // 1 定义辅助栈 Stack<Character> stack = new Stack<Character>(); // 2 遍历字符串字符 for (int i = 0; i < s.length(); i++) { //遇到左小括号 if (s.charAt(i) == '(') { //期待遇到右小括号 stack.push(')'); } //遇到左中括号 else if (s.charAt(i) == '{') { //期待遇到右中括号 stack.push('}'); } //遇到左大括号 else if (s.charAt(i) == '[') { //期待遇到右大括号 stack.push(']'); } //没有遇到左括号的情况下来了个右括号||或者遇到的右边括号和栈顶元素不相同则认为非法 else if (stack.isEmpty() || stack.pop() != s.charAt(i)) { return false; } } // 3 字符串遍历完成后，且栈中没有元素则全部匹配完成，括号序列合法 return stack.isEmpty(); } }
复杂度分析
时间复杂度：遍历了一遍字符串，时间复杂度为O（N）
空间复杂度：使用了辅助栈，空间复杂度为O（N）
最小栈（包含min函数的栈）【EASY】
表达栈操作的一道题
题干
解题思路
我们都知道栈结构的push、pop、top操作都是O(1)，但是min函数做不到，于是想到在push的时候就将最小值记录下来，由于栈先进后出的特殊性，我们可以构造一个单调栈，保证栈内元素都是递增的，栈顶元素就是当前最小的元素
step 1：使用一个栈记录进入栈的元素，正常进行push、pop、top操作。
step 2：使用另一个栈记录每次push进入的最小值。
step 3：每次push元素的时候与第二个栈的栈顶元素比较，若是较小，则进入第二个栈，若是较大，则第二个栈的栈顶元素再次入栈，因为即便加了一个元素，它依然是最小值。于是，每次访问最小值即访问第二个栈的栈顶
代码实现
给出代码实现基本档案
基本数据结构：数组
辅助数据结构：哈希表
算法：迭代
技巧：哈希查找
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; import java.util.Stack; public class Solution { // 1 初始化操作栈和最小栈 private Stack<Integer> stack = new Stack<Integer>(); ; private Stack<Integer> minStack = new Stack<Integer>();; public void push(int node) { // 1 push时操作栈push元素，空栈或当前值小于操作栈顶元素时，当前值压入最小栈 if (minStack.isEmpty() || node < minStack.peek()) { minStack.push(node); } else { // 否则将操作栈顶元素压入最小栈 minStack.push(minStack.peek()); } // 2 无论如何，元素要压入操作栈 stack.push(node); } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int min() { return minStack.peek(); } }
复杂度分析
时间复杂度：没有循环和递归，任何操作都是常数阶，时间复杂度为O（1）
空间复杂度：使用了辅助栈，空间复杂度为O（N）
拓展知识：栈的基本操作
Java中栈的操作方法通常是通过使用java.util.Stack类或java.util.Deque接口的实现类来完成的。以下是一些常见的栈操作方法：
- 创建一个栈：
Stack<Integer> stack = new Stack<>();
- 入栈操作（push）：
stack.push(1); stack.push(2); stack.push(3);
- 出栈操作（pop）：
int top = stack.pop(); // 弹出栈顶元素并将其存储在变量中
- 查看栈顶元素但不移除它（peek）：
int top = stack.peek();
- 检查栈是否为空（isEmpty）：
boolean isEmpty = stack.isEmpty();
- 获取栈的大小（size）：
int size = stack.size();
- 清空栈（clear）：
stack.clear();
- 使用Deque实现栈：
你也可以使用java.util.Deque接口的实现类，如java.util.ArrayDeque来模拟栈的行为。以下是使用ArrayDeque实现栈的示例：
Deque<Integer> stack = new ArrayDeque<>(); stack.push(1); stack.push(2); stack.push(3); int top = stack.pop(); int size = stack.size(); boolean isEmpty = stack.isEmpty();
注意：在Java中，推荐使用Deque接口的实现类来模拟栈，因为Stack类是Vector的子类，而Vector在多线程环境下不是线程安全的，因此不推荐在多线程环境中使用Stack类。
