当前位置: 代码迷 >> 综合 >> PAT1051. Pop Sequence (25)(栈模拟)
  详细解决方案

PAT1051. Pop Sequence (25)(栈模拟)

热度:81   发布时间:2024-01-16 13:21:23.0
题意:

有个容量限制为m的栈,分别把1,2,3,…,n入栈,给出一个系列出栈顺序,问这些出栈顺序是否可能.

思路:

我的思路是将出栈顺序一个个入栈,如果当前栈顶等于此时入栈的元素说明正确,如果小于就继续入栈到该元素为止,如果小于说明出栈顺序有错,其中判断一下栈的元素个数是否大于m。过是过了但是感觉写的不太好,看了一下网上的代码思路比我的要清晰很多,所以还是记录一下,这个问题可以用来判断出栈顺序是否正确,感觉有点用。

我的代码:
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<string.h>
#include<sstream>
#include<functional>
#include<algorithm>
using namespace std;
const int INF = 0xfffff;
const int maxn = 1050;stack<int> s;
int num[maxn];int main() {int n, m, k;scanf("%d%d%d", &n, &m, &k);while (k--) {while (!s.empty())s.pop();int pos;for (int i = 1; i <= m; i++)scanf("%d", &num[i]);s.push(-1);//为了下面pop要先入栈-1for (pos = 1; pos <= num[1]; pos++) {s.push(pos);}bool flag = true;for (int i = 2; i <= m; i++) {if (s.size() > n+1) {flag = false;break;} s.pop();int top = s.top();//cout << top << " ";if (top == num[i])continue;else if (top > num[i]) {flag = false;break;} else {for (; pos <= num[i]; pos++) {s.push(pos);}}}if (flag)printf("YES\n");elseprintf("NO\n");}return 0;
}
网上的代码:
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<string.h>
#include<sstream>
#include<functional>
#include<algorithm>
using namespace std;
const int INF = 0xfffff;
const int maxn = 1050;stack<int> s;
int num[maxn];int main() {int n, m, k;scanf("%d%d%d", &n, &m, &k);while (k--) {while (!s.empty())s.pop();for (int i = 1; i <= m; i++)scanf("%d", &num[i]);int pos = 1;for (int i = 1; i <= m; i++) {s.push(i);if (s.size() > n) break;while (!s.empty() && s.top() == num[pos]) {s.pop();pos++;}}if (pos==m+1)printf("YES\n");elseprintf("NO\n");}return 0;
}


  相关解决方案