【算法专题--栈】栈的压入、弹出序列 -- 高频面试题（图文详解，小白一看就懂！！）

目录

一、前言

二、题目描述   

三、解题方法  

 💧栈模拟法💧-- 双指针

⭐ 解题思路

⭐ 案例图解

四、总结与提炼  

五、共勉  

---

一、前言

        栈的压入、弹出序列 这道题，可以说是--栈专题--，最经典的一道题，也是在面试中频率最高的一道题目，通常在面试中，面试官可能会从多个方面考察这道题目，所以大家需要对这道题目非常熟悉哦！！
       本片博客就来详细的讲讲解一下 栈的压入、弹出序列 的实现方法，让我们的面试变的更加顺利！！！ 

二、题目描述   

题目链接： 栈的压入、弹出序列_牛客题霸_牛客网 (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();}
};

 四、总结与提炼  

        最后我们来总结一下本文所介绍的内容，本文讲解了一道牛客中有关 栈的压入、弹出序列的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握  

五、共勉  

以下就是我对 栈的压入、弹出序列 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 栈专题 的理解，请持续关注我哦！！！