一、题目描述

JZ21 栈的压入、弹出序列
题目大意：给出两个序列, 一个是元素入栈的序列, 一个是元素出栈的序列, 判断按照第一个序列入栈是否可以得到给定的第二个出栈序列
注意审题：这两个序列的长度是相等的, 因此不用考虑长度不相等的情况, 并且题目假设压入的所有数字都不同

二、算法（栈模拟、双指针）

解题思路

1. 首先栈的弹出序列是指在插入元素的途中我们可以弹出若干元素, 直到栈空为止, 因此一个压入序列可以对应多个弹出序列

2. 根据题意, 我们可以用栈来模拟整个过程, 同时用两个指针i, j分别指向两个序列的头部, 每次我们先将i所指向的元素压入栈中, 然后i向后移动一步, 之后再检查当前栈顶, 若对应上了弹出序列中j所指向的元素, 则弹出元素, j向后移动, 再继续检查, 直到栈空或栈顶元素和j所指元素不等为止

3. 若压入完所有的元素后指针j不等于序列长度或栈不为空, 说明不能成功对应弹出序列, 返回false, 否则返回true
   

   代码实现 (C++11)

   class Solution {
   public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        int n = pushV.size();
        stack<int> stk;    // 使用STL中的栈容器
        int i = 0, j = 0;
        while(i < n){
            stk.push(pushV[i]);    // 首先将pushV[i]入栈
            while(!stk.empty() && stk.top() == popV[j]){    // 不断检查栈顶
                ++j;
                stk.pop();
                }
            ++i;
            }
   
        return j == n;    // 判断能否成功对应
    }
   };

时间复杂度：O(n), n为序列的长度
空间复杂度：O(n), 栈空间的消耗最坏是O(n)