试玩网站怎么做友情链接赚钱
目录
一、前言
二、题目描述
三、解题方法
💧栈模拟法💧-- 双指针
⭐ 解题思路
⭐ 案例图解
四、总结与提炼
五、共勉
一、前言
栈的压入、弹出序列 这道题，可以说是--栈专题--，最经典的一道题，也是在面试中频率最高的一道题目，通常在面试中，面试官可能会从多个方面考察这道题目，所以大家需要对这道题目非常熟悉哦！！
本片博客就来详细的讲讲解一下 栈的压入、弹出序列 的实现方法，让我们的面试变的更加顺利！！！
二、题目描述
题目链接： 栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出序列。
假设压入栈的所有数字均不相等。
例如：序列{1,2,3,4,5}是某栈的压栈序列，序列{4,5,3,2,1}是该压栈序列对应的一个弹出序列，但{4,3,5,1,2}就不可能是该压栈序列的弹出序列。
三、解题方法
💧栈模拟法💧-- 双指针
解决该问题需要借助一个辅助栈，把输入的第一个序列中的数字依次入栈，并按照第二个序列的顺序依次从该栈中弹出数字。
⭐ 解题思路
开始：
入栈 序列 当前的数据 入栈
栈顶元素 跟 出栈序列比较，是否相等
- 相等，栈顶元素出栈，出栈序列 指针向后移动
- 不相等，入栈序列继续入栈
结束判断：
- 出栈序列走到尾部，说明完全匹配
- 栈顶元素和出栈序列匹配不上，且入栈序列已经走完了，没有数据可以入栈了
⭐ 案例图解
入栈序列：【1，2，3，4，5】 出栈序列：【4，5，3，2，1】
- 开始入栈，进行比较
- 当 栈顶元素【4】 和 出栈序列【4】相等 ，【4】出栈，pop指针向后移动
- 开始进行逐一匹配
- 直到，辅助栈 为空结束！！
代码：
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// 创建一个 栈stack<int> st;// 建立两个下标指针，一个用来指向当前的入栈序列，一个用来指向的出栈序列int pushi = 0, popi = 0;// 开始入栈 , 当入栈 序列 走完结束while(pushi < pushV.size()){st.push(pushV[pushi++]); // 入栈// 进行入栈序列 和 出栈序列 进行匹配// 当栈不能为空，或者 ，进行栈顶 和 出栈序列成功匹配while(!st.empty() && st.top() == popV[popi]){// 当匹配成功时st.pop();popi++;} }return popi == popV.size();}
};四、总结与提炼
最后我们来总结一下本文所介绍的内容，本文讲解了一道牛客中有关 栈的压入、弹出序列的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握
五、共勉
以下就是我对 栈的压入、弹出序列 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 栈专题 的理解，请持续关注我哦！！！
