2020-06-07(实时记录)验证栈序列

题目

给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。

输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出:true
解释:我们可以按以下顺序执行:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/validate-stack-sequences

思路:

在进栈顺序如题时,如果是正确的序列出栈,假设出去一个就去掉一个,
如4-5-3-2-1,因为是可行的出栈方式,那么poped中的元素都可以被去掉
如4-5-2-3-1,因为2的顺序错误,4可以出栈,5可以栈,那么2始终出去不了
观察上面执行顺序,可以发现,push和pop的对应数字为镜像,在push中最后一个进的,在pop中就第一个出

所以如果用一个栈和队列分别存储pushed和popped中的元素
栈顶元素一旦和队头元素相同,就在两个结构中同时pop该元素,
直到栈为空,即都能顺利出栈,返回true,否则返回false
具体代码如下

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        std::stack<int> s;
        std::queue<int> q;
        int i;
        for(i=0;i<pushed.size();i++)
        {
            q.push(popped[i]);
        }
        for(i=0;i<pushed.size();i++)
        {
            s.push(pushed[i]);
            while(!s.empty() && s.top() == q.front())
            {
                s.pop();
                q.pop();
            }
        }
        if(!s.empty())
        {
            return false;
        }else
        {
            return true;
        }
        
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。