栈和队列没有迭代器他们只是容器适配器不是容器。容器才有迭代器文章目录栈Stack头文件stack本质成员函数实现stack.h按需实例化队列queue本质成员函数实现queue.hdeque双端队列成员函数priority_queue优先级队列本质头文件queue‼️成员函数应用大根堆小根堆实现位置基础完整代码拓展函数题目1.栈的压入、弹出序列2.二叉树的层序遍历1.实现二叉树层序遍历2.进一步实现题目要求栈Stack➡️有关 栈的实现/二叉树的实现 的知识可以点击这里进行学习⬅️头文件stack本质templateclassT,classContainerdequeTclassstack;后进先出栈是一种“容器适配器” ——栈可能是由listvector或deque容器称为底层容器变化而来底层容器如果不传默认是deque成员函数(constructor)Construct stack (public member function )emptyTest whether container is empty (public member function )sizeReturn size (public member function )topAccess next element (public member function )pushInsert element (public member function )emplaceConstruct and insert element (public member function )popRemove top element (public member function )swapSwap contents (public member function )实现stack.h#pragmaoncenamespacelcj{templateclassT,classContainervectorTclassstack{public:/// summary/// 不用写构造函数因为container是自定义类型会调用对应的构造函数/// /summary///voidpush(constTx){_con.push_back(x);}voidpop(){_con.pop_back();}constTtop()const{return_con.back();///不能通过‘[ ]’访问当container是list时没有这个功能}size_tsize()const{return_con.size();}boolempty()const{return_con.size()0;}private:Container _con;};}按需实例化在.h中写的类中的成员函数并不会全都被实例化编译器只实例化使用的接口——编译器不检查细节语法有时候不会报错但是使用的时候还是会发生错误——写函数的时候还是要写一个检查一个队列queue本质templateclassT,classContainerdequeTclassqueue;先进先出也是一种“容器适配器” ——栈可能是由listvector或deque容器称为底层容器变化而来底层容器如果不传默认是deque成员函数(constructor)Construct queue (public member function )emptyTest whether container is empty (public member function )sizeReturn size (public member function )frontAccess next element (public member function )backAccess last element (public member function )pushInsert element (public member function )emplaceConstruct and insert element (public member function )popRemove next element (public member function )swapSwap contents (public member function )实现queue.h#pragmaoncenamespacelcj{templateclassT,classContainerlistTclassqueue{public:/// summary/// 不用写构造函数因为container是自定义类型会调用对应的构造函数/// /summary///voidpush(constTx){_con.push_back(x);}voidpop(){_con.pop_front();}constTback()const{return_con.back();///不能通过‘[ ]’访问当container是list时没有这个功能}constTfront()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 容器赋值公有成员函数迭代器Iteratorsbegin返回指向容器起始位置的迭代器公有成员函数end返回指向容器末尾位置的迭代器公有成员函数rbegin返回指向容器反向起始位置的反向迭代器公有成员函数rend返回指向容器反向末尾位置的反向迭代器公有成员函数cbegin返回指向容器起始位置的 const 迭代器公有成员函数cend返回指向容器末尾位置的 const 迭代器公有成员函数crbegin返回指向容器反向起始位置的 const 反向迭代器公有成员函数crend返回指向容器反向末尾位置的 const 反向迭代器公有成员函数容量管理Capacitysize返回容器当前存储的元素数量公有成员函数max_size返回容器可容纳的最大元素数量公有成员函数resize改变容器的大小公有成员函数empty检测容器是否为空公有成员函数shrink_to_fit释放容器未使用的内存收缩到适配当前元素大小公有成员函数元素访问Element accessoperator[]访问容器中指定下标位置的元素公有成员函数at访问容器中指定下标位置的元素带越界检查公有成员函数front访问容器的第一个元素公有成员函数back访问容器的最后一个元素公有成员函数内容修改Modifiersassign给容器重新赋值覆盖原有内容公有成员函数push_back在容器末尾添加一个元素公有成员函数push_front在容器开头插入一个元素公有成员函数pop_back删除容器末尾的最后一个元素公有成员函数pop_front删除容器开头的第一个元素公有成员函数insert在容器指定位置插入元素公有成员函数erase删除容器指定位置的元素公有成员函数swap交换两个 deque 容器的内容公有成员函数clear清空容器内的所有元素公有成员函数emplace_front在容器开头直接构造并插入一个元素公有成员函数emplace_back在容器末尾直接构造并插入一个元素公有成员函数分配器Allocatorget_allocator获取容器使用的内存分配器公有成员函数非成员函数重载relational operatorsdeque 容器的关系比较运算符函数模板swap交换两个 deque 容器的内容函数模板priority_queue优先级队列➡️有关 堆和二叉树 的知识可以点击这里进行学习【数据结构精讲】堆与二叉树从底层原理到代码落地堆的构建 / 调整 / 排序 二叉树遍历 / 操作附完整 C 源码 LeetCode 题解⬅️本质templateclassT,classContainervectorT,classComparelesstypenameContainer::value_typeclasspriority_queue;就是个堆默认是大根堆也是容器适配器默认是vector因为下标访问用的多头文件queue‼️不是单独的‼️成员函数(constructor)Construct priority queue (public member function )emptyTest whether container is empty (public member function )sizeReturn size (public member function )topAccess top element (public member function )pushInsert element (public member function )emplaceConstruct and insert element (public member function )popRemove top element (public member function )swapSwap contents (public member function )应用大根堆priority_queueint, vectorint, lessint pq;中的lessint也可以不写是默认的这时候是大根堆——打印出来是从大到小的#includequeueusingnamespacestd;///必须在#includestack.h的前面这样如果stack.h里面有std::cout这种函数也没问题intmain(){priority_queueint,vectorint,lessintpq;pq.push(3);pq.push(777);pq.push(66);pq.push(88);pq.push(22);pq.push(9);while(!pq.empty()){coutpq.top()endl;pq.pop();}return0;}小根堆——从小到大打印只需要改lessint为greaterint即可实现位置在namespace lcj中基础通过类模板实现template class T, class Container std::vectorT, class Compare LessT class Tpriority_queue中存的类型class Container std::vectorTpriority_queue 也是一种“容器适配器” ——可能是由listvector或deque容器称为底层容器变化而来class Compare LessT仿函数 重载了 () 运算符的类长得像函数实际是对象。。需要你在前面专门写两个仿函数只有operator() 的类模板Greater和Lesspush堆插入需要提前写向上调整算法void Adjustup(size_t child)pop删除堆顶元素需要提前写向下调整算法void Adjustdown(int parent)完整代码templateclassT///类模板——得到的类中只有operator——仿函数classLess///——用来判断小于的仿函数{public:booloperator()(constTx,constTy){returnxy;}};templateclassTclassGreater///——用来判断大于的仿函数{public:booloperator()(constTx,constTy){returnxy;}};templateclassT,classContainerstd::vectorT,classCompareLessT///传参传的是仿函数一种类/// summary/// 在创建priorityqueue的时候直接传仿函数就能判断是大根堆还是小根堆classpriority_queue{public:priority_queue(){}voidAdjustup(size_t child){intparent(child-1)/2;while(child0){if(comp(c[parent],c[child])){std::swap(c[child],c[parent]);childparent;parent(child-1)/2;}elsebreak;}}voidpush(constTx){c.push_back(x);Adjustup(c.size()-1);}voidAdjustdown(intparent){intchildparent*21;while(childc.size()){if(child1c.size()comp(c[child],c[child1]))child;if(comp(c[parent],c[child])){std::swap(c[parent],c[child]);parentchild;childparent*21;}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();}constTtop()const{returnc.front();}private:Container c;Compare comp;};};拓展函数make_heap(传begin和end)可以将一个vector变成堆sort_heap创begin和end将堆进行堆排序只能将堆进行堆排序‼️push_heappop_heap题目1.栈的压入、弹出序列栈的压入、弹出序列入栈序列每次入栈一个值如果入后的栈顶数据跟出栈序列匹配——出栈——不断匹配不断出栈入栈序列入完了就结束了2.二叉树的层序遍历原题链接二叉树的层序遍历这个题目给的是二叉树要求是输出一个vectorvectorint类型的数组1.实现二叉树层序遍历队列存节点指针下来一个节点放一个节点的子节点创造一个队列存的是TreeNode*类型的指针queueTreeNode* q;插入树根q.push(root);while循环遍历条件 队列中还有元素while(!q.empty())循环体得到队列头节点TreeNode* thisnodeq.front();头删q.pop();操作……将这个节点的孩子放进队列​if(thisnode-left)​q.push(thisnode-left);​if(thisnode-right)​q.push(thisnode-right);queueTreeNode*q;intlevelsize0;if(root){q.push(root);}while(!q.empty()){TreeNode*thisnodeq.front();q.pop();//对thisnode的操作if(thisnode-left)q.push(thisnode-left);if(thisnode-right)q.push(thisnode-right);}2.进一步实现题目要求在上面的条件下我们一层一层输入数据levelsize作为内部的循环条件在“插入树根”的时候levelsize置为1——因为第一层只有一个节点然后的循环中只将levelsize个节点的子节点插入队列中插入结束之后的队列的size就是下一层的节点个数classSolution{public:vectorvectorintlevelOrder(TreeNode*root){vectorvectorintvv;queueTreeNode*q;intlevelsize0;if(root){q.push(root);levelsize1;}while(!q.empty()){vectorintv;while(levelsize--)////////////////////////////////levelsize作为内部的循环条件{TreeNode*thisnodeq.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);//////////////////////////////////////////操作levelsizeq.size();/////////////////////////////插入结束之后的队列的size就是下一层的节点个数}returnvv;}};