题意描述

给出一个入栈序列和一个出栈序列，判断出栈序列是否属于这个入栈序列的一个合法的出栈序列。合法输出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)
    • 并且只要存储这些数字，空间复杂度为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模拟栈，但我们需要开一个额外的变量记录动态数组的最后的那个位置。其余的思路还是和上面一样。

  • 代码如下

    • 需要进行一次遍历时间复杂度保持不变为O(n)
    • 需要堆这些数字进行存储，空间复杂度为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);
  }
  //先进行清空，反正后面不需要使用了
  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();
}
};