【stack、queue、deque、priority_queue】C++ 栈 / 队列 / 优先级队列全解析！手撕实现 + 二叉树层序遍历（附源码）
栈和队列没有迭代器，他们只是容器适配器，不是容器。容器才有迭代器
文章目录
- 栈Stack
- 头文件：stack
- 本质
- 成员函数
- 实现
- stack.h
- 按需实例化：
- 队列queue
- 本质
- 成员函数
- 实现
- queue.h
- deque双端队列
- 成员函数
- priority_queue优先级队列
- 本质
- 头文件：queue‼️
- 成员函数
- 应用
- 大根堆
- 小根堆
- 二叉树的层序遍历
- 1.实现层序遍历：
- 2.进一步实现题目要求
栈Stack
➡️有关 栈的实现/二叉树的实现 的知识，可以点击这里进行学习⬅️
头文件：stack
本质
template<classT,classContainer=deque<T>>classstack;- 后进先出
- 栈是一种“容器适配器” ——>栈可能是由list，vector或deque容器（称为底层容器）变化而来
- 底层容器，如果不传，默认是deque
成员函数
(constructor)
Construct stack (public member function )
empty
Test whether container is empty (public member function )
size
Return size (public member function )
top
Access next element (public member function )
push
Insert element (public member function )
emplace
Construct and insert element (public member function )
pop
Remove top element (public member function )
swap
Swap contents (public member function )
实现
stack.h
#pragmaoncenamespacelcj{template<classT,classContainer=vector<T>>classstack{public:/// <summary>/// 不用写构造函数，因为container是自定义类型，会调用对应的构造函数/// </summary>///voidpush(constT&x){_con.push_back(x);}voidpop(){_con.pop_back();}constT&top()const{return_con.back();///不能通过‘[ ]’访问，当container是list时，没有这个功能}size_tsize()const{return_con.size();}boolempty()const{return_con.size()==0;}private:Container _con;};}按需实例化：
在.h中写的类中的成员函数，并不会全都被实例化，编译器只实例化使用的接口——>编译器不检查细节语法，有时候不会报错，但是使用的时候还是会发生错误——>写函数的时候还是要写一个检查一个
队列queue
本质
template<classT,classContainer=deque<T>>classqueue;- 先进先出
- 也是一种“容器适配器” ——>栈可能是由list或deque容器（称为底层容器）变化而来
- 底层容器，如果不传，默认是deque
成员函数
(constructor)
Construct queue (public member function )
empty
Test whether container is empty (public member function )
size
Return size (public member function )
front
Access next element (public member function )
back
Access last element (public member function )
push
Insert element (public member function )
emplace
Construct and insert element (public member function )
pop
Remove next element (public member function )
swap
Swap contents (public member function )
实现
queue.h
#pragmaoncenamespacelcj{template<classT,classContainer=list<T>>classqueue{public:/// <summary>/// 不用写构造函数，因为container是自定义类型，会调用对应的构造函数/// </summary>///voidpush(constT&x){_con.push_back(x);}voidpop(){_con.pop_front();}constT&back()const{return_con.back();///不能通过‘[ ]’访问，当container是list时，没有这个功能}constT&front()const{return_con.front();///不能通过‘[ ]’访问，当container是list时，没有这个功能}size_tsize()const{return_con.size();}boolempty()const{return_con.size()==0;}private:Container _con;};}deque双端队列
stack和queue的缝合
成员函数
| 函数分类 | 函数名 | 功能说明 |
|---|---|---|
| 构造 / 析构 / 赋值 | (constructor) | 构造 deque 容器（公有成员函数） |
| (destructor) | 销毁 deque 容器（公有成员函数） | |
| operator= | 给 deque 容器赋值（公有成员函数） | |
| 迭代器（Iterators） | begin | 返回指向容器起始位置的迭代器（公有成员函数） |
| end | 返回指向容器末尾位置的迭代器（公有成员函数） | |
| rbegin | 返回指向容器反向起始位置的反向迭代器（公有成员函数） | |
| rend | 返回指向容器反向末尾位置的反向迭代器（公有成员函数） | |
| cbegin | 返回指向容器起始位置的 const 迭代器（公有成员函数） | |
| cend | 返回指向容器末尾位置的 const 迭代器（公有成员函数） | |
| crbegin | 返回指向容器反向起始位置的 const 反向迭代器（公有成员函数） | |
| crend | 返回指向容器反向末尾位置的 const 反向迭代器（公有成员函数） | |
| 容量管理（Capacity） | size | 返回容器当前存储的元素数量（公有成员函数） |
| max_size | 返回容器可容纳的最大元素数量（公有成员函数） | |
| resize | 改变容器的大小（公有成员函数） | |
| empty | 检测容器是否为空（公有成员函数） | |
| shrink_to_fit | 释放容器未使用的内存，收缩到适配当前元素大小（公有成员函数） | |
| 元素访问（Element access） | operator[] | 访问容器中指定下标位置的元素（公有成员函数） |
| at | 访问容器中指定下标位置的元素，带越界检查（公有成员函数） | |
| front | 访问容器的第一个元素（公有成员函数） | |
| back | 访问容器的最后一个元素（公有成员函数） | |
| 内容修改（Modifiers） | assign | 给容器重新赋值，覆盖原有内容（公有成员函数） |
| push_back | 在容器末尾添加一个元素（公有成员函数） | |
| push_front | 在容器开头插入一个元素（公有成员函数） | |
| pop_back | 删除容器末尾的最后一个元素（公有成员函数） | |
| pop_front | 删除容器开头的第一个元素（公有成员函数） | |
| insert | 在容器指定位置插入元素（公有成员函数） | |
| erase | 删除容器指定位置的元素（公有成员函数） | |
| swap | 交换两个 deque 容器的内容（公有成员函数） | |
| clear | 清空容器内的所有元素（公有成员函数） | |
| emplace_front | 在容器开头直接构造并插入一个元素（公有成员函数） | |
| emplace_back | 在容器末尾直接构造并插入一个元素（公有成员函数） | |
| 分配器（Allocator） | get_allocator | 获取容器使用的内存分配器（公有成员函数） |
| 非成员函数重载 | relational operators | deque 容器的关系比较运算符（函数模板） |
| swap | 交换两个 deque 容器的内容（函数模板） |
priority_queue优先级队列
➡️有关 堆和二叉树 的知识，可以点击这里进行学习【数据结构精讲】堆与二叉树从底层原理到代码落地：堆的构建 / 调整 / 排序 + 二叉树遍历 / 操作（附完整 C++ 源码 + LeetCode 题解）⬅️
本质
template<classT,classContainer=vector<T>,classCompare=less<typenameContainer::value_type>>classpriority_queue;- 就是个堆，默认是大根堆
- 也是容器适配器，默认是vector（因为下标访问用的多）
头文件：queue‼️
不是单独的‼️
成员函数
(constructor)
Construct priority queue (public member function )
empty
Test whether container is empty (public member function )
size
Return size (public member function )
top
Access top element (public member function )
push
Insert element (public member function )
emplace
Construct and insert element (public member function )
pop
Remove top element (public member function )
swap
Swap contents (public member function )
应用
大根堆
priority_queue<int, vector<int>, less<int>> pq;中的：less<int>也可以不写，是默认的，这时候是大根堆——>打印出来是从大到小的
#include<queue>usingnamespacestd;///必须在#include"stack.h"的前面，这样，如果stack.h里面有std::cout这种函数也没问题intmain(){priority_queue<int,vector<int>,less<int>>pq;pq.push(3);pq.push(777);pq.push(66);pq.push(88);pq.push(22);pq.push(9);while(!pq.empty()){cout<<pq.top()<<endl;pq.pop();}return0;}小根堆
——>从小到大打印
只需要改less<int>为greater<int>即可
栈的压入、弹出序列
- 入栈序列，每次入栈一个值
- 如果入后的栈顶数据跟出栈序列匹配，——>出栈——>不断匹配，不断出栈
- 入栈序列入完了，就结束了
二叉树的层序遍历
原题链接：二叉树的层序遍历
这个题目给的是二叉树，要求是输出一个vector<vector<int>>类型的数组
1.实现层序遍历：
队列存节点指针，下来一个节点，放一个节点的子节点
创造一个队列，存的是TreeNode*类型的指针：
queue<TreeNode*> q;插入树根：
q.push(root);while循环遍历：
条件： 队列中还有元素：
while(!q.empty())循环体：
得到队列头节点：
TreeNode* thisnode=q.front();头删：
q.pop();操作：……
将这个节点的孩子放进队列：
if(thisnode->left)
q.push(thisnode->left);
if(thisnode->right)
q.push(thisnode->right);
queue<TreeNode*>q;intlevelsize=0;if(root){q.push(root);}while(!q.empty()){TreeNode*thisnode=q.front();q.pop();//对thisnode的操作if(thisnode->left)q.push(thisnode->left);if(thisnode->right)q.push(thisnode->right);}2.进一步实现题目要求
在上面的条件下，我们一层一层输入数据
- levelsize作为内部的循环条件
- 在“插入树根”的时候，levelsize置为1——因为第一层只有一个节点
- 然后的循环中，只将levelsize个节点的子节点插入队列中
- 插入结束之后的队列的size，就是下一层的节点个数
- 在“插入树根”的时候，levelsize置为1——因为第一层只有一个节点
classSolution{public:vector<vector<int>>levelOrder(TreeNode*root){vector<vector<int>>vv;queue<TreeNode*>q;intlevelsize=0;if(root){q.push(root);levelsize=1;}while(!q.empty()){vector<int>v;while(levelsize--)////////////////////////////////levelsize作为内部的循环条件{TreeNode*thisnode=q.front();q.pop();v.push_back(thisnode->val);//操作if(thisnode->left)q.push(thisnode->left);if(thisnode->right)q.push(thisnode->right);}vv.push_back(v);//////////////////////////////////////////操作levelsize=q.size();/////////////////////////////插入结束之后的队列的size，就是下一层的节点个数}returnvv;}};155. 最小栈