题意描述

给出一个入栈序列和一个出栈序列，判断出栈序列是否属于这个入栈序列的一个合法的出栈序列。合法输出true，否则输出false.(题目保证入栈的序列中的每个数字都是不一样的）

思路分析

前置知识

首先，我们需要了解什么是栈和队列。

  • 学习过数据结构的同学应该都知道，栈是一个先进后出的数据结构，这个你可以理解为你把一本一本书放进一个箱子，你每次放的书一定是在最上面的，我们称之为栈顶。而每次我们取的时候，我们也只能从栈顶取。
  • 队列的原理是一个先进先出的数据结构。这个可以类比我们日常生活中的排队（当然，我们不允许插队的情况）。排在前面的人肯定优先处理相关的事情。一个队伍的前面我们称之为队首。
  • 另外，现在许多高级语言都不需要我们从头开始造轮子，C++就有封装好的相关的数据结构STL，不管是时间复杂度还是空间复杂度都是比较好的。

思路一

  • 我们可以利用一个栈和一个队列进行模拟求解。我们先将我们知道的出栈的数字按顺序存入一个队列里面，然后我们遍历入栈的数字，将这些数字放到一个栈里面，我们每次放一个数字进入栈，我们需要判断的是这个栈顶的数字和队首的数字是否相等，如果相等我们就需要将队首出队和栈顶出栈。直到其中一个为空或者不相等的情况。这个我们可以用一个while进行实现。

    while(!st.empty()&&!q.empty()&&st.top()==q.front()){
  st.pop();
  q.pop();
}

    先看代码，你会发现我将判断是否为空的放到前面，这是因为当我们判断这个while里面的条件的时候，如果将st.top()==q.front()放到前面的话，加入这个时候栈为空或者队列为空的话，那么就会出现类似于段错误，也就是越界了。这个是需要注意的小细节。

  • 接下来，给出一个简单的证明。其实我上面的思路就是在模拟题目的意思。我们现将出栈的数字放入一个队列里面，然后我们遍历入栈的数字，如果遇到相等的情况，那么说明这个时候就需要我们将这个数字出栈，反映到队列里面就是出队，在栈里面就是出栈。

  • 代码，时间复杂度为O(N)

    class Solution {
public:
  queue<int> q;
  stack<int> st;
  bool IsPopOrder(vector<int> pushV,vector<int> popV) {
      for(auto x:popV){
          q.push(x);
      }
      for(auto x:pushV){
          st.push(x);  //模拟入栈
          //判断是否满足出栈条件
          while(!st.empty()&&!q.empty()&&st.top()==q.front()){
              st.pop();
              q.pop();
          }
      }
      return !st.size();
  }
};

思路二

  • 我们发现，其实栈我们可以利用一个数组进行模拟的。但是由于题目并没有给出具体的数据范围，所以建议可以使用vector动态数组进行处理。那么这个题目不是已经为我们开好了一个vector数组吗？我们观察上面的代码，我们发现在利用完那个popV数组之后，我们后面基本就不需要对其进行操作了，所以为了实现再利用，我们可以用popV模拟栈，但我们需要开一个额外的变量记录动态数组的最后的那个位置。其余的思路还是和上面一样。

  • 代码 时间复杂度保持不变，但是空间复杂度得到了优化。

    class Solution {
public:
  queue<int> q;
  stack<int> st;
  bool IsPopOrder(vector<int> pushV,vector<int> popV) {
      for(auto x:popV){
          q.push(x);
      }
      popV.clear();  //先进行清空，反正后面不需要使用了
      int cnt=-1;  //开一个变量记录最后的位置
      for(auto x:pushV){
          popV.push_back(x);  //模拟入栈操作
          ++cnt;

          //判断是否可以出栈
          while(!popV.empty()&&!q.empty()&&popV[cnt]==q.front()){
              popV.pop_back();
              --cnt;
              q.pop();
          }
      }
      return !popV.size();
  }
};