等级标准
掌握数据结构及结构的概念；掌握数据结构中的指针和链表；掌握数据结构中的栈；掌握数据结构中的队列；掌握数据结构中的哈希；能够使用上述方法编写指定功能的正确完整的程序。stack or queue
考试题目
栈和队列都是常用的线性结构，它们都提供两个操作：
Push：加入一个元素。
Pop：弹出一个元素。
不同的是，栈是”先进后出”，而队列则是”先进先出”。
给出一个线性结构的进出顺序，判定这个结构是栈还是队列。
时间限制：1000
内存限制：65535
输入
第一行输入一个整数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 LOCALfreopen("09_6_1.in", "r", stdin);#endifstack<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){//pushif(bs == true) s.push(val);if(bq == true) q.push(val);}else if (type == 2){//popif(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;}
栈的基本操作
考试题目
栈是一种重要的数据结构，它具有push k和pop操作。push k是将数字k加入到栈中，pop则是从栈中取一个数出来。
栈是后进先出的：把栈也看成横向的一个通道，则push k是将k放到栈的最右边，而pop也是从栈的最右边取出一个数。
假设栈当前从左至右含有1和2两个数，则执行push 5和pop操作示例图如下：
push 5 pop
栈 1 2 -------> 1 2 5 ------> 1 2
现在，假设栈是空的。给定一系列push k和pop操作之后，输出栈中存储的数字。若栈已经空了，仍然接收到pop操作，
则输出error。
时间限制：1000
内存限制：65536
输入
第一行为m，表示有m组测试输入，m<100。 每组第一行为n，表示下列有n行push k或pop操作。（n<150） 接下来n行，每行是push k或者pop，其中k是一个整数。 （输入保证同时在栈中的数不会超过100个）
输出
对每组测试数据输出一行。该行内容在正常情况下，是栈中从左到右存储的数字，数字直接以一个空格分隔，如果栈空，则不作输出；但若操作过程中出现栈已空仍然收到pop，则输出error。
样例输入
2
4
push 1
push 3
pop
push 5
1
pop
样例输出
1 5
error
参考答案
#include<bits/stdc++.h>using namespace std;int main(){#ifdef LOCALfreopen("09_6_2.in", "r", stdin);#endifstack<int> s;stack<int> sTmp;int m;scanf("%d", &m);for(int i = 1; i <= m; i++){int n;scanf("%d", &n);for(int j = 1; j <= n; j++){char type[10];memset(type, 0, sizeof(type));scanf("%s", &type);if(strcmp(type, "push") == 0){int val;scanf("%d", &val);s.push(val);}else if(strcmp(type, "pop") == 0){if(s.empty()){printf("error\n");break;}s.pop();}}//s堆栈数据倒排到STmp堆栈while(!s.empty()){sTmp.push(s.top());s.pop();}while(!sTmp.empty()){printf("%d ", sTmp.top());sTmp.pop();}printf("\n");}return 0;}
发型糟糕的一天
考试题目
农夫John 的N(1 ≤ N ≤ 80,000)只奶牛中，有一些也许正在经历发型糟糕的一天。每只奶牛对自己乱糟糟的发型都有自知之明，农夫John想知道所有奶牛能看到其他奶牛头顶的数量之和。
任意奶牛i身高记为 hi (1 ≤ hi ≤ 1,000,000,000)，所有奶牛面向东方（本题示意图的右面）依次站成一条线。因此，奶牛i能够看到在它前面的（奶牛i+1，i+2…）所有身高比它低的奶牛，直到被一头比它高的奶牛挡住
考虑如下的例子：
=
= =
= - = Cows facing right ->
= = =
= - = = =
= = = = = =
1 2 3 4 5 6 奶牛#1 可以看见奶牛#2, 3, 4的头顶
奶牛#2 无法看到任何奶牛的头顶
奶牛#3可以看见奶牛#4的头顶
奶牛#4无法看到任何奶牛的头顶
奶牛#5可以看见奶牛#6的头顶
奶牛#6无法看到任何奶牛的头顶!
用ci表示奶牛i能够看到头顶的奶牛个数；请计算c1 至cN的和。对于上面这个例子，其和为：3 + 0 + 1 + 0 + 1 + 0 = 5。
时间限制：2000
内存限制：65536
输入
第1行：奶牛数N
第2行至N+1行：第i+1行包含一个整数，表示奶牛i的高度
输出
第1行：c1 至cN的累加和
样例输入
6
10
3
7
4
12
2
样例输出
5
参考答案
在这里插入代码片
合影效果
考试题目
小云和朋友们去爬香山，为美丽的景色所陶醉，想合影留念。如果他们站成一排，男生全部在左（从拍照者的角度），并按照从矮到高的顺序从左到右排，女生全部在右，并按照从高到矮的顺序从左到右排，请问他们合影的效果是什么样的（所有人的身高都不同）？
时间限制：1000
内存限制：65536
输入
第一行是人数n（2 <= n <= 40，且至少有1个男生和1个女生）。 后面紧跟n行，每行输入一个人的性别（男male或女female）和身高（浮点数，单位米），两个数据之间以空格分隔。
输出
n个浮点数，模拟站好队后，拍照者眼中从左到右每个人的身高。每个浮点数需保留到小数点后2位，相邻两个数之间用单个空格隔开。
样例输入
6
male 1.72
male 1.78
female 1.61
male 1.65
female 1.70
female 1.56
样例输出
1.65 1.72 1.78 1.70 1.61 1.56
参考答案
#include <bits/stdc++.h>using namespace std;int main(){int n;scanf("%d", &n);vector<float> Men;vector<float> Women;string gender;float height;for(int i = 1; i <= n; i++){scanf("%f%f", &gender, &height);if (gender == "male"){Men.push_back(height);}else if (gender == "female"){Women.push_back(height);}}sort(Men.begin(), Men.end(), less<float>()); //sort ascendingsort(Women.begin(), Women.end(), greater<float>()); // sort descending for(int i = 0; i < Men.size(); i++){printf(".2f ", Men[i]);}for(int i = 0; i < Men.size(); i++){printf(".2f ", Women[i]);}printf("\n");return 0;}
