pta_02_线性结构4_Pop_Sequence

题目内容

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.

给定一个最多可以保存M个数字的堆栈。按1、2、3、…的顺序按N个数字， N和随机弹出。您应该知道给定的数字序列是否可能是堆栈的弹出序列。例如，如果M是5,N是7，我们可以从堆栈中得到1,2,3,4,5,6,7，而不是3,2,1,7,5,6,4。

输入样式

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.

每个输入文件包含一个测试用例。对于每种情况，第一行包含3个数字(都不超过1000):M(堆栈的最大容量)、N (push序列的长度)和K(要检查的pop序列的数量)。然后接着K行，每一行包含一个由N个数字组成的弹出序列。一行中的所有数字用一个空格隔开。

输出样式

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

对于每个弹出序列，如果它确实是一个可能的堆栈弹出序列，则打印一行“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

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

输出结果

YES
NO
NO
YES
NO

题目分析

本体主要在于模拟栈的进栈与出栈的过程。

代码分析

准备阶段

#include<stdio.h>
#include<iostream>

using namespace std;

constexpr auto MAXSIZE = 1000;;

struct Snode {
	int top;
	int data[MAXSIZE];
	int capacity;
};
typedef Snode* stack;
int ispopstack(int arr[], int m, int n);

主函数

int main()
{
	int m, n, k;
	cin >> m >> n >> k;//输入，M，N，K
	int arr[1000];
	string add[1000];
	int flag = 0;
	for (int i = 0; i < k; i++)
	{
		flag++;
		for (int j = 0; j < n; j++)
		{
			cin >> arr[j];//读取需要判断的堆栈元素的值
		}
		if (ispopstack(arr, m, n))//根据模拟堆栈的函数的返回值，判断输入的是否是堆栈的元素
		{
			cout << "YES" << endl;
			add[flag] = "YES";
		}
		else
		{
			cout << "NO" << endl;
			add[flag] = "NO";
		}
		
	}
	for (int i = 1; i <= flag; i++)//循环将判别结果打印处理啊
	{
		cout << add[i] << endl;
	}
	return 0;
}

堆栈的判别函数

int ispopstack(int arr[], int m, int n)//输入的是待检验元素arr,堆栈最大容量m,序列的宽度n
{
	int count = 0;//计数器
	stack link = (stack)malloc(sizeof(struct Snode));//分配一个内存空间
	link->capacity = m;
	link->top = -1;//模拟栈顶指针
	for (int i = 1; i <= n; i++)
	{
		if (link->capacity == link->top + 1)
			return 0;//当栈顶指针与堆栈最大的容量相差为1的时候，则不是堆栈
		else
			link->data[++link->top] = i;//入栈，1，2，3，4，5，6，7
		while (link->data[link->top] == arr[count])
		{
			link->top--;
			count++;
		}
	}
	if (count == n)
		return 1;
	else
		return 0;

}

结果

nk->top] == arr[count])
{
link->top–;
count++;
}
}
if (count == n)
return 1;
else
return 0;

}