给定一个入栈序列A和另外一个序列B，判断这个序列B是不是这个入栈序列A的出栈序列

这个问题有个名字叫做“栈混洗”，经典的不合法出栈序列是那个1，3，2出栈序列，详情请看学堂在线-数据结构（上）

不过这里记录的是从编码的角度去解决栈混洗问题，题目链接：剑指offer31

入栈序列是pushed，待判断的序列是popped，算法思想就是用一个辅助栈s，同时用一个变量pop_i记录出栈序列中的当前元素；遍历pushed数组，然后对于每一次入栈操作，都循环判断一次入栈的元素是不是出栈序列中的当前元素，如果是就从s中弹出该元素，并且pop_i++；遍历pushed完成后，判断s是否为空，若为空则说明popped序列是合法的出栈序列

AC代码：

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int pop_i=0;
        int len=pushed.size();
        for(int i=0;i<len;i++){
            s.push(pushed[i]);
            while(!s.empty()&&s.top()==popped[pop_i]){
                s.pop();
                pop_i++;
            }
        }
        return s.empty();
    }
};

最后

以上就是老实月饼为你收集整理的给定一个入栈序列A和另外一个序列B，判断这个序列B是不是这个入栈序列A的出栈序列的全部内容，希望文章能够帮你解决给定一个入栈序列A和另外一个序列B，判断这个序列B是不是这个入栈序列A的出栈序列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。