A40954. stack or queue
填空题
困难
知识点
题目描述
stack or queue
题目描述
栈和队列都是常用的线性结构，它们都提供两个操作：
Push：加入一个元素。
Pop：弹出一个元素。
不同的是，栈是”先进后出”，而队列则是”先进先出”。
给出一个线性结构的进出顺序，判定这个结构是栈还是队列。
输入
第一行输入一个整数t，代表有t组测试数据 对于每组测试数据，第一行输入一个整数n，代表操作的次数。 随后输入n行，每行包含两个整数 type val。 当type = 1时，表示该次操作为push操作，val表示进入的数字。当type=2时，表示该次操作为pop操作，val代表出来的数字。 3<=n<=2000
输出
每组测试数据输出一行。 输出该组数据对应的线性结构，”Stack” 或者 “Queue”。 题目保证是栈或者队列的一种。
样例输入
2
6
1 1
1 2
1 3
2 3
2 2
2 1
4
1 1
1 2
2 1
2 2
样例输出
Stack
Queue
参考答案
#include<bits/stdc++.h>
using namespace std;
int main(){
#ifdef LOCAL
freopen("202209_6_1.in", "r", stdin);
#endif
stack<int> s;
queue<int> q;
bool bs = true;
bool bq = true;
int t;
scanf("%d", &t);
for(int i = 1; i <= t; i++){
int n;
scanf("%d", &n);
bs = true; //堆栈数据是否错误标志位
bq = true; //队列数据是否错误标志位
for(int j = 1; j <= n; j++){
int type, val;
scanf("%d%d", &type, &val);
if(type == 1){ //push
if(bs == true) s.push(val);
if(bq == true) q.push(val);
}else if (type == 2){ //pop
if(s.top() != val) bs = false; //读取并判断堆栈数据是否正确
if(q.front() != val) bq = false;//读取并判断队列数据是否正确
if(bs == true) s.pop();
if(bq == true) q.pop();
}
}
if(bs == true) printf("Stack\n");
if(bq == true) printf("Queue\n");
//清理堆栈和队列数据
while(!s.empty()) s.pop();
while(!q.empty()) q.pop();
}
return 0;
}
上一题
下一题