• 【C++】stack、queue、priority_queue的模拟实现

    前言

            hello~大家好呀！欢迎大家进入我的C++系列笔记！上一篇的传送点在这里哦：【C++】vector从理解到深入_柒海啦的博客-CSDN博客 

            本篇主要简单介绍一下stack、queue、priority_queue的作用以及用法，然后就快速到具体的模拟实现。本篇会引入两个新的概念：适配器和仿函数，模拟实现的时候会具体介绍，我们开始吧~

    （红蓝赛高~）

    目录

    一、stack、queue、priority_queue的简单引入

    1.验证特性 

    2.适配器与仿函数

    二、stack、queue、priority_queue的模拟实现

    1.stack&queue的模拟实现

    总体思路：

    完整代码：

    2.priority_queue的模拟实现

    总体思路：

    完整代码：

    一、stack、queue、priority_queue的简单引入

    1.验证特性 

            stack

            *栈结构  特性：先进后出，后进先出

            queue

            *队列结构 特性：先进先出，后进后出

            priority_queue

            *优先级队列 特性：堆结构存储（默认大根堆），每次取出值为当前存储值的最大值（最小值） 

            比如使用一下程序来验证上述的特性：

    1. 	void test()
    2. 	{
    3. 		// 均为模板类 需要给定类型
    4. 		stack<int> s;
    5. 		queue<int> q;
    6. 		priority_queue<int> p;
    7.  
    8. 		// 1 -9 4 9 3 0 -2 60
    9. 		int arr[] = { 1, -9, 4, 9, 3, 0, -2, 60 };
    10. 		int len = sizeof arr / sizeof arr[0];
    11. 		for (int i = 0; i < len; ++i)
    12. 		{
    13. 			s.push(arr[i]);
    14. 			q.push(arr[i]);
    15. 			p.push(arr[i]);
    16. 		}
    17.  
    18. 		cout << "stack:\n";
    19. 		while (!s.empty())
    20. 		{
    21. 			cout << s.top() << " ";  // 60 -2 0 3 9 4 -9 1
    22. 			s.pop();
    23. 		}
    24. 		cout << endl;
    25. 		cout << "queue:\n";
    26. 		while (!q.empty())
    27. 		{
    28. 			cout << q.front() << " ";  // 1, -9, 4, 9, 3, 0, -2, 60
    29. 			q.pop();
    30. 		}
    31. 		cout << endl;
    32. 		cout << "priority_queue:\n";
    33. 		while (!p.empty())
    34. 		{
    35. 			cout << p.top() << " ";  // 60  9 4 3 1 0 -2 -9
    36. 			p.pop();
    37. 		}
    38. 		cout << endl;
    39. 	}

             可以发现是可以完美符合性质的哦。

            可是，我们查看文档，发现stack、queue、以及priority_queue都有一个：Container的模板参数，并且stack和queue给的都是deque，priority_queue给的是vector。另外priority_queue还有一个模板参数Compare，给的是less。

             这就是我们马上要开始的适配器和仿函数。

    2.适配器与仿函数

            适配器，顾名思义，就是适配的一种模式。

            在计算机编程中，适配器模式（有时候也称包装样式或者包装）将一个类的接口适配成用户所期待的。一个适配允许通常因为接口不兼容而不能在一起工作的类工作在一起，做法是将类自己的接口包裹在一个已存在的类中。（百度百科）

            而这里就是容器适配器。可以看到给的缺省参数是deque，那么相比底层代码操作的也就是deque（deque实际上是综合了vector和list的特点，适合作为stack和queue的容器适配器）。如果是利用C语言进行编程，那么就无法使用到如此便捷的容器，也只能像之前实现vector那样或者说实现线性表那样，自己开空间，赋值，扩容，深浅拷贝......

            既然有这个参数，也就是说明了我们使用别的容器也可以咯， 可以试下vector和list：

    1. 	void test2()
    2. 	{
    3. 		// 更改容器适配器
    4. 		stack<int, vector<int>> sv;
    5. 		stack<int, list<int>> sl;
    6. 		//queue> qv;
    7. 		queue<int, list<int>> ql;
    8.  
    9. 		int arr[] = { 1, 2, 3, 4, 5};
    10. 		int len = sizeof arr / sizeof arr[0];
    11. 		for (int i = 0; i < len; ++i)
    12. 		{
    13. 			sv.push(arr[i]);
    14. 			sl.push(arr[i]);
    15. 			//qv.push(arr[i]);
    16. 			ql.push(arr[i]);
    17. 		}
    18.  
    19. 		while (!sv.empty())
    20. 		{
    21. 			cout << sv.top() << " ";
    22. 			sv.pop();
    23. 		}
    24. 		cout << endl;
    25.  
    26. 		while (!sl.empty())
    27. 		{
    28. 			cout << sl.top() << " ";
    29. 			sl.pop();
    30. 		}
    31. 		cout << endl;
    32.  
    33.  
    34. 		//while (!qv.empty())
    35. 		//{
    36. 		//	cout << qv.front() << " ";
    37. 		//	qv.pop();
    38. 		//}
    39. 		//cout << endl;
    40.  
    41.  
    42. 		while (!ql.empty())
    43. 		{
    44. 			cout << ql.front() << " ";
    45. 			ql.pop();
    46. 		}
    47. 		cout << endl;
    48. 	}

             实际上，在queue的传递容器适配器的时候，底层实现了pop_front。而vector容器是不支持头插头删的。所以如果报错就说明此容器不适合。

             既然容器适配器就是我们实现此结构的一个容器，那么仿函数（compare）又是什么呢？

            仿函数(functor)，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

            是的，仿函数用起来就像一个函数一样，实际上是通过类进行实现的，然后在类中实现()运算符重载：

    1. 	// 比较仿函数
    2. 	template<class T>
    3. 	struct myless
    4. 	{
    5. 		// <
    6. 		bool operator()(const T& val1, const T& val2)
    7. 		{
    8. 			return val1 < val2;
    9. 		}
    10. 	};
    11.  
    12. 	void test4()
    13. 	{
    14. 		int a = 2, b = 3;
    15. 		myless<int> less;
    16. 		if (less(a, b))
    17. 			cout << "a < b" << endl;
    18. 		else cout << "a >= b" << endl;
    19. 	}

             compare是比较的意思，在优先级队列里面第三个模板参数也就意思在于我们传入的比较函数用来控制优先级是大根堆还是小根堆。而在算法库里，less表示两个数比较的(<),greater表示(>)。此时默认给的是less，代表大根堆的优先级，传入greater类型就表示小根堆了。

            下面简单测试一下：

    1. 	void test3()
    2. 	{
    3. 		// 测试仿函数类型传入
    4. 		priority_queue<int> q;  // 默认大根堆
    5. 		priority_queue<int, vector<int>, greater<int>> p;  // 指定小根堆
    6.  
    7. 		int arr[] = { 1, 2, 3, 4, 5 };
    8. 		int len = sizeof arr / sizeof arr[0];
    9. 		for (int i = 0; i < len; ++i)
    10. 		{
    11. 			q.push(arr[i]);
    12. 			p.push(arr[i]);
    13. 		}
    14.  
    15. 		while (!q.empty())
    16. 		{
    17. 			cout << q.top() << " ";  // 5 4 3 2 1
    18. 			q.pop();
    19. 		}
    20. 		cout << endl;
    21.  
    22. 		while (!p.empty())
    23. 		{
    24. 			cout << p.top() << " ";  // 1 2 3 4 5
    25. 			p.pop(); 
    26. 		}
    27. 		cout << endl;
    28. 	}

             可以发现果然如此，这样我们就能控制优先级的存储顺序了。

    二、stack、queue、priority_queue的模拟实现

    1.stack&queue的模拟实现

    总体思路：

            通过上面的引入，我们发现了，stack以及queue的底层均是用deque容器实现的，那么我们利用其结构，进行简单的push、pop、top、empty、size即可。

            stack是先进后出，后进先出。所以进即就是简单线性表的尾插，所以需要container适配器有push_back结构，出的话也就是每次都是尾删，也就是需要有pop_back结构。top就是简单的最后一个元素而已。

            queue同理，只不过保持结构先进先出，后进后出，需要push_back、pop_front....

            上述大体可用一下思路图解释：

     

    完整代码：

    // stack.h

    1. // 引入新内容 空间适配器 不再原生自己造，而是用其他封装好的空间
    2. 	// 保持结构 先进后出 后进先出即可
    3. 	template<class T, class Containers = std::deque>
    4. 	class stack
    5. 	{
    6. 	public:
    7. 		void push(const T& val)
    8. 		{
    9. 			v.push_back(val);  // 套用容器模板
    10. 		}
    11.  
    12. 		void pop()
    13. 		{
    14. 			v.pop_back();
    15. 		}
    16.  
    17. 		T& top()
    18. 		{
    19. 			return v.back();
    20. 		}
    21.  
    22. 		T top() const
    23. 		{
    24. 			return v.back();
    25. 		}
    26.  
    27. 		bool empty() const
    28. 		{
    29. 			return v.empty();
    30. 		}
    31.  
    32. 		size_t size() const
    33. 		{
    34. 			return v.size();
    35. 		}
    36.  
    37.  
    38. 	private:
    39. 		Containers v;
    40. 	};

    // queue.h

    1. 	template<class T, class Container = std::deque>
    2. 	class queue
    3. 	{
    4. 	public:
    5. 		void push(const T& val)
    6. 		{
    7. 			q.push_back(val);
    8. 		}
    9.  
    10. 		void pop()
    11. 		{
    12. 			q.pop_front();
    13. 		}
    14.  
    15. 		T& top()
    16. 		{
    17. 			return q.front();
    18. 		}
    19.  
    20. 		T top() const
    21. 		{
    22. 			return q.front();
    23. 		}
    24.  
    25. 		bool empty() const
    26. 		{
    27. 			return q.empty();
    28. 		}
    29.  
    30. 		size_t size()
    31. 		{
    32. 			return q.size();
    33. 		}
    34. 	private:
    35. 		Container q;
    36. 	};

     

    2.priority_queue的模拟实现

    总体思路：

            通过引入我们知道了，此优先级队列实际上也就是一个堆结构。在堆结构的时候利用数组结构构造一个之前数据结构以及详细讲过了，感兴趣的可以去看一下哦~：堆的c语言实现以及简单应用_柒海啦的博客-CSDN博客_堆在c语言

            以下实现使用适配器vector容器实现，首先是数组的随机访问（父子结点计算）、其次就是尾插效率也高，所以没有选择默认适配器deque。其次就是加入了仿函数代替原本的< >符号，这样在向上调整和向下调整的时候就可以控制优先级顺序了（大根堆和小根堆）。根据如上，我们也可以得到一个大致思路：

     

     

    完整代码：

    1. // 默认大根堆
    2. 	template<class T, class Container = std::vector, class Compare = std::less>  // 默认给的仿函数是 < 符号
    3. 	class priority_queue
    4. 	{
    5. 	public:
    6. 		priority_queue()
    7. 		{}
    8.  
    9. 		// 迭代器区间构造函数
    10. 		template<class InputIterator>
    11. 		priority_queue(InputIterator frist, InputIterator end)
    12. 		{
    13. 			// 先插入
    14. 			while (frist != end)
    15. 			{
    16. 				v.push_back(*frist);
    17. 				++frist;
    18. 			}
    19.  
    20. 			// 利用向下调整  利用从最后开始的父节点开始
    21. 			for (int i = (v.size() - 1 - 1) / 2; i >= 0; --i)
    22. 			{
    23. 				adjust_down(i);
    24. 			}
    25. 		}
    26.  
    27. 		void adjust_up(size_t child)
    28. 		{
    29. 			// 向上调整  logn
    30. 			size_t parent = (child - 1) / 2;
    31. 			while (child > 0)
    32. 			{
    33. 				// v[parent] < v[child]
    34. 				if (com(v[parent], v[child]))
    35. 				{
    36. 					std::swap(v[parent], v[child]); // 交换数据
    37. 					child = parent;
    38. 					parent = (child - 1) / 2;
    39. 				}
    40. 				else
    41. 					break;
    42. 			}
    43. 		}
    44.  
    45. 		void push(const T& val)
    46. 		{
    47. 			// 插入，保持堆结构，进行向上调整
    48. 			v.push_back(val);
    49. 			adjust_up(v.size() - 1);
    50. 		}
    51.  
    52. 		void adjust_down(size_t parent)
    53. 		{
    54. 			// 向下调整 logn
    55. 			size_t child = parent * 2 + 1;
    56. 			while (child < v.size())
    57. 			{
    58. 				// 防止越界 v[child] < v[child + 1]  
    59. 				if (child + 1 < v.size() && com(v[child], v[child + 1]))
    60. 					++child;
    61. 				if (com(v[parent], v[child]))
    62. 				{
    63. 					std::swap(v[parent], v[child]);
    64. 					parent = child;
    65. 					child = parent * 2 + 1;
    66. 				}
    67. 				else
    68. 					break;
    69. 			}
    70. 		}
    71.  
    72. 		void pop()
    73. 		{
    74. 			// 删除，删除堆顶元素，和尾元素交换，删除，向下调整
    75. 			std::swap(v[0], v[v.size() - 1]);
    76. 			v.pop_back();
    77.  
    78. 			adjust_down(0);  // 向下调整  保持下方为堆结构
    79. 		}
    80.  
    81. 		const T& top() const
    82. 		{
    83. 			return v[0];
    84. 		}
    85.  
    86. 		bool empty() const
    87. 		{
    88. 			return v.empty();
    89. 		}
    90.  
    91. 		size_t size() const
    92. 		{
    93. 			return v.size();
    94. 		}
    95. 	private:
    96. 		Container v;
    97. 		Compare com;
    98. 	};

            欢迎大佬补充~ 

  • 相关阅读:
    Linux系列之查找jar包安装目录
    试用copilot过程中问题解决
    Python基于词袋模型特征和TFIDF特征进行支持向量机模型中文邮件分类项目实战
    Vue3项目引入 vue-quill 编辑器组件并封装使用
    vue-admin-better前端页面-菜单-权限配置
    FPGA—可乐机拓展训练题（状态机）
    mybatis自定义类型控制器（TypeHandler）处理将字符串处理为集合
    【Opencv450】HOG+SVM 与Hog+cascade进行行人检测
    打造千万级流量秒杀第二十七课 单元测试：如何做单元测试和 benchmark？
    EMERSON艾默生变频器维修M600/M701/M702
  • 原文地址：https://blog.csdn.net/weixin_61508423/article/details/127064176