• C++stack&queue

    目录

    一、stack

    1.1 简要介绍

    1.2 小试身手

    1.3 模拟实现

    二、queue

    2.1 简要介绍

    2.2 小试身手        

    2.3 模拟实现

    三、deque

    3.1 简要介绍

    3.2 分析底层        

    四、priority_queue

    4.1 简要介绍

    4.2 小试身手

    4.3 模拟实现

    五、仿函数/函数对象 

    5.1 简要介绍        

    一、stack

    1.1 简要介绍

            鉴于读者如果阅读到本文，应该对上述函数（empty、size、push_back等）基本用法和功能有一定了解，因此不再赘述。读者可以在queue - C++ Reference (cplusplus.com)查询详细内容        

    1.2 小试身手

    150. 逆波兰表达式求值icon-default.png?t=N7T8https://leetcode.cn/problems/evaluate-reverse-polish-notation/参考解法：

    1. class Solution {
    2. public:
    3.     int evalRPN(vector& tokens) {
    4.         stack<int> st;
    5.         for (auto& s : tokens) 
    6.         {
    7.             if (s == "+" || s == "-" || s == "*" || s == "/") 
    8.             {
    9.                 int right = st.top();
    10.                 st.pop();
    11.                 int left = st.top();
    12.                 st.pop();
    13.                 switch(s[0])
    14.                 {
    15.                     case '+':
    16.                         st.push(left+right);
    17.                         break;
    18.                     case '-':
    19.                         st.push(left-right);
    20.                         break;
    21.                     case '*':
    22.                         st.push(left*right);
    23.                         break;
    24.                     case '/':
    25.                         st.push(left/right);
    26.                         break;
    27.                     default:
    28.                         break;
    29.                 }
    30.             }
    31.             else 
    32.             {
    33.                 st.push(stoi(s));
    34.             }
    35.         }
    36.         return st.top();
    37.     }
    38. };

            

    1.3 模拟实现

    1. #pragma once
    2.  
    3. #include 
    4. //#include 
    5.  
    6. namespace myContainer
    7. {    
    8.     template<class T, class Container = vector>    // 复用vector
    9.     //template>    // 复用deque
    10.     class stack
    11.     {
    12.     public:
    13.         
    14.         void push(const T& x)
    15.         {
    16.             _con.push_back(x);
    17.         }
    18.         void pop()
    19.         {
    20.             _con.pop_back();
    21.         }
    22.         T& top()
    23.         {
    24.             return _con.back();
    25.         }
    26.         const T& top()const
    27.         {
    28.             return _con.back();
    29.         }
    30.         size_t size()const
    31.         {
    32.             return _con.size();
    33.         }
    34.         bool empty()const
    35.         {
    36.             return _con.empty();
    37.         }
    38.     private:
    39.         Container _con;
    40.     };
    41. }

    效果演示：

            

            

    二、queue

    2.1 简要介绍

            

    2.2 小试身手        

    102. 二叉树的层序遍历icon-default.png?t=N7T8https://leetcode.cn/problems/binary-tree-level-order-traversal/参考解法：

    1. ​
    2. class Solution {
    3. public:
    4.     vectorint>> levelOrder(TreeNode* root) {
    5.         queue q;
    6.         int levelSize = 0;
    7.         if (root)
    8.         {
    9.             q.push(root);
    10.             levelSize = 1;
    11.         }
    12.  
    13.         vectorint>> vv;
    14.         while (!q.empty())
    15.         {
    16.             vector<int> v;
    17.             while (levelSize--)
    18.             {
    19.                 TreeNode* front = q.front();
    20.                 q.pop();
    21.                 v.push_back(front->val);
    22.                 if (front->left)
    23.                 {
    24.                     q.push(front->left);
    25.                 }
    26.                 if (front->right)
    27.                 {
    28.                     q.push(front->right);
    29.                 }
    30.             }
    31.  
    32.             vv.push_back(v);
    33.             // 队列中的数据个数就是下一层的数据个数
    34.             levelSize = q.size();
    35.         }
    36.         return vv;
    37.     }
    38. };
    39.  
    40. ​

            

    2.3 模拟实现

    1. #pragma once
    2.  
    3. #include 
    4.  
    5. namespace myContainer
    6. {
    7.     template<class T, class Container = deque>
    8.     class queue
    9.     {
    10.     public:
    11.         
    12.         void push(const T& x)
    13.         {
    14.             _con.push_back(x);
    15.         }
    16.         void pop()
    17.         {
    18.             _con.pop_front();
    19.         }
    20.         T& front()
    21.         {
    22.             return _con.front();
    23.         }
    24.         T& back()
    25.         {
    26.             return _con.back();
    27.         }
    28.         const T& front()const
    29.         {
    30.             return _con.front();
    31.         }
    32.         const T& back()const
    33.         {
    34.             return _con.back();
    35.         }
    36.         size_t size()const
    37.         {
    38.             return _con.size();
    39.         }
    40.         bool empty()const
    41.         {
    42.             return _con.empty();
    43.         }
    44.     private:
    45.         Container _con;
    46.     };
    47. }

    效果演示：

            

            

    三、deque

    deque -- 双队列        

    3.1 简要介绍

            deque结合了vector和list两者的优势并融合起来，同时必然地，deque比不过vector和list的优势区间，deque就好比一个六边形战士，杂而不精。deque的用法与vector和list几乎相同，这里不再赘述。先前我们模拟实现stack和queue的时候也都可以复用deque。      

    3.2 分析底层        

            

            

    四、priority_queue

    priority_queue -- 优先级队列

    4.1 简要介绍

    我们可以看到，优先级队列的底层实际上是vector，但是数据的排列方式更像是堆

    使用演示：

    4.2 小试身手

    215. 数组中的第K个最大元素icon-default.png?t=N7T8https://leetcode.cn/problems/kth-largest-element-in-an-array/参考解法：

    1. class Solution {
    2. public:
    3.     int findKthLargest(vector<int>& nums, int k) {
    4.         priority_queue<int> pq(nums.begin(), nums.end());
    5.         while (--k)
    6.             pq.pop();
    7.         return pq.top();
    8.     }
    9. };

            

    4.3 模拟实现

    1. template<class T>
    2. class Less
    3. {
    4. public:
    5.     bool operator()(const T& x, const T& y)
    6.     {
    7.         return x < y;
    8.     }
    9. };
    10.  
    11. template<class T>
    12. class Greater
    13. {
    14. public:
    15.     bool operator()(const T& x, const T& y)
    16.     {
    17.         return x > y;
    18.     }
    19. };
    20. // class Less 和 class Greater 都是函数对象，具体知识参考后文
    21.  
    22.  
    23. namespace my_pq
    24. {
    25. 	template<class T, class Container = vector, class Compare = Less>
    26. 	class priority_queue
    27. 	{
    28. 	public:
    29. 		priority_queue()
    30. 		{}
    31.  
    32. 		template <class InputIterator>
    33. 		priority_queue(InputIterator first, InputIterator last)
    34. 			:_con(first, last)
    35. 		{
    36. 			for (int i = (_con.size() - 2) / 2; i >= 0; --i)
    37. 			{
    38. 				adjust_down(i);
    39. 			}
    40. 		}
    41.  
    42. 		void adjust_up(int child)
    43. 		{
    44. 			int parent = (child - 1) / 2;
    45. 			while (child > 0)
    46. 			{
    47. 				if (com(_con[parent], _con[child]))
    48. 				{
    49. 					swap(_con[child], _con[parent]);
    50. 					child = parent;
    51. 					parent = (child - 1) / 2;
    52. 				}
    53. 				else
    54. 				{
    55. 					break;
    56. 				}
    57. 			}
    58. 		}
    59.  
    60. 		void adjust_down(int parent)
    61. 		{
    62. 			size_t child = parent * 2 + 1;
    63. 			while (child < _con.size())
    64. 			{
    65. 				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
    66. 				{
    67. 					++child;
    68. 				}
    69.  
    70. 				if (com(_con[parent], _con[child]))
    71. 				{
    72. 					swap(_con[child], _con[parent]);
    73. 					parent = child;
    74. 					child = parent * 2 + 1;
    75. 				}
    76. 				else
    77. 				{
    78. 					break;
    79. 				}
    80. 			}
    81. 		}
    82.  
    83. 		void push(const T& x)
    84. 		{
    85. 			_con.push_back(x);
    86. 			adjust_up(_con.size() - 1);
    87. 		}
    88.  
    89. 		void pop()
    90. 		{
    91. 			swap(_con[0], _con[_con.size() - 1]);
    92. 			_con.pop_back();
    93. 			adjust_down(0);
    94. 		}
    95.  
    96. 		const T& top()
    97. 		{
    98. 			return _con[0];
    99. 		}
    100.  
    101. 		bool empty()
    102. 		{
    103. 			return _con.empty();
    104. 		}
    105.  
    106. 		size_t size()
    107. 		{
    108. 			return _con.size();
    109. 		}
    110. 	private:
    111. 		Container _con;
    112.         Compare com;
    113. 	};
    114. }

    效果演示：
            

            

    五、仿函数/函数对象 

    5.1 简要介绍        

            仿函数实际上并不是函数，只是使用起来与函数非常相似，故称为仿函数。本质上它是一个函数对象，我们通过一段代码来了解一下        

            借助模板和仿函数，我们就可以减少函数指针的使用，当然它也可以作为函数参数，为其它函数所用

    void qsort (void* base, size_t num, size_t size,
            int (*compar)(const void*,const void*));        
        这样的函数指针谁也不喜欢用

    我们还可以把仿函数用在其它类中，例如上面模拟实现的 priority_queue

  • 相关阅读:
    Docker——作为非运维人员，数据卷我们需要了解哪些？
    基于内容的个性化推荐算法
    GAN笔记：利普希茨连续（Lipschitz continuity）
    React 函数组件导出自定义方法的办法说明
    springboot整合返回数据统一封装
    【正点原子STM32连载】 第四十二章 IIC实验 摘自【正点原子】APM32F407最小系统板使用指南
    Centos7如何配置实现网卡的切换
    【计算机方向】通信、算法、自动化、机器人、电子电气、计算机工程、控制工程、计算机视觉~~~~~合集！！！
    UE5如何实现语言本地化管理（中英文切换）
    集合篇---Queue集合
  • 原文地址：https://blog.csdn.net/weixin_72501602/article/details/133560319