栈和队列没有迭代器，他们只是容器适配器，不是容器。容器才有迭代器

栈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，vector或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的缝合

成员函数

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>即可

实现

位置：

• 在namespace lcj中

基础：

1. 通过类模板实现：template <class T, class Container = std::vector<T>, class Compare = Less<T> >
   1. class T：priority_queue中存的类型
   2. class Container = std::vector<T>：priority_queue 也是一种“容器适配器” ——>可能是由list，vector或deque容器（称为底层容器）变化而来
   3. class Compare = Less<T>：仿函数， （重载了 () 运算符的类，长得像函数，实际是对象。）。需要你在前面专门写两个仿函数（只有operator() 的类模板）：Greater和Less
2. push：堆插入，需要提前写向上调整算法void Adjustup(size_t child)
3. pop：删除堆顶元素，需要提前写向下调整算法：void Adjustdown(int parent)

完整代码

template<classT>///类模板——>得到的类中只有operator（）——>仿函数classLess///——>用来判断小于的仿函数{public:booloperator()(constT&x,constT&y){returnx<y;}};template<classT>classGreater///——>用来判断大于的仿函数{public:booloperator()(constT&x,constT&y){returnx>y;}};template<classT,classContainer=std::vector<T>,classCompare=Less<T>>///传参传的是仿函数（一种类）/// <summary>/// 在创建priorityqueue的时候，直接传仿函数就能判断是大根堆还是小根堆classpriority_queue{public:priority_queue(){}voidAdjustup(size_t child){intparent=(child-1)/2;while(child>0){if(comp(c[parent],c[child])){std::swap(c[child],c[parent]);child=parent;parent=(child-1)/2;}elsebreak;}}voidpush(constT&x){c.push_back(x);Adjustup(c.size()-1);}voidAdjustdown(intparent){intchild=parent*2+1;while(child<c.size()){if(child+1<c.size()&&comp(c[child],c[child+1]))++child;if(comp(c[parent],c[child])){std::swap(c[parent],c[child]);parent=child;child=parent*2+1;}else{break;}}}voidpop(){std::swap(c[0],c[c.size()-1]);c.pop_back();Adjustdown(0);}boolempty()const{returnc.size()==0;}size_tsize()const{returnc.size();}constT&top()const{returnc.front();}private:Container c;Compare comp;};};

拓展函数

make_heap(传begin和end)

• 可以将一个vector变成堆

sort_heap（创begin和end）

• 将堆进行堆排序（只能将堆进行堆排序‼️）

push_heap

pop_heap

题目

1.栈的压入、弹出序列

栈的压入、弹出序列

1. 入栈序列，每次入栈一个值
2. 如果入后的栈顶数据跟出栈序列匹配，——>出栈——>不断匹配，不断出栈
3. 入栈序列入完了，就结束了

2.二叉树的层序遍历

原题链接：二叉树的层序遍历

这个题目给的是二叉树，要求是输出一个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.进一步实现题目要求

在上面的条件下，我们一层一层输入数据

1. levelsize作为内部的循环条件
   1. 在“插入树根”的时候，levelsize置为1——因为第一层只有一个节点
      1. 然后的循环中，只将levelsize个节点的子节点插入队列中
   2. 插入结束之后的队列的size，就是下一层的节点个数

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;}};