判断出栈序列

题目信息输入输出测试样例 解答

题目信息

判断：指定的序列能否仅由 入栈 和 出栈 操作得到。

输入

有若干组数据输入 每组数据中，第一行为两个个整数 n 和 m。n 表示需要依次从 1~n 入栈，m 表示这组数据有 m 个出栈序列需要判断，当 n=0 且 m=0 时停止。 接下来有行，每行表示一个出栈序列

输出

对每一个出栈序列，如果能正常出栈，则输出 Yes，否则输出 No。

测试样例

测试样例1

5 2 1 2 3 4 5 5 4 1 2 3 6 2 6 5 4 3 2 1 3 2 5 6 4 1 0 0 Yes No Yes Yes

测试样例2

5 2 1 2 3 4 5 5 4 1 2 3 6 1 6 5 4 3 2 1 0 0 Yes No Yes

解答

#include <cstring> #include <iostream> #include <vector> #include <stack> using namespace std; bool IsPopOrder(const vector<int>& Push, const vector<int>& Pop) {//判断是否为出栈序列 if (Push.size() != Pop.size()) {//如果两个大小都不一样肯定不可能一样 return false; } //123456 //325641 stack<int> temp; int PushIndex = 0;//这个用来遍历原栈 int PopIndex = 0;//这个用来遍历后来的栈 int Size = Pop.size();//6 while (PopIndex < Size) {//相当于在后来的栈中一个一个在原栈中去对应 for (; PushIndex < Size; PushIndex++) {//这个for循环是用来寻找到原栈中和现在栈中相等的元素 if (Push[PushIndex] == Pop[PopIndex]) { PopIndex++; PushIndex++; break; } temp.push(Push[PushIndex]);//如果没有找到的话就先把原栈存储到temp栈中,用来模拟出入栈这个过程 }//如果这个循环结束了表明要么没有找到相同的,把所有该存入的值都存好了,要么就是找到相同的值跳出来 if (!temp.empty() && temp.top() != Pop[PopIndex]) {//如果temp不是空的,且其顶端存储的值不等于后来刚刚存进去的这个值 for (; PushIndex < Size; PushIndex++) { if (Push[PushIndex] == Pop[PopIndex]) { PopIndex++; PushIndex++; break; } temp.push(Push[PushIndex]); } } else if (!temp.empty()) {//如果下一个值相同的话则弹出temp中顶端的值,同时可以读下一个后来的栈的值了 temp.pop(); PopIndex++; } if (!temp.empty() && PushIndex >= Size && temp.top() != Pop[PopIndex]) {//如果此时之前的栈已经被遍历结束 且 temp中剩余的那个不等于后来的那个值 且temp剩余东西了 return false; } else { while (!temp.empty() && temp.top() == Pop[PopIndex]) {//不断倒着弹出相同的值 temp.pop(); PopIndex++; } } } if (temp.empty() && PushIndex >= Size) {//用来模拟的temp全部清空了,且原栈的遍历已经结束即成功的匹配上了 return true; } return false; } int main() { //freopen("E://test.txt", "r", stdin); int op = 1; while (op++) { int n, m; cin >> n >> m; if (n == 0 && m == 0) { return 0; } if (op > 2) { cout << endl; } vector<int> push; for (int i = 1; i <= n; i++) { push.push_back(i); } for (int i = 0; i < m; i++) {//每一个每一个判断 vector<int> pop; for (int j = 0; j < n; j++) { int tmp; cin >> tmp; pop.push_back(tmp); } if (IsPopOrder(push, pop)) { cout << "Yes" << endl; } else { cout << "No" << endl; } } } }