目录

一 queue

1 常见构造

1 空容器构造函数

2. 使用指定容器构造

3 拷贝构造函数

2 empty

3  size

4 front && back

5 push && pop

6 emplace

7 swap

二 优先级队列( priority_queue)

1 常见构造

2 其他操作

3 大堆和小堆

1. 大小堆切换

2 自定义类型比较

三 总结

---

一 queue

1 常见构造

1 空容器构造函数

构造一个没有元素的空容器。

2. 使用指定容器构造

可以使用指定的底层容器来构造栈，默认是 std::deque，但也可以是 std::vector 或 std::list

3 拷贝构造函数

构造一个容器，其中包含 x 中每个元素的副本，顺序相同

void Test1()
{
	queue<int> q1;
	cout << q1.size() << endl;

	vector<int> v{ 1, 2, 3, 4 };
	queue<int, vector<int>> q2(v);
	cout << q2.size() << endl;

	queue<int> q3(q1);
	cout << q3.size() << endl;
}

2 empty

测试容器是否为空

bool empty() const;

void Test2()
{
	queue<int> q1;
	if (q1.empty()) cout << "q1 is empty" << endl;
	else cout << "q1 is not empty" << endl;
	
	vector<int> v{ 1, 2, 3, 4 };
	queue<int, vector<int>> q2(v);
	if (q2.empty()) cout << "q2 is empty" << endl;
	else cout << "q2 is not empty" << endl;

}

3  size

返回容器大小

上面已经演示过了, 这里不做过多讲解

4 front && back

返回对头元素和队尾元素

value_type& front(); 
const value_type& front() const;

value_type& back(); 
const value_type& back() const;

void Test3()
{
	vector<int> v{ 1, 2, 3, 4 };
	queue<int, vector<int>> q2(v);
	cout << "front: " << q2.front() << endl;
	cout << "back: " << q2.back() << endl;
}

5 push && pop

void push(const value_type& val); 
void push(value_type&& val);
void pop();

void Test4()
{
	queue<int> q;
	for (int i = 0; i < 4; i++)
	{
		q.push(i);
	}

	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
}

6 emplace

 作用和 push一样的, 只是效率不一样, 涉及到了右值引用问题, 后面讲

7 swap

void swap (queue& x) noexcept(/*see below*/);

交换两个容器的内容

void Test5()
{
	queue<int> q1, q2;
	for (int i = 0; i < 4; i++)
	{
		q2.push(i);
	}

	q1.swap(q2);
	cout << "q1.size--> " << q1.size() << endl;
	cout << "q2.size--> " << q2.size() << endl;
}

二 优先级队列( priority_queue)

1 常见构造

同queue一样

void Test6()
{
	priority_queue<int> q1;
	cout << q1.size() << endl;

	vector<int> v{ 1, 2, 3, 4 };
	priority_queue<int, vector<int>> q2(v.begin(), v.end());// 这里不同queue
	cout << q2.size() << endl;

	priority_queue<int> q3(q1);
	cout << q3.size() << endl;
}

2 其他操作

同 queue一样, 很简单 

3 大堆和小堆

1. 大小堆切换

#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
       // 默认情况下，创建的是大堆，其底层按照小于号比较
       vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
       priority_queue<int> q1;
       for (auto& e : v)
       {
              q1.push(e);
       }

       while (!q1.empty())
       {
              cout << q1.top() << ' ';
              q1.pop();
       }
       cout << endl;

       // 如果要创建小堆，将第三个模板参数换成greater比较方式
       priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
       while (!q2.empty())
       {
              cout << q2.top() << ' ';
              q2.pop();
       }
}

int main()
{
       TestPriorityQueue();
       return 0;
}

2 自定义类型比较

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。 

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d)const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d)const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& _cout, const Date& d)
	{
		_cout << d._year << "-" << d._month << "-" << d._day;
		return _cout;
	}
private:
	int _year;
	int _month;
	int _day;
};
void TestPriorityQueue2()
{
	// 大堆，需要用户在自定义类型中提供<的重载
	priority_queue<Date> q1;
	q1.push(Date(2018, 10, 29));
	q1.push(Date(2018, 10, 28));
	q1.push(Date(2018, 10, 30));
	cout << q1.top() << endl;
	// 如果要创建小堆，需要用户提供>的重载
	priority_queue<Date, vector<Date>, greater<Date>> q2;
	q2.push(Date(2018, 10, 29));
	q2.push(Date(2018, 10, 28));
	q2.push(Date(2018, 10, 30));
	cout << q2.top() << endl;
}

三 总结

本节难度不算大, 但是优先级队列涉及到了前面大小堆知识, 对概念不清晰的可以看看我前面的排序章节

昨天游泳了, 今天全身酸痛. 大家一定要做到生活平很, 锻炼纳入到自己学习和工作中. 

前段日子, 不是蓝桥杯嘛, 搞了个省三, 因为学校的一些傻逼操作导致我丧失一个半小时时间, 有一道很难的DFS决策树问题, 测试完毕没问题,可是没时间提交了, 差几秒. 虽然我觉得省三没啥技术含量, 然后学校的傻逼操作对我也是心态打击. 但是感觉老爸挺高兴的, 又发朋友圈又给我发红包的, 我还是很开心, 下次再来吧. 

继续加油