前言

在准备考研复习专业课数据结构，所以我在mooc平台上找了浙江大学的数据结构课程重新学习，感觉老师留的课后题都很有趣，所以想记录下自己的学习过程。

题目：

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

Sample Input:

1
2
3
4
5
6
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

Sample Output:

1
2
3
4
5
YES
NO
NO
YES
NO

按照惯例先秀一下AC的图

题解

题目大意

​ 限定堆栈的最大容量M，然后给出一个从1到N的序列按顺序依次入栈；我们可以随机的选择出栈的时刻。要求判断给出的K个出栈序列是否合法。（M,N,K都不超过1000）

​ 假如M=5,N=7，那么 1, 2, 3, 4, 5, 6, 7 这个出栈序列是合法的，而3, 2, 1, 7, 5, 6, 4 这个出栈序列则是非法的。因为当7出栈后，栈顶元素应该为6，但是此序列给出的下一个出栈元素为5，故此序列不合法。

题目分析

​ 我的思路是这样的，首先我将每一个出栈序列都按顺序保存下来，然后建立一个空堆栈，首先将堆栈里push一个0进去。于是我就可以拿栈顶的元素和保存下来的出栈序列作比较，从序列的第一个元素一直比较到第K个元素，每次比较有三种情况

①如果栈顶元素<出栈序列中的第i个元素，那么就将push（栈顶元素+2），若push失败，说明超出堆栈的范围，直接break，此序列不合法。

②栈顶元素=出栈序列中的第i个元素，那么就把栈顶元素pop出来，并且i=i+1

③栈顶元素>出栈序列中的第i个元素，说明序列不合法，直接break退出循环。

循环从1执行到N，循环结束，若没有①②这两种情况则说明，此出栈序列为合法的出栈序列。

完整代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<stdio.h>
#define MAXSIZE 1001
typedef struct SqStack{
    int size;
    int top;
    int data[MAXSIZE];
}SqStack;
bool push(SqStack &stack,int x){
    if(stack.top==stack.size -1){
        return false;
    }
    else{
        stack.data[++(stack.top)] = x;
    }
    return true;
}
int pop(SqStack &stack){
    if(stack.top == -1){
        return -1;
    }
    else
        return stack.data[(stack.top)--];
}
int main(){
    int m,n,k,j,count,list[k+1][n+1];
    bool result[k+1],temp;
    scanf("%d%d%d",&m,&n,&k);
    SqStack stack;
    stack.size = m+1;//因为一开始要push 0 进去所以多增加一个空间
    
    //初始化结果数组
    for(int i=1;i<=k;i++)
        result[i] = true;
    //读取出栈序列，保存在list中
    for(int i=1;i<=k;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&list[i][j]);
        }
    for(int i=1;i<=k;i++){
        stack.top = -1;
        push(stack,0);
        //判断该序列是否合法
        j=1;count=1;
        while(count<=n){
            if(stack.data[stack.top]<list[i][count]){
                temp = push(stack,j);
                j++;
                if(!temp){//堆栈已满，插入失败
                    result[i] = false;
                    break;
                }
            }
            if(stack.data[stack.top]==list[i][count]){
                pop(stack);
                count++;
            }
            if(stack.data[stack.top]>list[i][count]){
                result[i] = false;
                break;
            }
        }
    }
    //输出结果
    for(int i=1;i<k;i++){
        if(result[i])
            printf("YES\n");
        else
            printf("NO\n");
    }
    if(result[k]) printf("YES"); else printf("NO");
    return 0;
}