栈-946.验证栈序列-力扣(LeetCode)

一、题目解析

1、判断push和pop的序列是否符合poped

2、poped的长度和pushed相同

3、pushed中没有重复元素

二、算法原理

相信大多数读者在学习栈这个数据结构时，肯定接触过类似的题目：判断下面序列能通过push和pop得到？而今天这道题就是把我们平时做题时在纸上或者在大脑中推演的过程用代码实现，并判断

解法：栈模拟

这里不一定要用栈来实现，这里可以用vector来实现一个简单的栈，通过vector的back()达到栈的top()的效果

想了解更多相关知识，可以自行访问查询

链接：cplusplus.com - The C++ Resources Network

模拟过程：

1、在入栈后，先判断入栈的元素是否等于poped中的元素(通过维护一个下标索引来遍历poped)

2、如果相等，则执行出栈操作，加加poped的下标索引。但我们出栈操作可能是需要重复的，所以这里是一个循环

3、如果不相等，则继续入栈

4、如果符合栈序列，则栈内元素为空，反之不为空，所以我们将栈的元素是否为空作为返回结果，记得取反哦(取反是用vector模拟栈需要取反，如果直接使用栈empty()无需取反)

vector模拟取反是因为，返回的是size()，如果为空，则size=0，0为false，非0为true，所以需要取反；empty()如果为空，则返回true，反之为false

三、代码示例

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
    {
        vector<int> num;
        int  i = 0, j = 0;
        for (int i = 0; i < pushed.size(); i++)
        {
            num.push_back(pushed[i]);//模拟入栈
            if (num.back() == popped[j])
            {
                while (num.size() && num.back() == popped[j])//模拟连续出栈
                {
                    num.pop_back();
                    j++;
                }
            }
        }
        return !num.size();//如果符合，则栈为空，数量为0，否则栈不为空
    }
};

看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！