栈的压入、弹出序列

题目描述

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

思路

借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是 1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是 4，很显然 1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

举例：

入栈 1,2,3,4,5

出栈 4,5,3,2,1

首先 1 入辅助栈，

此时辅助栈栈顶 1≠ 弹出序列 4，继续入栈 2

此时辅助栈栈顶 2≠ 弹出序列 4，继续入栈 3

此时辅助栈栈顶 3≠ 弹出序列 4，继续入栈 4

此时辅助栈栈顶 4 ＝弹出序列 4，辅助栈将 4 出栈，并且弹出序列向后移动一位，此时为 5,辅助栈里面是 1,2,3

此时辅助栈栈顶 3≠ 弹出序列 5，继续入栈 5

此时辅助栈栈顶 5=弹出序列 5，辅助栈将 5 出栈,并且弹出序列向后移动一位，此时为 3,辅助栈里面是 1,2,3

此时辅助栈栈顶 3=弹出序列 3，辅助栈将 3 出栈,并且弹出序列向后移动一位，此时为 2,辅助栈里面是 1,2,

….

依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。

代码

function IsPopOrder(pushV, popV) {
  let index = 0; // 用于标识弹出序列的位置
  let stack = []; // 辅助栈
  for (let i = 0; i < pushV.length; i++) {
    stack.push(pushV[i]);
    //如果栈不为空，且辅助栈栈顶元素等于弹出序列
    while (stack.length && stack[stack.length - 1] === popV[index]) {
      stack.pop(); // 出栈
      index++; // 弹出序列向后移动一位
    }
  }
  return stack.length == 0;
}