1. 题目
剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode）
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
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 之前弹出。
3. 分析
（1）需要模拟入栈和出栈的场景，如果能够模拟成功，则输入序列OK，否则错误
（2）执行过程。先入栈push中的数据，不需要入栈pop中的数据，再把pop数组中的元素依次和栈里面的数据进行比较，如果相等，那么pop数组往后移动，不断出栈里面的数据。直到栈和pop数组中的值不相等或栈为空截止。
（3）判断结果。如果pop数组走完了就是匹配的，否则不匹配。
4. 代码实现
1. class Solution { 2. public: 3. bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { 4. 5. //定义一个栈 6. stack<int> st; 7. int i = 0; 8. int j = 0; 9. 10. //执行过程 11. //pushed数组每入栈一个元素，都要判断一下popped数组第一个元素是否和入栈的栈顶元素相等 12. while(i<pushed.size()) 13. { 14. //入栈一个pushed数组元素 15. st.push(pushed[i]); 16. i++; 17. 18. //如果栈顶元素和popped数组第一个元素相等，那么就弹出栈顶元素，并继续比较，还相等的话，继续弹出栈顶元素和popped下一个元素进行比较 19. //直到栈为空或栈顶元素和popped第一个元素不相等 20. while((!st.empty()) && (st.top() == popped[j])) 21. { 22. st.pop(); 23. j++; 24. } 25. } 26. 27. //判断结果：popped数组是否走完 28. return j == popped.size(); 29. } 30. };
