小工具知识网

当前位置: 首页 > 行业知识 > 剑指offer面试题31:栈的压入、弹出序列

行业知识

剑指offer面试题31:栈的压入、弹出序列

2026-11-18 13:31:34 来源:互联网转载

面试题31:栈的压入、弹出序列

题目:

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

()

示例1:

输入: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

示例2:

()
输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]输出:false解释:1 不能在 2 之前弹出。

思路:

这个题目我们可以模拟整个入栈和出栈的操作,我们按照建立一个栈,按照pushed序列压入栈,并且判断是否与popped序列的首元素是否相同,如果相同就把这个元素从栈内弹出,并观察下一个popped元素判断与现在的栈元素首元素是否相同,如果是则循环操作,直到遇到与栈首元素不同或者栈为空时退出循环,继续在外边接着上面pushed序列压入剩余元素,等遍历完所有pushed元素后,如果两个序列相互匹配的话就栈内为空,否则就不为空。

代码:

class Solution {public:    bool validateStackSequences(vector& pushed, vector& popped) {        stack st;        int n = pushed.size();        for(int i=0,j=0;i//循环遍历pushed元素            st.emplace(pushed[i]);//也可以用s1.push(pushed[i]);            while(!st.empty()&&st.top()==popped[j]){//判断popped元素与栈顶元素是否相同                st.pop();                j++;            }        }        return st.empty();    }};

上一篇:提升下载速度的解决方案

下一篇:软件服务器应该怎么选择?