数据结构4.0

大家好，今天是栈的知识点~

一、栈的概念

1.0 栈的概念

2.0 概念区分

二、栈的方法

1.0 MyStack方法：

2.0 将元素压入栈顶

3.0 移除并返回栈顶元素

4.0 返回栈顶元素但不移除

三、栈的题目

1.0括号匹配

2.0逆波兰表达式求值

3.0 出栈入栈次序匹配

4.0 最小栈

5.0 将递归转化为循环

一、栈的概念

1.0 栈的概念

如果将栈底当作数组下标为0的元素依此类推~

这样我们就能发现其实栈的底层是一个数组

现实生活中的例子：羽毛球桶（只允许在固定的一端插入和删除）

2.0 概念区分

栈、虚拟机栈、栈帧有什么区别呢？

栈：数据结构里面的栈

虚拟机栈：内存当中的一块区域

栈帧：你每次调用这块方法的时候创建的一个区域

二、栈的方法

peek 瞄一眼就是瞄一眼栈得到它的栈顶元素

pop 先返回栈顶元素然后移除

下面我们开始自己模拟实现一遍，加深对栈的理解：

1.0 MyStack方法：

构造一个栈栈的数据结构底层是一个数组说到数组又离不开uesdSize

所以我们的代码是：

public class MyStack {private int[] elem;private int usedSize;private static final int DEFAULT_CAPACITY = 10;public MyStack ()  {this.elem=new int[DEFAULT_CAPACITY];}
}

2.0 将元素压入栈顶

首先还是要判断我们的栈（数组）满了没有，如果满的话需要扩容

将元素压入栈顶代码就是elem[usedSize]=val; usedSize++;（这个小更新经常容易被忘记）

public void push(int val){if(isFull()){elem= Arrays.copyOf(elem,2*elem.length);}this.elem[usedSize]=val;usedSize++;}
public boolean isFull(){return usedSize==elem.length;}

3.0 移除并返回栈顶元素

删除元素首先看能不能删除也就是说要进行操作删除这个操作的对象有没有元素

所以我们第一步还是需要判断是否为空（和单链表删除方法想法类：插入先看满了没有删除先看是不是空呢）

要返回栈顶元素：我们先把这个元素存起来然后删除

int oldVal = elem[ usedSize -- 1]; usedSize --;

然后返回栈顶元素 return oldVal；

下面是代码：

 public int pop (){if(isEmpty()){throw new EmptyException();}int oldVal = elem[usedSize-1];usedSize--;return oldVal;}

4.0 返回栈顶元素但不移除

peek方法直接就是返回oldVal就可以啦和pop方法有点类似

代码纯享：

public int peek(){if (isEmpty()){throw new EmptyException();}return elem[usedSize-1];}public boolean isEmpty(){return usedSize==0;}

和单链表和双链表还有顺序表对比好简单哇

三、栈的题目

1.0括号匹配

20. 有效的括号 - 力扣（LeetCode）

如果我们没有学过栈这个数据结构的话，题目会变得很麻烦。这也是为什么数据结构是算法的基础。学习好数据结构，能为算法打下坚实的基础~

思路分析：

这道题重要的是顺序匹配第一个右括号要和最后一个左括号匹配

不是说括号个数是偶数就一定匹配

为什么要用栈栈的插入和删除复杂度是O(1) 对于这个题更合适

如果是链表需要删除，相对于栈来说复杂度有点高了

利用的就是栈的特性后进先出

我们可以先遍历一遍字符串将所有的左括号放入栈里面

遇到右括号了开始消除边遍历边消除

这时候会遇到各种情况：左括号和右括号不匹配多出来的右面括号多出来的左括号

对于peek和pop的使用要知道匹配上了才能用pop消除哦

注意：

左括号不匹配：左括号在栈里面没有被消除多出来的左括号我们用代码最后的是否empty来检验

右括号不匹配：此时栈是空的但是右括号还有未被消除的我们用else里面的

如果一上来就是右括号所以需要判断是否栈为空那个代码

消除后看栈的空否

就是我们要理解题目对于出现的各种情况都了解知道怎么判断和应对

甚至可以去把情况分类对于这道题目：左括号开头右括号开头左括号个数大于右括号个数

右面括号个数大于左括号

下面是我的代码：

class Solution {public boolean isValid(String s) {Stack <Character> stack = new Stack();for(int i = 0;i<s.length();i++){char ch = s.charAt(i);if(ch=='(' || ch=='{' || ch=='['){//左括号入栈stack.push(ch);}else{//右括号不匹配//虽然右括号是和左括号匹配的 但是栈里面并不是一定有左括号的if(stack.empty()){return false;}char top = stack.peek();//此时top是从栈里面拿出来的左括号 ch是括号if(ch==')' && top=='(' || ch=='}' && top=='{' || ch==']' && top=='['){stack.pop();} else{//左括号不匹配return false;}}}  if(! stack.empty()){return false;}return true;
}
}

2.0逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

思路分析：

（1）什么叫做逆波兰表达式：

1+2*5 中缀表达式 ----------> 后缀表达式 12+5*

后缀表达式的别名也叫做逆波兰表达式

(2)中缀表达式如何转换为后缀表达式：

一个快速的方式：拿到中缀表达式从左到右先加减后乘除加括号

用数字把字母代替回来

（3）逆波兰表达式的计算：

如果大家看的比较迷糊的话：可惜这里不是视频演示效果比较折扣

i从1开始遍历那串后缀表达式是数字压入栈此时栈里面有 1 2 3 遇到*号了

弹出栈里面的两个元素 2和3 2*3=6 放回栈里面此时栈里面的数字为 1 6

以此类推

最后得到的结果在栈里面

（这里的运算符都是双目运算符，靠近的两个，用到了栈的特点）

下面是图片展示：

（4）代码实现：

一步一步来分析把这道题拆解成小问题逐个击破

我们根据上面的思路来进行翻译

过程：遍历字符串遇到是数字压入栈遇到是运算符号出栈两个计算后压入栈直到遍历结束

如何遍历字符串？

使用for循环移动 for(int i = 0；i<字符串的长度；i++) 解决！

如何判断是数字还是运算符号？

不是数字就是符号符号可以一个一个对比出来是不是

if语句 if（s[ i ]== 加减乘除） { } else{ s.push(s[ i ]) } 不是符号，所以为数字直接压入栈解决！

如果遇到运算符号了呢？

出栈两个元素然后运算注意左右顺序 int a= s.pop(); 第一个出来的a为右操作数

int b = s.pop(); 左操作数计算

如何直到自己遇到了哪个运算符号？

这里就想到了else if语句然后之后的逻辑是计算好了压入栈

当然也可以用swiitch语句

综上-->代码纯享版：

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(int i = 0;i<tokens.length;i++){String token = tokens[i];if(token.equals("+")){int a = stack.pop();int b = stack.pop();int c = b+a;stack.push(c);}else if(token.equals("-")){int a = stack.pop();int b = stack.pop();int c = b-a;stack.push(c);}else if(token.equals("*")){int a = stack.pop();int b = stack.pop();int c = b*a;stack.push(c);}else if(token.equals("/")){int a = stack.pop();int b = stack.pop();int c = b/a;stack.push(c);}else{stack.push(Integer.parseInt(tokens[i]));}}return stack.peek();}
}

注意：

小问题：
对于Stack的创建
字符串类里面的知识:
首先是 i<tokens.length( )应该改为tokens.lenth 因为这里的tokens是一个字符串
其次 String token = tokens[i]; 这样得到的就是一个字符了
然后 token.equals("+") equals() 是 Java 中用于比较两个对象内容是否相同的方法
最后：Integer.parseInt() 是 Java 中用于将字符串转换为整数的核心方法
这里的注意点说明我的字符串那节课没有认真听，之后复习复习

3.0 出栈入栈次序匹配

栈的压入、弹出序列_牛客题霸_牛客网

这个题的难度不大分析了思路之后把思路实现为代码就好

思路分析：

两个序列一个是入栈序列一个是出栈序列

我们定义一个栈A 讲入栈序列一步一步放到里面

同时和出栈序列对比如果匹配上了那么从栈A里面弹出来同时出栈序列遍历

如果最后入栈序列遍历完了出栈序列也遍历完了栈还是空的

说明符合情况返回true

注意：

我们要注意空指针异常和数组越界分析同时遍历的两个数组

入栈数组的临界是空那么我们的判断条件是 !stack.empty()

出栈数组的临界是满那么我们的判断条件是 j<popV.length

下面是代码：

import java.util.*;public class Solution {public boolean IsPopOrder (int[] pushV, int[] popV) {Stack <Integer> stack = new Stack<>();int j = 0;for(int i= 0;i < pushV.length;i++){stack.push(pushV[i]);while(!stack.empty() && j<popV.length&&stack.peek() == popV[j]){stack.pop();j++;}}return stack.empty();}
}

4.0 最小栈

155. 最小栈 - 力扣（LeetCode）

审清题目

思路分析：

这道题目的关键点是要在O（1）时间内完成，也是题目的启发点

对于常数时间内的理解：

什么是「常数时间」？

定义：时间复杂度为 O(1)，即无论栈中有多少元素（1个或100万个），获取最小值的操作耗时固定不变。
对比其他时间复杂度：
- O(1)：固定时间（如数组按索引访问）
- O(n)：线性时间（如遍历链表查找）
- O(log n)：对数时间（如二分查找）

也就是说：

时间复杂度不达标：遍历栈需要 O(n) 时间（n 为元素数量），违反题目要求的 O(1) 时间复杂度。

对于实现O(1)获取最小值有两种经典方法：一种是辅助栈同步记录一种是差值存储法

这个就是经验累积了

获取堆栈中的最小元素：

我们可以定义一个辅助栈 minStack 用来记录当前的最小值如果发现新的比这个还小的最小值

我们及时的更新辅助栈，最后取辅助栈的栈顶元素就是达到了O（1）的要求

注意：

（1）第一次放的时候栈为空这个时候元素都必须先放进去

（2）平时要养成好的习惯

我们使用pop方法的时候永远要先判断一下栈是否为空呢单链表里面也一样

执行删除单链表的时候我们需要判断单链表是否为空

下面是代码：

class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {//普通栈是正常放stack.push(val);if(minStack.empty()){minStack.push(val);}else{if(val<=minStack.peek()){minStack.push(val);}}}public void pop() {//以后记住 pop的必要前提都要先判断一下栈是不是空呢if(! stack.empty()){int ret = stack.pop();if(minStack.peek() == ret){minStack.pop();}}// if(stack.pop()==minStack.peek()){}//获取正常栈的栈顶元素public int top() {//又忘了前提是是否判断为空了if(stack.empty()){return -1;}return stack.peek();}public int getMin() {if(stack.empty()){return -1;}return minStack.peek();}
}

5.0 将递归转化为循环

逆序打印链表

递归、逆序

递归递和归

我们把过程结果依此放入栈最后拿出来就是逆序的就是这个道理

循环走完了节点都放到栈里面了我们开始弹出一直弹到栈为空

粗略图看一下水印没有弄好补药嫌弃哇哈哈

示例代码：

public void reversePrintList(){Stack<ListNode> stack = new Stack<>();ListNode cur = head;while(cur != null){stack.push(cur);cur=cur.next;}while(!stack.isEmpty()){ListNode top = stack.pop();System.out.println(top.val);}}

这样，我们就利用了栈的特点实现了逆序

感谢大家的支持