• C++——stack和queue的使用和OJ练习题

     

    目录

    stack

    简介

    使用

    模拟实现

    queue

    简介

    使用

    模拟实现

    deque

    简介

    dqueue的优势

    相关OJ题目

    逆波兰表达式求值

     栈的压入、弹出序列

     最小栈

    stack

    简介

    1、stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行 元素的插入与提取操作。

    2、 stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

    3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下 操作：

    • empty：判空操作
    • back：获取尾部元素操作
    • push_back：尾部插入元素操作
    • pop_back：尾部删除元素操作

    4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。

    使用

    成员函数功能
    empty判断栈是否为空
    size获取栈中有效元素个数
    top获取栈顶元素
    push元素入栈
    pop元素出栈
    swap交换两个栈中的数据

    模拟实现

    1. namespace cl //防止命名冲突
    2. {
    3. 	template<class T, class Container = std::deque>
    4. 	class stack
    5. 	{
    6. 	public:
    7. 		//元素入栈
    8. 		void push(const T& x)
    9. 		{
    10. 			_con.push_back(x);
    11. 		}
    12. 		//元素出栈
    13. 		void pop()
    14. 		{
    15. 			_con.pop_back();
    16. 		}
    17. 		//获取栈顶元素
    18. 		T& top()
    19. 		{
    20. 			return _con.back();
    21. 		}
    22. 		const T& top() const
    23. 		{
    24. 			return _con.back();
    25. 		}
    26. 		//获取栈中有效元素个数
    27. 		size_t size() const
    28. 		{
    29. 			return _con.size();
    30. 		}
    31. 		//判断栈是否为空
    32. 		bool empty() const
    33. 		{
    34. 			return _con.empty();
    35. 		}
    36. 		//交换两个栈中的数据
    37. 		void swap(stack& st)
    38. 		{
    39. 			_con.swap(st._con);
    40. 		}
    41. 	private:
    42. 		Container _con;
    43. 	};
    44. }

    queue

    简介

    1.队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端 提取元素。

    2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。

    3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操 作: empty：检测队列是否为空 size：返回队列中有效元素的个数 front：返回队头元素的引用 back：返回队尾元素的引用 push_back：在队列尾部入队列 pop_front：在队列头部出队列

    4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标 准容器deque。

    使用

    成员函数功能
    empty判断队列是否为空
    size获取队列中有效元素个数
    front获取队头元素
    back获取队尾元素
    push队尾入队列
    pop队头出队列
    swap交换两个队列中的数据

    模拟实现

    1. namespace cl //防止命名冲突
    2. {
    3. 	template<class T, class Container = std::deque>
    4. 	class queue
    5. 	{
    6. 	public:
    7. 		//队尾入队列
    8. 		void push(const T& x)
    9. 		{
    10. 			_con.push_back(x);
    11. 		}
    12. 		//队头出队列
    13. 		void pop()
    14. 		{
    15. 			_con.pop_front();
    16. 		}
    17. 		//获取队头元素
    18. 		T& front()
    19. 		{
    20. 			return _con.front();
    21. 		}
    22. 		const T& front() const
    23. 		{
    24. 			return _con.front();
    25. 		}
    26. 		//获取队尾元素
    27. 		T& back()
    28. 		{
    29. 			return _con.back();
    30. 		}
    31. 		const T& back() const
    32. 		{
    33. 			return _con.back();
    34. 		}
    35. 		//获取队列中有效元素个数
    36. 		size_t size() const
    37. 		{
    38. 			return _con.size();
    39. 		}
    40. 		//判断队列是否为空
    41. 		bool empty() const
    42. 		{
    43. 			return _con.empty();
    44. 		}
    45. 		//交换两个队列中的数据
    46. 		void swap(queue& q)
    47. 		{
    48. 			_con.swap(q._con);
    49. 		}
    50. 	private:
    51. 		Container _con;
    52. 	};
    53. }

    deque

    简介

     我们通过看文档会发现这个名为双端队列的容器居然如此强大，不仅弥补了vector和list的缺点，更是都具有vector和list的优点。当然，我们也知道，它肯定不会是无敌的存在，那么我们就不会再学习vector和list了。

    它作为我们实现stack和queue的缺省参数，肯定有它的存在意义。

    它通过一个中控指针数组来完成了很多效率很低的操作！

    dqueue的优势

    在实现stack与vector相比：

    扩容代码不大，不需要拷贝数据浪费空间也不多。

    ​​​​​在实现stack与list相比：

    cpu高速cache命中。其次不会频繁申请小块空间。申请和释放空间次数少代价低。

    在实现queue与list相比：

    cpu高速cache命中。其次不会频繁申请小块空间。申请和释放空间次数少代价低。

    总结：

    deque适合头尾插入删除，但是中间插入删除，和随机访问效率都差强人意。所以要高频随机访问还得是vector，要任意位置插入删除，还得是list。

    相关OJ题目

    解析见代码中的注释！

    逆波兰表达式求值

    力扣icon-default.png?t=M85Bhttps://leetcode.cn/problems/evaluate-reverse-polish-notation/

     

    1. class Solution {
    2. public:
    3.     int evalRPN(vector& tokens) {
    4.         stack<int> st;
    5.         for(const auto& str : tokens)
    6.         //利用范围for进行遍历
    7.         {
    8.             if(str=="+"||str=="-"||str=="*"||str=="/")
    9.             //如果是操作符就进行操作
    10.             {
    11.                 long right=st.top();
    12.                 st.pop();
    13.                 long left=st.top();
    14.                 st.pop();
    15.             switch(str[0])
    16.             //这里不能填写str因为switch只能支持整型
    17.             //因此直接取它的第一个字符
    18.             {
    19.                 case '+':
    20.                 st.push(left+right);
    21.                 break;
    22.  
    23.                 case '-':
    24.                 st.push(left-right);
    25.                 break;
    26.  
    27.                 case '*':
    28.                 st.push(left * right);
    29.                 break;
    30.  
    31.                 case '/':
    32.                 st.push(left/right);
    33.                 break;
    34.  
    35.                 default :
    36.                 assert(false);
    37.             }
    38.             }
    39.             else
    40.             {
    41.                 st.push(stoi(str));
    42.                 //将tokens中的字符串转为int型存放入栈中
    43.             }
    44.         }
    45.         return st.top();
    46.         //最终栈中剩下的数就是我们所需要的
    47.     }
    48. };

     栈的压入、弹出序列

    栈的压入、弹出序列_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力icon-default.png?t=M85Bhttps://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

    1. class Solution {
    2. public:
    3.     bool IsPopOrder(vector<int> pushV,vector<int> popV) {
    4.         stack<int> st;
    5.         //定义一个栈用来实现
    6.         size_t pushi=0,popi=0;
    7.         //分别用来遍历pushV和popV
    8.         while(pushisize())
    9.         {
    10.             st.push(pushV[pushi]);
    11.             //将第一个vector中的数据入栈
    12.             pushi++;
    13.             //更新pushi
    14.             while(!st.empty()&&st.top()==popV[popi])
    15.             {
    16.                 st.pop();
    17.                 popi++;
    18.             }
    19.         }
    20.         return popi==popV.size();
    21.  
    22.  
    23.         
    24.     }
    25. };

     最小栈

    力扣icon-default.png?t=M85Bhttps://leetcode.cn/problems/min-stack/ 

    1. class MinStack {
    2. public:
    3.  
    4.     MinStack() 
    5.     {}
    6.     
    7.     void push(int val) {
    8.         St.push(val);
    9.         if(minSt.empty()||val<=minSt.top())
    10.         {
    11.             minSt.push(val);
    12.         }
    13.  
    14.     }
    15.     
    16.     void pop() {
    17.         if(St.top()==minSt.top())
    18.         {
    19.             minSt.pop();
    20.         }
    21.         St.pop();
    22.  
    23.     }
    24.     
    25.     int top() {
    26.         return St.top();
    27.  
    28.     }
    29.     
    30.     int getMin() {
    31.         return minSt.top();
    32.  
    33.     }
    34. private:
    35.     stack<int> minSt;
    36.     stack<int> St;
    37. };
    38.  
    39. /**
    40.  * Your MinStack object will be instantiated and called as such:
    41.  * MinStack* obj = new MinStack();
    42.  * obj->push(val);
    43.  * obj->pop();
    44.  * int param_3 = obj->top();
    45.  * int param_4 = obj->getMin();
    46.  */

     

  • 相关阅读:
    vue3 ts pinia openapi vue-query pnpm docker前端架构小记
    < Python全景系列-5 > 解锁Python并发编程：多线程和多进程的神秘面纱揭晓
    模拟建造游戏：城市:天际线Cities: Skylines for Mac/win中文原生版
    Cilium 系列-2-Cilium 快速安装
    Docker 入门
    Doris 1.1.2版本部署
    Flink的状态一致性
    GBASE 8s onconfig文件格式
    【线性代数】第五章-线性方程组
    计算3D目标框的NMS
  • 原文地址：https://blog.csdn.net/m0_57249790/article/details/127756092