?作者简介：一位喜欢写作，计科专业大二菜鸟
个人主页：starry陆离
首发日期：2022年7月14日星期四
上期文章：『牛客|每日一题』模板栈
订阅专栏：『牛客刷题集锦』
【牛客刷题集锦|『牛客|每日一题』 栈的压入、弹出序列】每日推荐：基础算法无论在研究生面试还是求职面试都是十分重要的一环，这里推荐一款算法面试神器：牛客网-面试神器；算法题只有多刷勤刷才能保持思路与手感，大家赶紧行动起来吧（温馨提示：常见的面试问答题库也很nice哦）
文章图片
如果文章有帮到你的话记得点赞+收藏支持一下哦
文章图片
『牛客|每日一题』 栈的压入、弹出序列
- 1.每日一题
- 2.方法一：辅助栈
-
- 2.1思路分析
- 2.2具体做法
- 2.3代码题解
- 3.方法二：原地栈
-
- 3.1思路分析
- 3.2具体做法
- 3.3代码题解
1.每日一题
文章图片
2.方法一：辅助栈 2.1思路分析 题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以用一个栈来模拟。对于入栈序列，只要栈为空，序列肯定要依次入栈。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。
//入栈：栈为空或者栈顶元素不等于出栈数组(注意还要控制数组越界j2.2具体做法
- step 1：准备一个辅助栈，两个下标分别访问两个序列。
- step 2：辅助栈为空或者栈顶不等于出栈数组当前元素，就持续将入栈数组加入栈中。
- step 3：栈顶等于出栈数组当前元素就出栈。
- step 4：当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个序列都访问完就是匹配的。
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
//元素的个数
int n=pushA.length;
//辅助栈
Stackstack=new Stack();
//遍历入栈的下标
int j=0;
//遍历出栈数组，i为出栈数组下标
for(int i=0;
i 
文章图片
3.方法二：原地栈 3.1思路分析 方法一我们使用了一个辅助栈来模拟，但是数组本来就很类似栈啊，用下标表示栈顶。在方法一中push数组前半部分入栈了，就没用了，这部分空间我们就可以用来当成栈。原理还是同方法一一样，只是这时我们遍历push数组的时候，用下标n表示栈空间，n的位置就是栈顶元素。
3.2具体做法
- step 1：用下标i表示栈空间，用j表示出栈序列的下标。
- step 2：遍历每一个待入栈的元素，加入栈顶，即push数组中i的位置，同时增加栈空间的大小，即i的大小。
- step 3：当栈不为空即栈顶i大于等于0，且栈顶等于当前出栈序列，就出栈，同时缩小栈的空间，即减小i。
- step 4：最后若是栈空间大小i为0，代表全部出栈完成，否则不匹配。
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
//栈空间的大小
int i=0;
//出栈序列下标
int j=0;
//遍历入栈数组
for(int a:pushA){
//将元素加入栈顶
pushA[i]=a;
//当栈不空且栈顶元素等于出栈数组元素时
while(i>=0&&pushA[i]==popA[j]){
j++;
//元素出栈，缩小栈空间大小
i--;
}
//为下一个元素入栈做准备
i++;
}
//栈空间的大小为0说明元素全部出栈
return i==0;
}
}
文章图片
每日推荐：基础算法无论在研究生面试还是求职面试都是十分重要的一环，这里推荐一款算法面试神器：牛客网-面试神器；算法题只有多刷勤刷才能保持思路与手感，大家赶紧行动起来吧（温馨提示：常见的面试问答题库也很nice哦）
文章图片
推荐阅读
- 牛客刷题集锦|『牛客|每日一题』模板栈
- 后端|分布式锁用 Redis 还是 Zookeeper（看完你就明白了）
- #|红黑树的学习
- 某课算法与数据结构体系课已完结
- Python每日一练|Python每日一练（牛客新题库）——第14天（元组、字典练习）
- 个人学习|牛客网在线编程题库——个人练习打卡记录（暂时停止）
- 学习笔记|【这可能不只是一篇面经】- 有话想说的四个月
- Linux|进程间通信之共享内存
- Linux|管道实现进程间通信之命名管道