1. 题目描述

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

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

2. 思路分析

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

  1. 将入栈序列的元素依次入辅助栈
  2. 检查辅助栈顶元素和弹栈序列栈顶元素是否一致：
  • 元素一致，弹出辅助栈元素，弹栈序列指针后移
  • 不一致，回到第一步

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

3. 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * 获得栈顶元素
 * @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]))