剑指offer31题-栈的压入弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 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 之前弹出。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

利用一个栈模拟压入弹出，当栈顶元素和弹出序列的值相同时，弹栈 并且弹出序列指针后移，最后判断弹出序列指针是否指向弹出序列最后。

class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int>s;//辅助栈 int indexPush=0;//压栈索引 int indexPop=0;//弹栈指针 while(indexPush!=pushed.size()) { s.push(pushed[indexPush]);//压入压栈序列值 indexPush++;//索引后移 while(!s.empty()&&s.top()==popped[indexPop])//如果遇到栈顶元素和弹出序列相同 循环弹栈 { s.pop(); indexPop++;//指针后移 } } return indexPop==popped.size();//判断指针是否遍历完成弹出序列 } };