探讨队列概念及其在广度优先搜索中的应用实例详解
本博文的目录:
$1 队列
$2 队列的例题
$3 广度优先搜索的例题
$1 队列:
•队列是什么?
队列是一种特殊的线性表,与栈不同,这种线性表只允许在表的前端(我们称为front或head)进行删除操作,在表的后端(我们称作rear或tail)进行插入操作。所以又叫F(First)I(In)F(First)O(Out)表。(对于栈来说,因为栈只允许在表的后端进行删除操作,所以叫做L(Last)I(In)F(First)O(Out)表)
•在队列里的元素设定:
tail / rear:表示队尾指针,应该指向队尾元素的所在位置
head / front :表示队头指针,应指向队头元素的前一个位置
•入队算法:
1 int q[maxn];
2 int head,tail; 3 int n; 4 head=0;//当前队列的头指针 5 tail=1;//当前队列的为指针 6 cin>>n; 7 q[tail]=n;//在当前尾指针处存上n的值 8 tail++;//将尾指针加一
•出队算法:
1 int q[maxn];
2 int head=0,tail=5;//假设队中有5个元素 3 cout<<q[head++]<<endl;//将队头元素输出
•循环队列:
(1)循环队列是啥?
当尾指针指向数组的最后一个元素时,数组将不能再继续存储,我们叫做“溢出”。但当队列的指针指向最后一个元素时,不一定是溢出了,因为对头指针不一定是0。若队头指针不为0,但队尾指针指向队列的最后一个元素时,这个队列理论上是不能继续存数据的,但是为队列所开的数组确实有空间,我们称之为“假溢出”。如果不对队列进行循环处理,就会造成对空间的极大浪费。这个时候,我们可以将整个队列看成是一个环,环上的元素就是队列的元素,队列的第maxn项后面为队列的第1项,这样就可以进行循环数组的使用啦!
(2)代码实现:
光说概念大家肯定不会完全理解,接下来是代码实现:
1 int q[maxn]; 2 int tail,head; 3 int n; 4 cin>>n; 5 q[tail%maxn]=n;//maxn表示q数组(队列)的长度 6 tail=(tail+1)%maxn;
(这只是一个模板,具体的使用方法视情况而定);
$2 队列的例题
•例--周末舞会:
【题目描述】
假设在周末舞会上,男士们和女士们进入舞厅时,各自排成一队。跳舞开始时,依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同,则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序,模拟上述舞伴配对问题。
【输入】
第一行两队的人数;
第二行舞曲的数目。
【输出】
配对情况。
【输入样例】
4 6 7
【输出样例】
1 1
2 2
3 3
4 4
1 5
2 6
3 1
直接上代码:
1 #include<cstdio>
2 #include<iostream>
3 #include<cstdlib>
4 #define maxn 1000010 5 using namespace std; 6 int head,tailw,tailm;//将两个队列看成一个,头指针是一样的,而尾指针则根据男女的人数决定; 7 int man[maxn],woman[maxn];//将所有男人的编号和所有女人的编号分别存到man和woman队列里; 8 int men,women,m;//men、women代表男人和女人的总数量; 9 int main(){ 10 scanf("%d%d",&men,&women); 11 scanf("%d",&m); 12 for(int i = 0;i < men;++i){ 13 man[i] = i+1; //读入男人的编号; 14 } 15 for(int i = 0;i < women;++i){ 16 woman[i] = i+1;//读入女人的编号; 17 } 18 head = 0; 19 tailw = women; tailm = men; 20 while(head < m){ 21 printf("%d %d\n",man[head],woman[head]); 22 man[tailm++] = man[head]; woman[tailw++] = woman[head]; 23 head++; 24 } 25 return 0; 26 }//简单易懂qaq
$3 广度优先搜索的例题
•例--连通块:
【题目描述】
一个n * m的方格图,一些格子被涂成了黑色,在方格图中被标为1,白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域,其中的每个黑色格子能通过四连通的走法(上下左右),只走黑色格子,到达该联通块中的其它黑色格子。
【输入】
第一行两个整数n,m(1≤n,m≤100),表示一个n * m的方格图。
接下来n行,每行m个整数,分别为0或1,表示这个格子是黑色还是白色。
【输出】
一行一个整数ans,表示图中有ans个黑色格子连通块。
【输入样例】
3 3 1 1 1 0 1 0 1 0 1
【输出样例】
3
1 #include<cstdio>
2 #include<iostream>
3 #include<cstdlib>
4 #define maxn 110 5 using namespace std; 6 const int flag[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};//设了一个数组,表示在(i,j)的情况下向4个方向搜索 7 int a[maxn][maxn],queue[maxn * maxn][2];//queue中存的是搜索到的联通块的横纵坐标 8 int n,m,ans; 9 bool p[maxn][maxn]; 10 11 void bfs(int x,int y){ 12 int head = 0, tail = 2; 13 queue[1][0] = x,queue[1][1] = y; 14 while(head < tail - 1){ 15 ++head; 16 x = queue[head][0]; 17 y = queue[head][1]; 18 for(int i = 0;i < 4;++i){ 19 int x1 = x + flag[i][0]; 20 int y1 = y + flag[i][1]; 21 if(x1 < 1 || y1 < 1 || x1 > n || y1 > m || !a[x1][y1] || p[x1][y1]) continue; 22 p[x1][y1] = true; 23 queue[tail][0] = x1; 24 queue[tail++][1] = y1; 25 } 26 } 27 } 28 29 int main(){ 30 cin>>n>>m; 31 for(int i = 1;i <= n;++i) 32 for(int j = 1;j <= m ;++j) cin>>a[i][j]; 33 for(int i = 1;i <= n;++i) 34 for(int j = 1;j <= m ;++j) 35 if(a[i][j] && !p[i][j]){ 36 ++ans;bfs(i,j); 37 } 38 cout<<ans<<endl; 39 return 0; 40 }
//本题的思路:搜索为1的元素-->如果为1,将联通块的附近搜索-->将搜过的元素标为0-->搞定!
推荐阅读
-
【2022新手指南】Java编程进阶之路 - 六、技术架构篇 ### MySQL索引底层解析与优化实战 - 你会讲解MySQL索引的数据结构吗?性能调优技巧知多少? - Redis深度揭秘:你知道多少?从基础到哨兵、主从复制全梳理 - Redis持久化及哨兵模式详解,还有集群搭建和Leader选举黑箱打开 - Zookeeper是个啥?特性和应用场景大公开 - ZooKeeper集群搭建攻略及 Leader选举、读写一致性、共享锁实现细节 - 探究ZooKeeper中的Leader选举机制及其在分布式环境中的作用 - Zab协议深入剖析:原理、功能与在Zookeeper中的核心地位 - RabbitMQ全方位解读:工作模式、消费限流、可靠投递与配置策略 - 设计者视角:RabbitMQ过期时间、死信队列与延时队列实践指南 - RocketMQ特性和应用场景揭示:理解其精髓与差异化优势 - Kafka详细介绍:特性及广泛应用于实时数据处理的场景解析 - ElasticSearch实力揭秘:特性概述与作为搜索引擎的广泛应用 - MongoDB认知升级:非关系型数据库的优势阐述,安装与使用实战教学 - BIO/NIO/AIO网络模型对比:掌握它们的区别与在网络编程中的实际应用 - Netty带你飞:理解其超快速度背后的秘密,包括线程模型分析 - 网络通信黑科技:Netty编解码原理与常用编解码器的应用,Protostuff实战演示 - 解密Netty粘包与拆包现象,怎样有效应对这一常见问题 - 自定义Netty心跳检测机制,轻松调整检测间隔时间的艺术 - Dubbo轻骑兵介绍:核心特性概览,服务降级实战与其实现益处 - Dubbo三大神器解读:本地存根与本地伪装的实战运用与优势呈现 ----------------------- 七、结语与回顾
-
探讨队列概念及其在广度优先搜索中的应用实例详解