什么是队列？

队列（queue）是一种数据结构，它的特点是只允许从队尾入队，从队列头部出队，满足先进先出的性质，即先进入队列的元素先出队列。可以把它理解为排队排在前一个人的后面。
比如数字1 5 7 9 2的队列，插入一个元素3，应该插入到队尾，成为3 1 5 7 9 2，再插入一个5，应该排到3的前面，变成5 3 1 5 7 9 2，出队一个头部元素2，则成为3 1 5 7 9，所以满足先进队列的先出队的先进先出性质。
此外，队列只允许队首出队，新元素也只能在队尾入队,访问只能访问队首和队尾,无法从中间进行入队出队的操作也无法访问队列中间的元素。

队列（queue）的代码实现

1
2
3
int queue[MAXN];
int head = 0;
int tail = 0;

$queue$数组为队列开辟需要的存储仪器：$MAXN$是队列的最大能入队元素的次数,一般开一个较大的数防止溢出
$head、tail$为指示队首与队尾元素的两个指针。
如果有新元素插入，就会插入到$tail$这个位置

1
2
3
4
5
void push(int x)
{
	if(tail >= MAXN) cout<<"Queue overflow (队列溢出)";
	else queue[tail++] = x; //插入新的元素
}

这是插入操作，我们接着给出出队操作，两个结合着来讲解。

1
2
3
4
5
void pop() //弹出队首需要判断队列是否为空
{
	if(head == tail) cout<<"Queue is empty（队列为空）";
	else head++;
}

解释：队列元素插入数组后就一直在数组中，我们通过的是首尾指针的增减来实现队列的还原。
比如插入3 5 1，那么queue[0~2]分别指代3 5 1。此时$tail = 3,head = 0$ 下次插入会从queue[3]插入元素，queue[head]指代的是队首的3。

$pop$函数中会增加队首指针的值，比如进行一次出队操作：$head$增加为1，指代queue[1]，也就是5,但是删除的元素3并不会删除数组，只是两个指针向后滚动来还原整个队列。进行第二次出队，head = 2，指代元素1。
如果再进行一次出队，此时已经进行三次出队，head = tail = 3,那么队列为空。
这样我们便实现了出队和入队的操作，下面给出访问队首的操作。

1
2
3
4
5
6
7
8
9
int front()
{
	if(head == tail)
	{
		cout<<"Queue is empty（队列为空）";
		return -1; // 队列为空返回-1，此处也可以返回别的数，因为这并不代表一个对内元素，只代表“空队列”这个概念
	}
	else return queue[head]; //队列不为空，返回队首
}

接下来我们给出一道Luogu例题：https://www.luogu.com.cn/problem/P1996 大家可以在上面自测代码。

约瑟夫问题

题目描述

$n$ 个人围成一圈，从第一个人开始报数，数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

输入格式

输入两个整数 $n,m$。

输出格式

输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。

样例输入

1
10 3

样例输出

1
3 6 9 2 7 1 8 5 10 4

对于这道问题，我们发现会形成一个所谓的约瑟夫环，报数时候如果报的数字不是$m$,那么就可以让把队首放到队尾，通过访问队首元素并将其复制到队尾然后再队首出队实现。报完$m - 1$次后，开始队首出队，出队前输出队首，然后接着循环即可。代码如下

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
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
using namespace std;
const int MAXN = 10000007;
int queue[MAXN];
int head = 0;
int tail = 0;
int n,m;
void push(int x)
{
	if(tail >= MAXN) cout<<"Queue overflow (队列溢出)";
	else queue[tail++] = x;
}

void pop()
{
	if(head == tail) cout<<"Queue is empty（队列为空）";
	else head++;
}

int front()
{
	if(head == tail)
	{
		cout<<"Queue is empty（队列为空）";
		return -1;
	}
	else return queue[head];
}

int main(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++) push(i);
	while(head != tail) //如果队列不为空就一直进行循环
	{
		for(int i = 1; i < m; i++)
		{
			push(front());
			pop();
			//上面两步实现了将队首元素换到队尾
		}
		cout<<front()<<" ";
		pop(); //报数到m，队首出队
	}
	return 0;
}

我们补充一个访问队尾元素的代码

1
2
3
4
5
6
7
8
int back()
{
    if (head == tail) {
        cout << "Queue is empty (队列为空)";
        return -1;
    }
    return queue[tail - 1]; // 返回队尾元素
}

需要注意的一点，如果这里我们使用的头文件库有queue*或者是包含了该头文件的万能头bits/stdc++.h,数组的命名就不能使用queue。可以使用q或者其他名字来命名数组。那是为什么呢？
这里我们引出一个头文件queue中自带的现成的队列，使用STL来进行操作。

STL中的队列（queue）

1
2
3
4
5
6
7
8
#include<queue> : 队列所需要的头文件
queue<int> q : 建立一个队列q，其内部元素类型为int
q.push(k) : 将元素k插入队列q中
q.pop() : 队列q队首出队
q.front() : 访问队列q的队首元素
q.back() : 访问队列q的队尾元素
q.size() : 查询队列q的元素个数
q.empty() : 查询队列是否为空

特别注意： q.empty()为空返回真
接着我们使用STL中的队列来重新做一下这道题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	queue<int>q;
	for(int i = 1; i <= n; i++) q.push(i);
	while(q.size()) //判断队列是否为空，在这里等价为while(!q.empty())
	{
		for(int i = 1; i < m; i++)
		{
			q.push(q.front());
			q.pop();
		}
		cout<<q.front()<<" ";
		q.pop();
	}
	return 0;
}

双端队列（deque）

文章的最后我们再给出一个STL中自带的双端队列（deque）,支持队首队尾都能删除和插入元素，用法如下

1
2
3
4
5
6
7
8
9
deque<int> q : 建立双端队列q
q.push_back(k) : 在队尾插入元素k
q.push_front(k) : 在队首插入元素k
q.pop_back() : 移除队尾元素
q.pop_front() : 移除队首元素
q.front() : 访问队首元素
q.back() : 访问队尾元素
q.size() : 查询队列的元素个数
q.empty() : 查询队列是否为空

写在最后

自此，我们讲完了队列的实现和使用。队列不仅作用于一些特殊情境的模拟，在一些算法（宽度优先搜索，迪杰斯特拉算法等等）中都有使用。同时它是我们讲解的第一个数据结构，对于后续数据结构的实现和使用了提供了一些思想上的经验。
除了上面提到的最常见的队列，以及不常见的双端队列，我们还有一个经常使用的队列，叫做优先队列（priority_queue），不过这是一种基于**堆（heap）**实现的数据结构，将在后续的文章中进行讲解，如有需要，请点击此处前往学习