【暑假集训笔记】栈与队列应用的一般思考方向

107 阅读 0 评论 71 点赞

我是靠谱客的博主虚心黑夜，最近开发中收集的这篇文章主要介绍【暑假集训笔记】栈与队列应用的一般思考方向，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/**栈应用：
1.单个栈应用
   火车站题型：根本问题————给定两个字符串，请问是否可以通过栈的操作（给个容器，后进先出的操作）让两个字符串相等
       解决思路：用栈模拟整个过程
           code1
2.多个栈应用
   计算器题型：涉及知识点：逆波兰表示法
       例题：输入下面算式计算出表达式的值（无负数，无括号，很简单） 5 + 6 * 7 / 8
       思路：数据放在一个栈（数据栈），+-放到一个栈（符号栈），* / 放到一个栈（临时栈）。
           输入数据之后，立即判断临时栈是否为空（为了保证乘除的优先级）
               如果为空：数据入数据栈
               如果不空：数据栈取出数据，与此数据进行相应运算，结果入符号栈
           数据输入完毕，乘除处理完毕
           符号栈与数据站进行运算（我习惯用双端队列deque）

3.其他
*/

//code1
int main()
{
	string a="输入序列",b="输出序列";

	stack<char> v;
	int j=0;//b的下标 
	int i=0;//a的下标
	
	//核心代码，根据问题不同需要扩展
	for(;i<a.size();i++){
		
		v.push(a[i]);// a入栈，此时栈内至少一个元素，栈顶元素是a
		
		//bug！！！一定要注意栈空与否的判断放在前面，不解释！
		while(!v.empty() && v.top() == b[j]){//判断栈顶与当前下标对应元素是否一样
			j++; //如果比对成功，就比对b的下一个元素
			v.pop();//比对成功a要出栈一个元素
		}
	} 
	if( v.empty() )
		cout<<"Yes."<<endl;
	else
		cout<<"No."<<endl;
	return 0;
}

/**queue
1.单个队列：
2.复合队列：很灵活，建立复杂的数据结构存储数据，利用队列的性质处理问题，此类问题的难点不是队列，而是数据存储的方式。
例题:POJ 2259
   在一个团队队列中，每个元素属于一个团队。如果一个元素进入一个队列，它首先从头到尾地搜寻这个队列——检查是否它的队友（在同一个团队称之为队友）
   也在这个队列里。如果有，它就排在它队友的后面（插队）。如果没有，它就排在整个队列的最后，成为新的最后一名.
   在普通队列中出队是这样的：元素从头到尾的被处理，按他们出现在团队队列里的顺序。你的任务是写一个程序模拟这样一个团队队列。
输入
   输入文件会包含一个或多个测试样例。每一个测试样例由代表团队数量的t（1<=t<=1000）开始。
   然后t只团队描述如下，每一个团队由一个表示元素个数的数字，以及每个元素组成。
   元素属于整型，并且范围在0到999999之间。一个团队可能有多达1000个元素。
   最后，指令列表如下。有三种不同的指令：
   ENQUEUE x——x进入团队队列。
   DEQUEUE x——处理第一个元素并将其移除
   STOP——结束一个测试样例。
   当t是0时，输入终止。
   警告：一个测试样例可能多达200000条指令，
   所以团队队列的实现应该是有效率的：入队和出队都应该花费常数时间。

输出
   对应每个测试样例，首先输出一行“Scenario #k”，
   其中k表示第几次测试。然后，每一个“DEQUEUE”指令打印包含出队的元素（单独占一行）.
   打印一空行在每一个测试样例之后，即使是最后一个测试样例。

   见code2
*/

//code2
/**
难点：如何判断是一个小队的 

思路：
构造大映射储存所有的队员信息：队员——队伍号（用map快速调用 ）
构造queue让团队参加排队
构造queue让队员在团队排序

难点：如何从队员信息过渡到队伍信息——使用map
输入队员，获取队伍
如果	队伍参加了团队排序，就让他排到团队内
		队伍没参加排序，就在团队排序中生成一个团队，团队就只有他一个人
输出队员：
先检查团队排序
排在前面的团队输出队员
如果团队空了，就让团队排序删除这个团队 


*/

int main()
{
	int n;
	int x;
	int num;
	int t=1; 
	while(scanf("%d", &n)&&n){
		map< int,int > team;//储存队伍成员与队伍编号信息 
		queue<int> xiaoteam[1001];// 储存每个队的成员排列 
		queue<int> bigteam;//储存队伍号的排队顺序 
		
		printf("Scenario #%dn",t++);
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			for(int k=0;k<x;k++){
				
				scanf("%d",&num);
				team[num] = i;
			}
		}
		char str[10];
		while(scanf("%s",str)){
			if(str[0] == 'S'){
				break;
			}
			else if(str[0] == 'E'){
				scanf("%d",&x);
				int temp = team[x];//获取队伍编号
				if(xiaoteam[temp].empty()) //如果队伍中还没有人排队，那他就排到后面去
					bigteam.push(temp);//队伍添加
				 
				xiaoteam[temp].push(x);//这个成员排到小队后面	
			}
			else if(str[0] == 'D'){
				int temp = bigteam.front();//取得排在前面的第一个小队
				
				int val = xiaoteam[temp].front(); //获取排头 
				xiaoteam[temp].pop();//排头出列
				 
				 //这时要判断这个小队是不是走光了，走光了就弹出这个小队的排名
				if(xiaoteam[temp].empty())
				 	bigteam.pop();

				printf("%dn",val);
			}
		}
		printf("n");
	}
	return 0;
}