张芷铭的个人博客

问题描述

创建时间 2024-04-10 14:58

问题描述

已知自然数1，2，…，N（1<=N<=100）依次入栈，请问序列C1，C2，…，CN是否为合法的出栈序列。

注意：

  • 如何人工判断一个序列是否是可能的出栈序列？ 出栈序列中的每一个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。否则不合法。例如2431合法，4123不合法

解决思路：

模拟出栈来判断序列是否合法：创建一个空的栈，按顺序把数据压入栈，如果发现栈顶元素和带判断序列的第一个元素相同，说明应该出栈了。执行完后要是待判断序列空了，则说明是合法的。

答案

Python版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

while True:
    N = int(input())  # 读取N
    if N == 0:
        break  # 输入为0时，结束程序

    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)

    # 输出结果
    if not stack:
        print("Yes")
    else:
        print("No")

💬 评论