一、queue 的介绍

queue 翻译为队列，在 STL 中主要则是实现了一个先进先出的容器。

 

二、queue 的定义

单独定义一个 queue：

queue<typename> name; 
//这里的typename可以是任何基本类型，例如 int、double、char、结构体等，也可以是STL标准容器，例如vector、set、queue等。 

 

 

三、queue 容器内元素的访问

由于队列（queue）本身就是一种先进先出的限制性数据结构，因此在 STL 中只能通过 front（）来访问队首元素，或是通过 back（）来访问队尾元素。

#include <stdio.h>
#include <queue>
using namespace std;

int  main()
{
	queue<int> q;
	for (int i = 0; i < 6; i++)
	{
		q.push(i); //push(i) 用来将 i 压入队列，因此依次入队 0 1 2 3 4 5
	}
	printf("%d %d\n", q.front(),q.back());
	return 0;
}

 

四、queue 常用函数实例解析

（1）push()

push(x) 将 x 进行入队，时间复杂度为 O（1）。

（2）front() ，back()

front（）和 back（）可以分别获得队首元素和队尾元素，时间复杂度为 O（1）。

 

（3）pop()

pop（）令队首元素出队，时间复杂度为 O（1）。

#include <stdio.h>
#include <queue>
using namespace std;

int  main()
{
	queue<int> q;
	for (int i = 0; i < 6; i++)
	{
		q.push(i); //push(i) 用来将 i 压入队列，因此依次入队 0 1 2 3 4 5
	}
	q.pop();  // 出队首元素 0
	q.pop();  // 出队首元素 1
	q.pop();  // 出队首元素 2
	printf("%d %d\n", q.front(),q.back());
	return 0;
}

 

（4）empty()

empty() 检测 queue 是否为空，返回 true 则空，返回 false 则非空 。时间复杂度为 O（1）。

（5）size()

size() 返回 queue 中元素的个数，时间复杂度为 O（1）。

#include <stdio.h>
#include <queue>
using namespace std;

int  main()
{
	queue<int> q;
	if (q.empty()==true)
	{
		printf("EMPTY! \n");
	}
	else
	{
		printf("NOT EMPTY! \n");
	}

	for (int i = 0; i < 6; i++)
	{
		q.push(i); //push(i) 用来将 i 压入队列，因此依次入队 0 1 2 3 4 5
	}

	if (q.empty() == true)
	{
		printf("EMPTY! \n");
	}
	else
	{
		printf("NOT EMPTY! \n");
	}

	printf("%d\n", q.size());
	return 0;
}

 

五、queue 的常见用途

当需要实现广度优先搜索时，可以不用自己手动实现一个队列，而是用 queue 作为代替。

注意： 使用 front（）和 pop（）函数前，必须用 empty（）判断队列是否为空，否则可能因为队空而出现错误。

STL 的容器中还有两种容器跟队列有关，分别是双端队列（deque）和优先队列（priority_queue）。

双端队列（deque）：首尾皆可插入和删除的队列。

优先队列（priority_queue）：使用堆实现的默认将当前队列最大元素置于队首的容器。