前言

在准备考研复习专业课数据结构,所以我在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;
}