1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。(尾插，头删)
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。?

queue的使用

queue()

?构造空的队列。

const container_type& ctnr = container_type()：这是一个空间适配器，我们只需要知道有了它就可以高效申请释放空间就可以了。

举个栗子：

int main()
{
	queue<int> q;
	return 0;
}

我们来调试一下看看情况：

通过调试我们发现无参构造的对象q，是一个空队列，里面没有数据。

queue<int> q：我们在构造对象时，要在queue后面加一个<类型>，在这里指定类型是int，说明该队列里面存放的是int类型的数据。?注意：q后面不能加()

push()

?将元素val插入到队尾。

举个栗子：

int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	return 0;
}

我们来调试一下看看情况：

通过数组下标我们发现数据1 2 3依次从队尾插入进去了。?

我们画图来展示一下这个过程：

pop()

?将队头的元素val进行删除(哨兵位头结点除外)。

举个栗子：

int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.pop();
	q.pop();
	return 0;
}

我们调试一下看看这个过程：

我们发现，每次pop()，就把队头的数据删除了，第一次pop(),删除了数据1，第二次pop()删除了数据2。

我们画图来展示一下这个过程：

empty()

判断队列是否为空。如果为空就返回真(1)，如果不为空就返回假(0)。?

举个栗子：

int main()
{
	queue<int> q1;
	q1.push(1);
	q1.push(2);
	q1.push(3);
	cout << q1.empty() << endl;

	queue<int> q2;
	cout << q2.empty() << endl;
	return 0;
}

运行结果：

我们发现q1队列中有数据，所以就返回假。q2是一个空队列，于是就返回真。?

size()

返回队列中元素的个数。?

举个栗子：

int main()
{
	queue<int> q1;
	q1.push(1);
	q1.push(2);
	q1.push(3);
	cout << q1.size() << endl;

	queue<int> q2;
	cout << q2.size() << endl;
	return 0;
}

运行结果：

front()?

返回队列中队头元素的引用。?

举个栗子：

int main()
{
	queue<int> q1;
	q1.push(1);
	q1.push(2);
	q1.push(3);
	cout << q1.front() << endl;

	int& p = q1.front();
	p = 10;
	cout << q1.front() << endl;
	return 0;
}

运行结果：

我们发现第一次输出是取到了队头的数据。

并且我们知道返回的是队头数据的引用，那么是否可以修改呢？?

我们通过int& p来接收返回值并修改，发现对头的数据的确被修改了！

注意：如果我们将来用引用变量接收了队头的返回值，我们为防止误操作把队头数据修改了，我们最好用const int& p来修饰。

back()

返回队尾中数据的引用。?

举个栗子：

int main()
{
	queue<int> q1;
	q1.push(1);
	q1.push(2);
	q1.push(3);
	cout << q1.back() << endl;

	int& p = q1.back();
	p = 30;
	cout << q1.back() << endl;
	return 0;
}

运行结果：

?我们发现第一次输出是取到了队尾的数据。

并且我们知道返回的是队尾数据的引用，那么是否可以修改呢？?

我们通过int& p来接收返回值并修改，发现对头的数据的确被修改了！

注意：如果我们将来用引用变量接收了队尾的返回值，我们为防止误操作把队尾数据修改了，我们最好用const int& p来修饰。

swap()

交换两个队列中的数据。

举个栗子：

int main()
{
	queue<int> q1;
	q1.push(1);
	q1.push(2);
	q1.push(3);

	queue<int> q2;
	q2.push(10);
	q2.push(20);
	q2.push(30);

	q1.swap(q2);

	while (!q1.empty())
	{
		cout << q1.front() << " ";
		q1.pop();
	}
	cout << endl;
	while (!q2.empty())
	{
		cout << q2.front() << " ";
		q2.pop();
	}
	return 0;
}

运行结果：

我们发现q1原来的数据时1 2 3;q2原来的数据是10 20 30。

经过q1.swap(q2)后我们发现q1里面的数据是10 20 30。q2里面的数据是1 2 3?

注意：这里的swap不是算法库里面的，而是queue里面的成员函数~

queue的模拟实现

成员变量

template<class T,class Container = deque<T>>
private:
Container _con;

//第二个模板参数给一个缺省值(缺省值从右往左给)

template<class T,class Container = deque<T>>：Container是一个容器适配器，在这里我们默认使用deque<T>这样的容器。

_con：构造的指定容器的一个对象。模板参数是直接用，不可以Container<T>这样来操作。

? ? ? ? 这里的容器适配器也可以使用list<T>来代替。适配的容器只要支持queue内部实现方法对应的接口即可。

成员函数

bool empty() const

bool empty() const
{
	return _con.empty();
}

bool empty() const //判断队列是否为空
{
?? ?return _con.empty();//调用适配的容器的empty()的函数接口。
}

size_t size() const

size_t size() const
{
	return _con.size();
}

size_t size() const?
{
?? ?return _con.size(); //调用_con容器的size()的函数接口。
}

const T& front() const

const T& front() const
{
	return _con.front();
}

const T& front() const? //返回头部数据的引用，由于被const修饰，所以不能被修改
{
?? ?return _con.front(); //调用适配的容器的front()接口。_con适配的容器一定要有支持这样的接口。
}

T& front()?

T& front() 
{
	return _con.front();
}

T& front()? //与上面的函数构成函数重载，在这里返回的val值可以被修改
{
?? ?return _con.front();
}

const T& back() const

const T& back() const
{
	return _con.back();
}

const T& back() const?//返回尾部数据的引用，由于被const修饰，所以不能被修改
{
?? ?return _con.back();//调用适配的容器的back()接口。_con适配的容器一定要有支持这样的接口。
}

T& back()

T& back()
{
	return _con.back();
}

T& back()?//与上面的函数构成函数重载，在这里返回的val值可以被修改
{
?? ?return _con.back();
}

void push(const T& x)

void push(const T& x)
{
	_con.push_back(x);
}

void push(const T& x)?
{
?? ?_con.push_back(x);//往尾部插入数据，适配的容器要支持push_back()这样的函数接口
}

void pop()

void pop()
{
	_con.pop_front();
}

void pop()
{
?? ?_con.pop_front(); //删除头部数据，_con容器要支持头删这样的函数接口。像list就可以。

注意：vector不支持pop_front()、push_front()，所以不能当queue适配的容器。
}

完整代码

queue.h

#pragma once
#include<deque>
#include<iostream>
using namespace std;

namespace cyq
{
	template<class T,class Container = deque<T>>
	class queue
	{
	public:
		bool empty() const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}
		const T& front() const
		{
			return _con.front();
		}
		T& front() 
		{
			return _con.front();
		}
		const T& back() const
		{
			return _con.back();
		}
		T& back()
		{
			return _con.back();
		}
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
	private:
		Container _con;
	};
}

测试代码

int main()
{
	cyq::queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);

	cout << q.size() << endl;
	cout << "队尾数据：" << q.back() << endl;
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
	return 0;
}

运行结果：

总结?

? ? ? ? 我们发现C++中stack和queue的模拟实现都使用了容器适配器，很好地体现了复用的原则。通过模板可以让编译器自动推导存储的数据类型，这体现了泛型编程的特点。

可以通过与C语言中模拟实现队列来进行比较，看看其中代码的差距体现。在最上面有博客的链接~

1、queue是先进先出的规则，它不支持迭代器！所以也就不支持范围for(语法糖)，和stack一样。

2、我们可以构造的方式：

queue<int,deque<int>> q; //使用deque容器

queue<int,list<int>> q; //使用list容器

3、我们发现我们模拟实现的queue没有自己实现构造函数，这样可以吗？答案是可以的。这里我们不需要自己显示实现构造函数，使用编译器默认生成的就可以。因为编译器默认生成的构造函数会自动调用适配的容器里面的构造函数(调用自定义类型的构造函数)。如果老铁们对这个知识点不理解，可以看一下我之前写的C++关于类和对象博客~ stack也是同理~

看到这里，给博主支持一下吧~

? ? ?