写在前面

队列(queue)是一种线性的数据结构, 和栈一样是一种运算受限的线性表.

其限制只能从表的前端进行删除操作, 而在表的后端进行插入操作.

一般允许进行插入的一端称为队尾, 允许删除的一端称为队头.

队列的插入操作叫入队, 删除操作叫出队.

使用队列需先导入头文件.

#include 
1

这里注意和STL中的deque的区别, 都是操作受限的线性表, 但deque是一种双端队列, 队头队尾均可插入删除; 但queue只允许在队头删除, 队尾插入.

构造

同堆栈(stack)一样, queue也没有较多的带参构造.

	//构造
	queue<int> q;	//构造一个空的队列
	queue<int> q1(q);	//拷贝构造
	
	deque<int> dq{ 1, 2, 3 };
	queue<int> q2(dq);

	queue<int> q3(initializer_list<int>{ 1, 2, 3 });

	//不支持
	queue<int> q{ 1, 2, 3 };
	queue<int> q1 = { 1, 2, 3 };
1
2
3
4
5
6
7
8
9
10
11
12

赋值

注意和拷贝构造的区别, 未初始化的是拷贝, 已初始化的是赋值.

	queue<int> q;	//构造一个空的队列
	queue<int> q1(q);	//拷贝构造
	
	deque<int> dq{ 1, 2, 3 };
	queue<int> q2(dq);

	queue<int> q3(initializer_list<int>{ 1, 2, 3 });

	q = q3;	//赋值操作
	
	queue<int> q4 = q;	//拷贝构造
1
2
3
4
5
6
7
8
9
10
11

大小操作

	queue<int>::size_type nSize = q.size();
	
	if (q.empty())
	{
		//空队列
	}
	else
	{
		//非空队列
	}
1
2
3
4
5
6
7
8
9
10

增删之push, pop成员函数

pop注意事项: 不能使用空的队列调用pop, 否则程序会异常终止.

	queue<int> q;	//构造一个空的队列
	q.push(1);
	q.push(2);
	q.push(3);

	nSize = q.size();


	//pop成员函数: 出队，注意队列不能非空
	for (int i = 0; i < nSize; i++)
	{
		q.pop();
	}

	for ( ; q.size() > 0; )
	{
		q.pop();
	}

	//不能这样
	for (int i = 0; i < q.size(); i++)
	{
		q.pop();
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

访问

不支持随机访问， 要想访问中间元素，必须得先出站.

//front成员函数: 返回队头元素的引用, 队头元素不出队。注意不能使用空队列对象调用该函数
	int nFront = q.front();

	//back成员函数: 返回队尾元素的引用。注意不能使用空队列对象调用该函数
	int nBack = q.back();

	for (int i = 0; i < nSize; i++)
	{
		cout << q.front() << endl;
		q.pop();
	}

	//不支持范围for循环
	for (auto nVal : q)
	{
		cout << nVal << endl;
	}

	//不支持迭代器: 没有迭代器，没有begin(), end()成员函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19