Coin163

首页 > UVA 11995 - I Can Guess the Data Structure! (数据结构) STL的应用

UVA 11995 - I Can Guess the Data Structure! (数据结构) STL的应用

相关标签: stl structure 数据结构

2020腾讯云10周年活动,优惠非常大!(领取2860元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1040

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
入口地址https://www.aliyun.com/minisite/goods

原题:

Problem I I Can Guess the Data Structure! There is a bag-like data structure, supporting two operations: 1 x Throw an element x into the bag. 2 Take out an element from the bag. Given a sequence of operations with return values, you're going to guess the data structure. It is a stack (Last-In, First-Out), a queue (First-In, First-Out), a priority-queue (Always take out larger elements first) or something else that you can hardly imagine! Input There are several test cases. Each test case begins with a line containing a single integer n (1<=n<=1000). Each of the next n lines is either a type-1 command, or an integer 2 followed by an integer x. That means after executing a type-2 command, we get an element x without error. The value of x is always a positive integer not larger than 100. The input is terminated by end-of-file (EOF). The size of input file does not exceed 1MB. Output For each test case, output one of the following: stack It's definitely a stack. queue It's definitely a queue. priority queue It's definitely a priority queue. impossible It can't be a stack, a queue or a priority queue. not sure It can be more than one of the three data structures mentioned above. Sample Input 61 11 21 32 12 22 361 11 21 32 32 22 121 12 241 21 12 12 271 21 51 11 32 51 42 4 Output for the Sample Input queuenot sureimpossiblestackpriority queue

/***

刚开始学用STL。 很方便。

不过还是再犹豫,该不该常用。。*/#include <cstdio>#include <cstring>#include <cmath>#include <stack>#include <string>#include <queue>#include <algorithm>#define INF 0x7fffffffusing namespace std;stack<int> filo;queue<int> fifo;priority_queue<int> pri;int main(){

int n, i;

while(scanf("%d", &n) != EOF ) {

while(filo.empty() == false) filo.pop();

while(fifo.empty() == false) fifo.pop();

while(pri.empty() == false) pri.pop();

int type, num, isStack = 1, isQueue = 1, isPriority = 1;

i = 0;

while(n --) {

int curNum;

scanf("%d%d", &type, &num);

if(type == 1){

fifo.push(num);

filo.push(num);

pri.push(num);

} else {

if(isStack) {

if(filo.empty()) {isStack = 0; }

else {

curNum = filo.top();

filo.pop();

if(curNum != num) {isStack = 0; }

}

}

if(isQueue) {

if(fifo.empty()) { isQueue = 0; }

else {

curNum = fifo.front();

fifo.pop();

if(curNum != num) {isQueue = 0; }

}

}

if(isPriority) {

if(pri.empty()) { isPriority = 0; }

else {

curNum = pri.top();

pri.pop();

if(curNum != num) { isPriority = 0; }

}

}

}

}

if(isStack && !isQueue && !isPriority) printf("stack\n");

else if(isQueue && !isStack && !isPriority) printf("queue\n");

else if(isPriority && !isStack && !isQueue) printf("priority queue\n");

else if(!isStack && !isQueue && !isPriority) printf("impossible\n");

else printf("not sure\n");

}

return 0;}

原文

原题:     Problem I I Can Guess the Data Structure! There is a bag-like data structure, supporting two operations: 1 x Throw an element x into the bag. 2 Take out an element from

------分隔线----------------------------