PAT-Advanced Stack

Abstract：栈相关

1051 Pop Sequence (25分)

解法一：std::stack

直接用栈来模拟，不断推入序列，当遇到pop序列和栈顶相等时，不断地pop直到为空或不等，最后再将栈内元素逐个弹出对比是否正确

#include<iostream>
#include<vector>
#include<stack>

bool checkSeq(int cap, std::vector<int>& seq) {
	std::stack<int> stack;
	int idx = 0;
	for (int i = 0; i < seq.size(); i++) {
		stack.push(i + 1);
		while (!stack.empty() && stack.top() == seq[idx]) {
			stack.pop();
			idx++;
		}
		if (stack.size() >= cap)
			return false;
	}

	while (!stack.empty()) {
		if (stack.top() != seq[idx++])
			return false;
		stack.pop();
	}

	return true;
}

int main() {
	std::vector<int> seq;
	int m, n, k;
	std::cin >> m >> n >> k;
	seq = std::vector<int>(n);
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < n; j++)
			std::cin >> seq[j];
		if (checkSeq(m, seq))
			std::cout << "YES" << std::endl;
		else
			std::cout << "NO" << std::endl;
	}
}