浙大陈越老师数据结构 02-线性结构4 Pop Sequence详解

        最开始的话想用一种方法找出出栈的顺序之间的内在逻辑

        因为输入的数据是按顺序的1~n，根据自己的模拟我成功得出了该结论：

                后弹出的数据应满足以下多种情况中的一种:

                 1.比已弹出的所有值的最小值小

                 2.比已弹出的所有值的最大值大

                 3.插入后在同一区间内递减

                 又因为对栈的大小有具体限制，不难得出

                        s[k] - k - 1 >= a\a为堆栈容量

                最后上代码

#include 
using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int s[b];
	for (int i = 0; i < c; i++) {
		int min = 100000, max = -100000, prior = 100000;
		bool insert = false, can = true;
		for (int k = 0; k < b; k++) {
			cin >> s[k];
			if (s[k] - k - 1 >= a)
				can = false;
			if (s[k] > max)
				max = s[k];
			else if (s[k] < min)
				min = s[k];
			else if (s[k] < max && s[k] > min) {
				if (s[k] < prior) {
					prior = s[k];
				} else {
					can = false;
				}
			}
		}
		if (can) {
			printf("YESn");
		} else {
			printf("NOn");
		}
	}
}

果不其然，最后寄了。被姥姥预判了我的预判

最后自己写了一个堆栈来进行模拟：
具体思路就是按1~n顺序逐渐入栈，当栈顶的值为s[k]（给出的第k个输出值）时输出，总之就是说模拟一下捏

ps：这里仅为了提高对栈的理解而手写了一个类，完全可以用相关库替代

上代码！！！！！！！！！！！！！！！！！！！

#include 
using namespace std;

class stack {
	public:
		int *love;
		int capacity;
		int top;
		stack(int a) {
			capacity = a;
			top = 0;
			love = (int *)malloc(sizeof(int) * a);
		}
		bool empty() {
			return (top == capacity);
		}
		bool pop(int a) {
			if (!empty()) {
				love[top++] = a;
			}
			return empty();
		}
		int push() {
			return love[--top];
		}
		int show_top() {
			return love[top - 1];
		}
};

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	for (int i = 0; i < c; i++) {
		bool success = true;
		int s[b], sum = 0;
		stack kdot(a);
		for (int k = 0; k < b; k++) {
			cin >> s[k];
		}
		for (int j = 0; j < b; j++) {
			if (kdot.empty()) {
				break;
			}
			kdot.pop(j + 1);
			while (kdot.love[kdot.top - 1] && kdot.show_top() == s[sum]) {
				kdot.push();
				sum++;
			}
		}
		if (sum  == b) {
			printf("YESn");
		} else {
			printf("NOn");
		}
	}
}