stack queue目录stack queue一、stack queue二、Stack的模拟实现三、Queue的模拟实现四、相关试题试题1最小栈试题2栈的压入、弹出序列试题3二叉树的层序遍历五、容器适配器六、deque七、优先级队列priority_queue八、仿函数函数对象九、与堆相关的算法一、stack queue容器适配器adaptor它们的底层容器为deque用stack实现后进先出用queue实现先进先出二、Stack的模拟实现#pragma once #include deque //templateclass T //class stack //{ //private: // T* _a; // size_t _top; // size_t _capacity; //}; namespace bit { //用Container适配器适配转换出stack //templateclass T,class Container //可以给模板参数设置缺省值 //templateclass T, class Container vectorT templateclass T, class Container dequeT class stack { public: //压栈 void push(const T x) { _con.push_back(x); } //出栈 void pop() { _con.pop_back(); } //获取栈顶数据 const T top() const { return _con.back(); } //计算数据个数 size_t size() const { return _con.size(); } //判空 bool empty() const { return _con.empty(); } private: Container _con; }; }三、Queue的模拟实现#pragma once #include deque namespace bit { templateclass T, class Container dequeT class queue { public: //入队 void push(const T x) { _con.push_back(x); } //出队 void pop() { _con.pop_front(); } //获取队首数据 const T front() const { return _con.front(); } //获取队尾数据 const T back() const { return _con.back(); } //计算数据个数 size_t size() const { return _con.size(); } //判空 bool empty() const { return _con.empty(); } private: Container _con; }; }四、相关试题试题1最小栈题目内容设计一个支持pushpoptop操作并且能在常数时间内检索到最小元素的栈实现MinStack类MinStack()初始化堆栈对象void push(int val)将元素val推入堆栈void pop()删除堆栈顶部的元素int top()获取堆栈顶部元素int getMin()获取堆栈中的最小元素class MinStack { public: MinStack() { } void push(int val) { _st.push(val); if(_minst.empty() || val _minst.top()) { _minst.push(val); } } void pop() { if(_st.top() _minst.top()) { _minst.pop(); } _st.pop(); } int top() { return _st.top(); } int getMin() { return _minst.top(); } private: stackint _st; stackint _minst; };试题2栈的压入、弹出序列题目内容输入两个整数序列第一个序列表示栈的压入顺序判断第二个序列是否可能为该栈的弹出顺序假设压入栈的所有数字均不相等例如序列1,2,3,4,5是某栈的压入顺序序列4,5,3,2,1是该压栈序列对应的一个弹出序列但4,3,5,1,2就不可能是该压栈序列的弹出序列示例1输入[1,2,3,4,5][4,5,3,2,1]返回true示例2输入[1,2,3,4,5][4,3,5,1,2]返回falseclass Solution { public: /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param pushV int整型vector * param popV int整型vector * return bool布尔型 */ bool IsPopOrder(vectorint pushV, vectorint popV) { size_t popi 0; stackint st; for(autoe : pushV) { //入栈 st.push(e); //与出栈序列匹配 while(!st.empty() st.top() popV[popi]) { st.pop(); popi; } } return st.empty(); } };试题3二叉树的层序遍历题目内容给你二叉树的根节点 root返回其节点值的层序遍历即逐层地从左到右访问所有节点示例输入root [3,9,10,null,null,15,7]输出[[3],[9,20],[15,7]]class Solution { public: vectorvectorint levelOrder(TreeNode* root) { vectorvectorint vv; queueTreeNode* q; //当前层的数据个数 int levelSize 0; if(root) { q.push(root); levelSize 1; } while(!q.empty()) { vectorint v; //当前层数据个数控制一层一层出 while(levelSize--) { TreeNode* front q.front(); q.pop(); v.push_back(front-val); if(front-left) { q.push(front-left); } if(front-right) { q.push(front-right); } } vv.push_back(v); //当前层出完下一层都进队列队列的个数就是下一层的数据个数 levelSize q.size(); } return vv; } };五、容器适配器适配器一种设计模式23种包括迭代器模式设计模式一套被反复使用的多数人知晓的进过分类编目的代码设计经验的总结作用将一个类的接口转换成客户希望的另外一个接口stack和queue这些依赖于vectorlist实现的数据结构它们的模板都需要有一个适配器来进行选择是用链式结构来存储数据还是用顺序表结构来存储数据六、dequevector与list的缝合vector优点尾插尾删效率高支持高效的下标随机访问物理空间连续高速缓存利用率高物理空间连续缺点空间不够需要扩容造成空间浪费和数据拷贝头部与中间的插入删除效率低list优点按需申请释放空间不需要扩容任意位置的插入删除缺点不支持下标的随机访问deque的结构图头插尾插效率高既没有像链表频繁地申请空间也没有像顺序表需要大量扩容下标访问效率较好但不如顺序表中间插入删除效率低需要挪动数据时间复杂度为O(N)七、优先级队列priority_queue底层结构堆用vector作默认适配容器优先级队列的使用top默认大的值优先级高#define _CRT_SECURE_NO_WARNINGS 1 #include iostream using namespace std; #include queue int main() { //默认建大堆 priority_queueint, vectorint pq; //使用仿函数建小堆priority_queueint,vectorint,greaterint pq; pq.push(4); pq.push(1); pq.push(5); pq.push(7); pq.push(9); while (!pq.empty()) { cout pq.top() ; pq.pop(); } cout endl; return 0; }模拟实现#pragma once #include vector namespace bit { templateclass T class Less { public: bool operator()(const T x, const T y) { return x y; } }; templateclass T class Greater { public: bool operator()(const T x, const T y) { return x y; } }; templateclass T, class Container vectorT,class Compare LessT class priority_queue { public: void AdjustUp(int child) { int parent (child - 1) / 2; while (child 0) { Compare com; if (com(_con[parent],_con[child])) { swap(_con[child], _con[parent]); child parent; parent (child - 1) / 2; } else { break; } } } void AdjustDown(int parent) { int child parent * 2 1; Compare com; while (child _con.size()) { if (child 1 _con.size() com(_con[child],_con[child 1])) { child; } if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); parent child; child parent * 2 1; } else { break; } } } void push(const T x) { _con.push_back(x); AdjustUp(_con.size() - 1); } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } const T top() { return _con[0]; } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; }; }八、仿函数函数对象本质是一个类这个类重载了operator()它的对象可以像函数一样调用需要手动实现仿函数的情况类类型不支持比较大小支持比较大小但比较的逻辑不是你想要的#define _CRT_SECURE_NO_WARNINGS 1 #include iostream using namespace std; templateclass T class Less { public: bool operator()(const T x, const T y) { return x y; } }; templateclass T class Greater { public: bool operator()(const T x, const T y) { return x y; } }; //升序 //降序 templateclass Compare void BubbleSort(int* a, int n, Compare com) { for (int j 0; j n; j) { int flag 0; for (int i 1; i n - j; i) { //if (a[i] a[i - 1]) if(com(a[i],a[i - 1])) { swap(a[i - 1], a[i]); flag 1; } } if (flag 0) { break; } } } int main() { Lessint LessFunc;//对象 Greaterint GreaterFunc;//对象 //函数对象 cout LessFunc(1, 2) endl; //本质 cout LessFunc.operator()(1,2) endl; int a[] { 9,1,2,5,7,4,6,3 }; BubbleSort(a, 8, LessFunc); BubbleSort(a, 8, GreaterFunc); //除了传有名对象 //也可以传匿名对象 BubbleSort(a, 8, Lessint()); BubbleSort(a, 8, Greaterint()); return 0; }九、与堆相关的算法#define _CRT_SECURE_NO_WARNINGS 1 #include iostream #include algorithm using namespace std; int main() { int myints[] { 10,20,30,5,15 }; sort(myints, myints 5); std::vectorint v(myints, myints 5); //判断是否是堆 cout is_heap(v.begin(), v.end()) endl; //物理上连续原生指针就是天然的迭代器 cout is_heap(myints, myints 5) endl; //默认建大堆 make_heap(v.begin(), v.end()); //判断是否是堆 cout is_heap(v.begin(), v.end()) endl; //堆排序 std::sort_heap(v.begin(), v.end()); for (auto e : v) { cout e ; } cout endl; return 0; }