PTA（栈和队列）2-6 出栈序列的合法性

zhangzhang2025-11-032025-11-03

2-6 出栈序列的合法性

分数 6

作者陈越

单位浙江大学

给定一个最大容量为 m 的堆栈，将 n 个数字按 1, 2, 3, …, n 的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 m=5、n=7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。

输入格式：

输入第一行给出 3 个不超过 1000 的正整数：m（堆栈最大容量）、n（入栈元素个数）、k（待检查的出栈序列个数）。最后 k 行，每行给出 n 个数字的出栈序列。所有同行数字以空格间隔。

输出格式：

对每一行出栈序列，如果其的确是有可能得到的合法序列，就在一行中输出YES，否则输出NO。

输入样例：

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

输出样例：

YES
NO
NO
YES
NO

我的卡壳代码

#include <iostream>
#include <stack>

using namespace std;

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    while (k--) { // 会执行k个序列
        stack<int> stack;
        bool hasOut[n+1]; // 用于记录是否出栈
        for (int i = 0; i <= n; ++i) {
            hasOut[i] = false;
        }
        while (n--) { // 入栈n个元素
            int num;
            cin >> num; // 获取当前数字，则说明小于它的且还没入过栈的得先压入栈
            while (num > 0 && hasOut[num]) {
                int i =
            }
        }
    }
}

思路方向是对的（通过记录元素是否出栈、控制入栈顺序来验证），但具体实现时陷入了细节误区，导致逻辑卡住。问题的核心在于：不需要记录 “是否出栈”，而是通过模拟 “入栈→对比出栈元素→出栈” 的完整过程，同时检查栈的容量是否超限。

为什么我的思路容易混乱？

hasOut 数组其实是多余的：因为入栈顺序是固定的（1→2→…→n），出栈序列的合法性只取决于 “入栈和出栈的时机”，不需要额外记录是否出栈。
内层循环逻辑不清晰：遇到当前出栈元素 num 时，正确的做法是 “把所有比 num 小且未入栈的元素先入栈”，再判断栈顶是否等于 num 并出栈。

正确思路（模拟栈操作）

初始化：准备一个栈，以及一个指针 current 记录 “下一个要入栈的元素”（从 1 开始）。
遍历出栈序列：对每个待检查的序列，逐个处理元素num：
- 先把所有 小于等于 num 且未入栈 的元素入栈（即 current 到 num 之间的元素）。
- 入栈过程中如果栈的大小超过 m，说明序列不合法。
- 入栈完成后，若栈顶元素等于 num，则出栈；否则序列不合法。
最终判断：如果所有元素都能按上述规则处理完，则序列合法（输出 YES），否则不合法（输出 NO）。

正确代码

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    while (k--) { // 会执行k个序列
        vector<int> seq(n);
        for (int i = 0; i < n; ++i) { // 存储当前要检查的出栈序列
            cin >> seq[i];
        }
        stack<int> stack;
        int current = 1; // 下一个入栈元素
        bool valid = true;

        for (int i = 0; i < n; ++i) { // 遍历出栈序列中的每个元素
            int num = seq[i];
            // 把小于等于num的且还没入栈的先入栈（还没入栈用current看）
            while (current <= num) {
                stack.push(current);
                current++;
                // 检查是否栈满
                if (stack.size() > m) {
                    valid = false;
                    break;
                }
            }
            if (!valid) { // 栈溢出直接退出
                break;
            }
            // 开始出栈，匹配题目给的出栈顺序是否正确
            if (stack.top() == num) {
                stack.pop();
            } else { // 栈顶不匹配，退出
                valid = false;
                break;
            }
        }
        if (valid) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

关键逻辑解析

入栈控制：比如当前出栈元素是 3，则必须先把 1、2、3 依次入栈（因为入栈顺序固定），才能让 3 出栈。
容量检查：入栈时如果栈的大小超过 m（比如 m=5，但需要入栈 6 个元素才能匹配出栈序列），则直接判定为非法。
栈顶匹配：入栈后栈顶必须等于当前出栈元素，否则说明出栈顺序违反了栈的 “后进先出” 规则（比如出栈序列是 3、1，入栈 1、2、3 后栈顶是 3，出栈后栈顶是 2，无法匹配 1，故非法）。