目录

题目：剑指 Offer 31. 栈的压入、弹出序列 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：剑指 Offer 31. 栈的压入、弹出序列 - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {

    }
};

解题思路：

这道题不算很复杂，

主要是要了解入栈和出栈的特性，

我的思路是：

先入栈，

然后让栈顶的值与需要出栈的值比较，

如果相等就出栈，然后继续比较，直到不相等或者栈为空，

然后就继续入栈，

每次入栈和出栈后 数组的下标就++，

如果入栈之后栈依然为空，证明所有元素都弹出了，返回 true，

如果入栈出栈的次数超过需要入栈出栈的数据个数，证明不是弹出序列，返回 false。         

代码：

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        //建一个栈
        stack<int> st;

        //设置访问数组的下标
        int i = 0;
        int j = 0;

        //记录循环次数（入栈出栈次数）
        int cnt = 0;

        //入栈出栈操作
        while(1)
        {
            //入栈
            if(i < pushed.size())
            {
                st.push(pushed[i++]);
            }

            //如果入栈之后栈依然为空，
            //证明所有元素都弹出了，返回 true
            if(st.empty())
            {
                return true;
            }
            
            //出栈
            while(!st.empty() && st.top() == popped[j])
            {
                st.pop();
                j++;
            }

            //记录循环次数
            cnt++;

            //如果入栈出栈的次数超过需要入栈出栈的数据个数，
            //证明不是弹出序列，返回 false
            if(cnt > pushed.size())
            {
                return false;
            }
        }
    }
};

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。