# PAT 1051 Pop Sequence (25分) 模拟入栈

### 题目

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.

Input Specification: 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.

Output Specification: For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

Sample Input:

```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```

Sample Output:

```YES
NO
NO
YES
NO```

### 解析

• 入栈顺序是确定的（`1-N`依次入栈），我们只需要模拟这个过程。
• 先把输入的序列接收进数组`seq[]`，设`index= 1`，表示当前比较的是序列哪个元素，然后按顺序`1~n`把数字进栈，每进入一个数字，判断有没有超过栈容量`m`，超过了就`break`
• 如果没超过，看看当前序列元素`seq[index]`是否与栈顶元素`s.top()`相等：`while`相等就一直弹出栈`s.pop()``index++`，相当于当前序列元素匹配成功，继续处理下一个；不相等就继续按顺序把数字压入栈。若能完美模拟，最终栈应该是空的，说明这个序列是可能的，输出`YES`

### 代码

```#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
// 栈容量m，序列长度n，k个序列
int m, n, k;
cin >> m >> n >> k;
while (k -- > 0) {
vector<int> seq(n + 1);
stack<int> s;
// 序列哪个位置元素
int index = 1;
// 输入这个序列
for (int j = 1; j <= n; ++j) cin >> seq[j];
// 模拟入栈过程（只能从1到n入栈）
for (int j = 1; j <= n; ++j) {
s.push(j);
// 栈中元素不能超过m个
if (s.size() > m) break;
// 如果当前栈顶元素和当前序列元素相等
while (!s.empty() && s.top() == seq[index]) {
// 出栈，相当于成功匹配这个元素
s.pop();
// 处理序列下一个元素
index++;
}
}
// 如果最终栈空，说明这个序列可以是正确的出栈序列
if (s.empty()) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}```

0 条评论

• ### PAT 1007 Maximum Subsequence Sum (25分) 最大连续子序列和

Given a sequence of K integers { N​1​​ , N​2​​ , ..., N​K​​ }. A continuous subs...

• ### PAT 1044 Shopping in Mars (25分) 二分法

Shopping in Mars is quite a different experience. The Mars people pay by chained...

• ### PAT 1037 Magic Coupon (25分) 贪心+排序+负负/正正得正

The magic shop in Mars is offering some magic coupons. Each coupon has an intege...

• ### HDU 5882 Balanced Game

Balanced Game Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/3276...

• ### Day21:栈的压入、弹出序列

借用一个辅助栈，遍历压栈顺序，先将第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1!=4，所以我们要继续压栈，直到相...

• ### 揭秘新科图灵奖得主Hinton、LeCun、Bengio的传奇人生

导读：2019年3月27日，ACM（国际计算机学会）宣布，三位“深度学习之父”约书亚·本吉奥(Yoshua Bengio)、杰弗里·辛顿(Geoffrey Hi...

• ### proc /sys/vm 终结版

本人最近会把proc目录详解给大家弄一下，欢迎翻译，有问题则留言。虽然是英文的，但都比较好理解，如有问题，请留言，我们共同为Linux社区而努力。我们翻译效果还...

• ### Go调试简单的内存泄漏

Memory leaks are a class of bugs where memory is not released even after it is n...

• ### 传滴滴与软银就进一步融资进行谈判，将用于自动驾驶业务

7月2日消息，有知情人士透露，滴滴正在与最大股东软银以及其他潜在投资者就自动驾驶业务融资进行谈判。目前谈判仍未结束，最终是否能达成协议尚未可知。

• ### 【DB笔试面试758】在Oracle的DG中，Switchover和Failover的区别有哪些？

一个DG环境中只有两种角色：Primary和Standby。所谓角色转换就是让数据库在这两种角色中切换，切换也分两种：Switchover和Failover，关...