张芷铭的个人博客

模拟栈操作判断出栈序列合法性：按序入栈，栈顶匹配则出栈，最终栈空则合法。

问题

自然数 1, 2, …, N 依次入栈，判断序列 C₁, C₂, …, Cₙ 是否为合法出栈序列。

人工判断法则

出栈序列中每个数字，在它后面的比它小的数字必须递减排列。

  • 2431 合法（4 后面的 3, 1 递减）
  • 4123 不合法（4 后面的 1, 2, 3 不递减）

算法思路

模拟栈操作：

  1. 按顺序将数据压入栈
  2. 若栈顶等于待判断序列首元素，则出栈
  3. 最终待判断序列为空则合法

Python 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

while True:
    N = int(input())
    if N == 0:
        break

    out_stack = list(map(int, input().split()))
    stack = []

    for i in range(1, len(out_stack) + 1):
        stack.append(i)
        while stack and stack[-1] == out_stack[0]:
            stack.pop()
            out_stack.pop(0)

    print("Yes" if not stack else "No")

Comments