TypeScript栈的压入与弹出序列校验

2024-04-02 19:04:59 333人浏览泡泡鱼

摘要

目录前言思路分析弹出序列满足条件弹出序列不满足条件实现代码前言有两个整数序列，第一个序列表示栈的压入顺序，判断第二个序列是否为该栈的弹出顺序。假设压入栈的数字均不相等。例如，序列[

前言

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

思路分析

仔细分析题目后，我们很直观的想法就是构造一个辅助栈，把压入序列中的数字依次压入该辅助栈。按照弹出序列的顺序依次从该栈中弹出数字，如果辅助栈被清空则代表此序列是它的一个弹出序列，否则就不可能是一个弹出序列。

弹出序列满足条件

如下图所示，它的压入过程为：

取出弹出序列的第1个元素，维护一个已取索引，在压入序列中从已取索引位置开始寻找与之相等的元素，将它之前的数字和其本身依次入栈，每取1个元素就将索引自增1次

此时，栈顶元素与弹出序列的第1个元素相等，将栈顶元素出栈。

取出弹出序列的第2个元素，在压入序列中从已取索引位置开始寻找与之相等的元素，将它之前的数字和其本身依次入栈。

此时，栈顶元素与弹出序列的第2个元素相等，将栈顶元素出栈。

取出弹出序列的第3个元素，此时，压入序列的元素已经被取完。我们继续判断 辅助栈中的元素是否与弹出序列的元素相等。

栈顶元素为3，要弹出的元素也是3，二者相等，栈顶元素出栈

取出弹出序列的第4个元素

栈顶元素为2，要弹出的元素也是2，二者相等，栈顶元素出栈

取出弹出序列的第5个元素

栈顶元素为1，要弹出的元素也是1，二者相等，栈顶元素出栈

弹出序列已取完，辅助栈已清空。 该弹出序列属于压入序列的一个弹出顺序

弹出序列不满足条件

接下来，我们来分析下它不是压入序列的弹出顺序的情况，它的压入过程与满足条件时一样，唯独不同的是，弹出序列的第3个元素从辅助栈出栈后，压入序列已经被取完。此时，弹出序列的第4个元素是1，辅助栈的栈顶元素是2，二者不等，那么该序列肯定不是压入序列的弹出顺序。

实现代码

经过上面的分析，我们已经知道了如何解决这个问题。思路已明确，接下来，我们就可以愉快的进入编码环节了?

export function StackPushAndPopSequence(
  pushSequence: Array<number>,
  popupSequence: Array<number>
): boolean {
  if (pushSequence.length === 0 || popupSequence.length === 0) return false;
  // 下一个入栈、出栈索引
  let nextPushIndex = 0;
  let nextPopIndex = 0;
  // 辅助栈
  const stackData = new Stack();
  // 下一个弹出序列存在则执行进一步的判断
  while (nextPopIndex < popupSequence.length) {
    // 下一个弹出序列的元素与栈顶元素不等则入栈
    while (
      nextPushIndex < pushSequence.length &&
      popupSequence[nextPopIndex] !== stackData.peek()
    ) {
      stackData.push(pushSequence[nextPushIndex]);
      nextPushIndex++;
    }
    // 栈顶元素与下一个弹出序列元素相等则出栈
    if (stackData.peek() === popupSequence[nextPopIndex]) {
      stackData.pop();
      nextPopIndex++;
    } else {
      // 元素不等则终止循环，此时压入序列已经全部压入辅助栈，该序列不可能是一个弹出序列
      break;
    }
    // 辅助栈清空，则代表弹出序列是正确的
    if (stackData.isEmpty()) {
      return true;
    }
  }
  return false;
}

最后，我们将开头列举的例子来验证下上述代码是否正确执行，如下所示：

const pushSuite = [1, 2, 3, 4, 5];
const popSuite1 = [4, 5, 3, 2, 1];
const popSuite2 = [4, 3, 5, 1, 2];
const result1 = StackPushAndPopSequence(pushSuite, popSuite1);
const result2 = StackPushAndPopSequence(pushSuite, popSuite2);
console.log(result1, result2);