出栈序列的合法性

7-5 出栈序列的合法性

给定一个最大容量为 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
1
2
3
4
5
6

输出样例：

YES
NO
NO
YES
NO
1
2
3
4
5

思路：

总体：你看那个栈如果要出栈的话顺序是7 6 5 4 3 2 1吧；然后给你一个串，要求这个串是7654321里面出来的，那有三种可能

1.要是要进的数和这个串的数一样就是进栈接着出栈这种直接判断下一个

2.要是栈顶的数和这个串的数相等的话就说明找到这个数了出栈！然后把那个串判断下一个，栈也弹出这个，来判断判断是不是还相等要是都弹完了栈也没用完这就说明符合规则

3.要是不相等呢就把x这个数入栈判断x下一个数就完事儿了，要是栈用完了或者栈弹完了就break

最后判断要是栈里面还有数或者栈用超了就说明不符合规则；

这就是一个动态入栈出栈的问题。掌握思路后很简单；

代码加注解：

#include 
#include 
#include 
#include 
using namespace std;

void test01()
{
    char s[100];
    int N, M, K;
    cin >> M >> N >> K;

    while (K--)
    {
        stack<int> num;
        int a[N];
        for (int i = 0; i < N; i++)
        {
            cin >> a[i];
        }
        int x = 1, y = 0;
        while (1)
        {
            if (x == a[y]) //如果x和a[y]相同的话就说明是先入栈后直接出栈的
            {
                x++;
                y++; //直接下一个不用管
            }
            else if (!num.empty() && a[y] == num.top()) //如果栈不为空并且栈顶元素等于a[y],说明找到出栈前的极大值了，可以出栈然后看看下一个是否相等相等就继续向里面压
            {
                num.pop();
                y++; //去找下一个序列看看有没有
            }
            else
            {
                if (y > N - 1)
                    break; //如果待察序列到头了，就不玩了
                num.push(x);
                x++;                 //不然就把下一个数压进栈看看有没有
                if (num.size() >= M) //如果栈不够装了也不玩了
                    break;
            }
        }
        if (!num.empty() || num.size() >= M)
        {
            cout << "NO" << endl;
        }
        else
        {
            cout << "YES" << endl;
        }
    }
}
int main()
{
    test01();
    system("pause");
}

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
57
58
59