栈的压入弹出序列

1. 题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如序列 1、2、3、4、5 是某栈的压栈序列，序列 4、5、3、2、1 是该压栈序列对应的一个弹出序列，但 4、3、5、1、2 就不可能是该压栈序列的弹出序列。

2. 思路分析

栈的题目还是借助“辅助栈”。大体思路如下：

将入栈序列的元素依次入辅助栈
检查辅助栈顶元素和弹栈序列栈顶元素是否一致：

元素一致，弹出辅助栈元素，弹栈序列指针后移
不一致，回到第一步

需要注意的是，过程中的边界条件检查（多试试几种情况）。除此之外，由于 js 不提供指针运算，所以用标记下标的方法代替指针。

3. 代码实现

/**
 * 获得栈顶元素
 * @param {Array} stack
 */
function getStackTop(stack) {
  if (!Array.isArray(stack)) {
    return null;
  }

  if (!stack.length) {
    return null;
  }

  return stack[stack.length - 1];
}

/**
 * 第二个参数是否是该栈的弹出顺序
 * @param {Array} pushOrder
 * @param {Array} popOrder
 * @return {Boolean}
 */
function check(pushOrder, popOrder) {
  if (
    !pushOrder.length ||
    !popOrder.length ||
    pushOrder.length !== popOrder.length
  ) {
    return false;
  }

  const stack = []; // 辅助栈
  let i = 0,
    j = 0; // i: 压入序列指针; j: 弹出序列指针

  while (j < popOrder.length) {
    for (; i < pushOrder.length && popOrder[j] !== getStackTop(stack); ++i) {
      stack.push(pushOrder[i]);
    }

    if (popOrder[j] !== getStackTop(stack)) {
      return false;
    }

    stack.pop();
    ++j;
  }

  return true;
}

/**
 * 以下是测试代码
 */

console.log(check([1, 2, 3, 4], [4, 3, 2, 1]));

console.log(check([1, 2, 3, 4, 5], [4, 5, 3, 2, 1]));

console.log(check([1, 2, 3, 4, 5], [4, 3, 5, 1, 2]));

大师兄

1. 题目描述

2. 思路分析

3. 代码实现