简述:

队列:在一端插入,在另一端删除的特殊线性表。 删除称为出队,插入称为入队。出队和入队是队列的两个基本操作。允许出队的一端为队首,允许删除的一端为队尾。
队列是一种先进先出的数据结构。
常用数组实现队列,并用两个指针:头指针和尾指针来实现入队和出队操作。
头指针(head):指向队首的前一个位置。
尾指针(tail):指向队尾的位置。 因此当head=tail时,队列为空。

基本操作:
出队:从队首出队,++head,即头指针向后移动一个位置。
入队:从队尾入队,++tail,即尾指针向后移动一个位置。

如右图,元素3入队前,尾指针tail=5。元素3入队后,尾指针tail=6;此时头指针为head=3,队列中的元素个数为tail-head=3,为{7,8,3}。

例题:

1:Open Judge 2729: Blah数集

描述
大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对于以a为基的集合Ba定义如下:
(1) a是集合Ba的基,且a是Ba的第一个元素;
(2)如果x在集合Ba中,则2x+1和3x+1也都在集合Ba中;
(3)没有其他元素在集合Ba中了。
现在小高斯想知道如果将集合Ba中元素按照升序排列,第N个元素会是多少?
输入
输入包括很多行,每行输入包括两个数字,集合的基a(1<=a<=50))以及所求元素序号n(1<=n<=1000000)
输出
对于每个输入,输出集合Ba的第n个元素值
样例输入
1 100
28 5437
样例输出
418
900585

分析:a>=1,因此产生的数都是正数,即a<2a+1<3a+1。因为对于一个a,能产生两个数2a+1和3a+1,
可以用三个队列来维护Blah数列。第一个队列为升序排列的Blah数列(下文简称A队列),第二个为2a+1产生的数(B队列),第三个为3a+1产生的数(C队列)。

首先预处理,将基数a入A队列,将a产生的2a+1入B队列,3a+1入C队列。
然后可以比较B队列和C队列的队首,把较小的数取出来在A队列中入队。再将那个数产生的两个数入B,C队列,再比较,再入队,再生成新数。
所以整个思路就是:生成——比较——入A数列——生成——…………直到A数列元素达到n。
仔细体会用队列维护的思想。
代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int lenn=2000005;
int A[lenn],B[lenn],C[lenn];
int main()
{
	int a,n;
	for(;~scanf("%d %d",&a,&n);)
	{
		int h=0,t=0,h1=0,h2=0,t2=0,t1=0;
		A[++t]=a;
		while(t<=n)
		{
			B[++t1]=2*A[t]+1;C[++t2]=3*A[t]+1;
			int x=B[h1+1],y=C[h2+1];
			if(x>y)
			{
				A[++t]=y;h2++;
			}
			else if(x<y)
			{
				A[++t]=x;
				h1++;
			}
			else
			{
				A[++t]=B[h1+1];
				h1++;h2++;
			}
		}
		printf("%d\n",A[n];
	}
	return 0;
}

bfs是依靠队列这一数据结构实现的。
广度优先搜索算法的基本思想:
1、对于初始状态入队,设置初始状态为已访问
2、如果队列不为空时,出队队头元素,否则跳到第5步
3、检查出队的元素是否为最终解,如果是则跳到第5步。
4、对于出队的元素,检查所有相邻状态,如果有效并且未访问,则将所有有效的相邻状态进行入队,并且设置这些状态为已访问,然后跳到第2步重复执行
5、检查最后出队的元素是否为最终解,如果是输出结果,否则说明无解 。
广度优先搜索算法的关键是要搞清楚求解过程中每一步的相邻状态有哪些, 每个状态需要记录什么信息,在搜索过程中如何标记这些状态为已访问。
下面以这道题为例简单说一下:

例题:连通块

题目描述
一个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

分析:可以枚举每个格子,若它是涂黑的,且它不属于已经搜索过的连通块,则由它开始,扩展搜索它所在的连通块,并把连通块里的所有黑色格子标记为已搜索过。
如何扩展搜索一个连通块呢?用一个搜索队列,储存要搜索格子。每次取出队首的格子,对其进行四连通扩展,若有黑格子,将其加入队尾,扩展完就把该格子删除,当队列为空时,一个连通块就搜索完了。
代码如下:

#include<iostream>
using namespace std;
const int N=110;
const int flag[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int a[N][N],queue[N*N][2];
int n,m,ans;
bool p[N][N];
void bfs(int x,int y)
{
	int front=0,rear=2;
	queue[1][0]=x,queue[1][1]=y;
	while(front<rear-1)
	{
		++front;
		x=queue[front][0];
		y=queue[front][1];
		for(int i=0;i<4;++i)
		{
			int xl=x+flag[i][0];
			int yl=y+flag[i][1];
			if(xl<1||yl<1||xl>n||yl>m||!a[xl][yl]||p[xl][yl]) continue;
			p[xl][yl]=true;
			queue[rear][0]=xl;
			queue[rear++][1]=yl;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(a[i][j]&&!p[i][j])
			{
				++ans;bfs(i,j);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

参考:

1.例题2———信息学奥赛一本通( 科学技术文献出版社 )。
2.队列————孙晓。
3.广度优先搜索———— STEPHEN_。
4.例题1———OpenJudge

3 对 “浅谈数据结构:队列——基础”的想法;

发表评论

电子邮件地址不会被公开。