栈的压入、弹出序列

剑指offer的一道经典题目，难度中等。

描述

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

示例1

输入：

[1,2,3,4,5],[4,5,3,2,1]

返回值：

true

说明：

可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true

示例2

输入：

[1,2,3,4,5],[4,3,5,1,2]

返回值：

false

说明：

由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

方法一：辅助栈

知识点：栈

栈是一种仅支持在表尾进行插入和删除操作的线性表，这一端被称为栈顶，另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；元素出栈指的是从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

思路：

题目要我们判断两个序列是否符合入栈出栈的次序，我们就可以用一个栈来模拟。对于入栈序列，只要栈为空，序列肯定要依次入栈。那什么时候出来呢？自然是遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来。

//入栈：栈为空或者栈顶不等于出栈数组

while(j < n && (s.isEmpty() || s.peek() != popA[i])){

s.push(pushA[j]);

j++;

}

如果能按照这个次序将两个序列都访问完，那说明是可以匹配入栈出栈次序的。

具体做法：

第一步：准备一个辅助栈，两个下标分别访问两个序列。
第二步：辅助栈为空或者栈顶不等于出栈数组当前元素，就持续将入栈数组加入栈中。
第三步：栈顶等于出栈数组当前元素就出栈。
第四步：当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个序列都访问完就是匹配的。

Java实现代码：

import java.util.Stack;
public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {int n = pushA.length;//辅助栈Stack<Integer> s = new Stack<>();//遍历入栈的下标int j = 0;//遍历出栈的数组for(int i = 0; i < n; i++){//入栈：栈为空或者栈顶不等于出栈数组while(j < n && (s.isEmpty() || s.peek() != popA[i])){s.push(pushA[j]);j++;}//栈顶等于出栈数组if(s.peek() == popA[i])s.pop();//不匹配序列elsereturn false;}return true;}
}

复杂度分析：

时间复杂度：O(n)，其中nn为数组长度，最坏情况下需要遍历两个数组各一次
空间复杂度：O(n)，辅助栈空间最大为一个数组的长度

方法二：原地栈

思路：

方法一我们使用了一个辅助栈来模拟，但是数组本来就很类似栈啊，用下标表示栈顶。在方法一种push数组前半部分入栈了，就没用了，这部分空间我们就可以用来当成栈。原理还是同方法一一样，只是这时我们遍历push数组的时候，用下标n表示栈空间，n的位置就是栈顶元素。

具体做法：

第一步：用下标n表示栈空间，用j表示出栈序列的下标。
第二步：遍历每一个待入栈的元素，加入栈顶，即push数组中n的位置，同时增加栈空间的大小，即n的大小。
第三步：当栈不为空即栈顶n大于等于0，且栈顶等于当前出栈序列，就出栈，同时缩小栈的空间，即减小n。
第四步：最后若是栈空间大小n为0，代表全部出栈完成，否则不匹配。

Java实现代码：

public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {//表示栈空间的大小，初始化为0int n = 0;//出栈序列的下标int j = 0;//对于每个待入栈的元素for(int num : pushA){//加入栈顶pushA[n] = num;//当栈不为空且栈顶等于当前出栈序列while(n >= 0 && pushA[n] == popA[j]){//出栈，缩小栈空间j++;n--;}n++;}//最后的栈是否为空return n == 0;}
}

复杂度分析：