现在的位置: 首页 > 综合 > 正文

例题3.1 猜猜数据结构 UVa11995

2018年05月03日 ⁄ 综合 ⁄ 共 1146字 ⁄ 字号 评论关闭

1.题目描述:点击打开链接

2.解题思路:本题要求根据输入的数据和输出的数据来猜测一种可能的数据结构,备选答案有“栈,队列,优先队列”,结果也可能都不是或者不确定。STL中已经有这三种数据结构了,因此直接模拟题意,输出时判断是否对应即可。注意:弹出时要判断一下是否已经为空。

3.代码:

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;

stack<int>s;
queue<int>q;
priority_queue<int>p;
char st[][20] = { "impossible", "priority queue", "queue","not sure" , "stack", "not sure","not sure" ,"not sure"  };
void clear()
{
	while (!s.empty())s.pop();
	while (!q.empty())q.pop();
	while (!p.empty())p.pop();
}
void add(int x)
{
	s.push(x);
	q.push(x);
	p.push(x);
}
void pop()
{
	if (!s.empty())s.pop();
	if (!q.empty())q.pop();
	if (!p.empty())p.pop();
}
int main()
{
	//freopen("t.txt", "r", stdin);
	int n;
	while (~scanf("%d", &n))
	{
		clear();
		int ok1, ok2, ok3;
		ok1 = ok2 = ok3 = 1;
		for (int i = 0; i < n; i++)
		{
			int a, b;
			cin >> a >> b;
			if (a == 1)add(b);//统一添加
			else
			{
				if (s.empty() || s.top() != b)
					ok1 = 0;
				if (q.empty() || q.front() != b)
					ok2 = 0;
				if (p.empty() || p.top() != b)
					ok3 = 0;
				pop();//统一弹出
			}
		}
		int x = (ok1 << 2) | (ok2 << 1) | ok3;//编码,方便输出结果
		printf("%s\n", st[x]);
	}
	return 0;
}

抱歉!评论已关闭.