• 「数据结构详解·一」树的初步
• 「数据结构详解·二」二叉树的初步
• 「数据结构详解·三」栈
• 「数据结构详解·四」队列

1. 队列的定义、构成、术语和性质

队列(queue)是一种简单且重要的数据结构。
队列就像排队结账，队伍前面的人结账后离开队伍，队伍后面的人等待前面的人结账完再结账。
如图，这就是一个队列：

这个队列有四个元素，分别是 $114,514,1919$ 和 $810$。
我们一般认为队列左端靠前。
最前端的元素被称为队首(队头)，最后端的元素被称为队尾。
如图，红色箭头所指的就是队头，蓝色箭头所指的就是队尾：

现在队列中要加入一个元素 $x$，那么就像排队一样让 $x$ 添加到队尾。这一操作被称为入队。

现在最前面的 $114$ 要离开队伍，那么就将其弹出队列。这一操作被称为出队。

可以发现，队列和排队一样是井然有序的。所以队列的性质就是先进先出(FIFO, First-In-First-Out)。

2. 队列的实现

我们再来浅谈一下队列在代码中的实现。

2-1. 数组模拟队列

定义数组 $q$ 来模拟队列：

int q[N];
1

然后用变量 $h$ 表示队头下标，$t$ 表示队尾下标，$s$ 表示队列元素个数。
入队：

void push(int x)
{
	q[++t]=x;//队尾下标加一
	s++;
}
1
2
3
4
5

出队：

void pop()
{
	h++;//直接将队头下标加一，使得那个元素不在 [h,t] 的范围内
	s--;
}
1
2
3
4
5

访问队首元素：

int front()
{
	return q[h];
}
1
2
3
4

访问队尾元素：

int back()
{
	return q[t];
}
1
2
3
4

判断队列是否为空：

bool empty()
{
	return h>t;//头下标大于尾下标意味着队列里无元素，为空
}
1
2
3
4

队列元素个数：

int size()
{
	return s;
}
1
2
3
4

但是，有的时候入队时 $t$ 已经超过数组范围，然而在 $h$ 之前的数组中仍然有空的元素，这一现象被称为假溢出。

2-2. 循环队列

为了避免假溢出，我们可以用一种“循环队列”来节约空间且避免这一现象。
大概是酱紫：

那么部分的实现都要改一下：
入队：

void push(int x)
{
	t=(t+1)%N+1;//防止出现假溢出，下同
	q[t]=x;
	s++;
}
1
2
3
4
5
6

Java Design Demo -简单的队列

rar 5星 超过95%的资源 1.12MB

下载

出队：

void pop()
{
	h=(h+1)%N+1;
	s--;
}
1
2
3
4
5

访问队首元素：

int front()
{
	return q[h];
}
1
2
3
4

访问队尾元素：

int back()
{
	return q[t];
}
1
2
3
4

判断队列是否为空：

bool empty()
{
	return (t+1)%N+1==h;//发现 t 向后一个就是头指针
}
1
2
3
4

队列元素个数：

int size()
{
	return s;
}
1
2
3
4

2-3. C++ STL queue

C++ STL 中的 queue 也为我们提供的了类似的功能。
定义一个 STL queue：

设一循环队列Queue，只有头指针front，不设尾指针，另设一个内含元素个数的计数器，试写出相应的进队、出队算法。

java 0星 超过10%的资源 2KB

下载

queue<int>q;
1

成员函数：

3. 例题详解

3-1. 洛谷 B3616 【模板】队列

模板题。
参考代码：

#include
using namespace std;

queue<int>q;

int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int op,x;
		cin>>op;
		if(op==1)
		{
			cin>>x;
			q.push(x);
		}
		else if(op==2)
		{
			if(q.empty()) cout<<"ERR_CANNOT_POP"<<endl;
			else q.pop();
		}
		else if(op==3)
		{
			if(q.empty()) cout<<"ERR_CANNOT_QUERY"<<endl;
			else cout<<q.front()<<endl;
		}
		else cout<<q.size()<<endl;
	}
 	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3-2. 洛谷 P1996 约瑟夫问题

用队列模拟一遍即可。
参考代码：

#include
using namespace std;

queue<int>q;

int main()
{
	int n,m,t=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		q.push(i);
	}
	while(q.size()>1)
    {
        t++;
        int s=q.front();
        q.pop();
        if(t==m)
		{
			t=0;
			cout<<s<<' ';
		}
        else q.push(s);
    }
	cout<<q.front();
 	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

4. 巩固练习

• 洛谷 P1540 [NOIP2010 提高组] 机器翻译
• 洛谷 P1443 马的遍历