• 【C++/STL】stack和queue(容器适配器、优先队列、双端队列)

      🌈个人主页：秦jh_-CSDN博客
    🔥 系列专栏：https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482

    9efbcbc3d25747719da38c01b3fa9b4f.gif

    目录

    stack的介绍

    stack常用接口

     queue的介绍

    queue的使用 

     容器适配器

    什么是适配器 

    STL标准库中stack和queue的底层结构 

    deque的简单介绍 

    deque的缺陷

    STL的六大组件

    模拟实现

    stack

    queue

     优先队列

    常用接口

    简单使用

    sort函数排序

    模拟实现(简单版)

    自定义类型

    测试完整代码

     queue.h

    stack.h

    test.cpp

    前言

        💬 hello! 各位铁子们大家好哇。

                 今日更新了stack、queue的相关内容
        🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

    stack的介绍

    1. stack是一种容器适配器。
    2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素。
    3. stack的底层容器应该支持以下操作：empty 、back、push_back、pop_back
    4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器， 默认情况下使用deque。 

    stack常用接口

     queue的介绍

    1. 队列是一种容器适配器。
    2. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty，size，front，back，push_back，pop_front。
    3. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。（vector不满足，因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低）

    queue的使用 

     容器适配器

    什么是适配器 

    适配器是一种设计模式，该种模式是将一个类的接口转换成客户希望的另外一个接口。 

    STL标准库中stack和queue的底层结构 

    虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque。

    deque的简单介绍 

    deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

    deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。

    deque的缺陷

    • 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素。
    • 与list比较，其底层是连续空间，空间利用率比较高。
    • 在实际中，需要线性结构时，大多数情况下优先考虑vector和list，目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

    STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

    1.  stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
    2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长 时，deque不仅效率高，而且内存使用率高。

    STL的六大组件

    模拟实现

    stack

    queue

    stack和queue的模拟实现基本一样。

     优先队列

    • 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

    优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

    常用接口

    简单使用

    我们插入时，是乱序插入的，取出来却是降序的。因为优先队列默认是大堆，不过它并没有在里面进行排序，它在里面依旧是乱序的，只是取出来的是堆顶，是最大的。

    如果我们想让他是小堆，就得改一下他的仿函数。 

    sort函数排序

    sort排序默认是升序，想要降序就得改仿函数。注意这里是函数模板，要传对象，所以有括号。而优先队列那里没有括号，是因为那里是类模板。

    在C语言中，我们排序如果要控制升序降序，传的是函数指针。而这里我们传的是仿函数。

    上方是仿函数的简单模拟。 

    模拟实现(简单版)

    1. 	template<class T,class Container=vector>
    2. 	class priority_queue
    3. 	{
    4. 	public:
    5. 		void adjust_up(size_t child)
    6. 		{
    7. 			int parent = (child - 1) / 2;
    8. 			while (child > 0)
    9. 			{
    10. 				if (_con[child] > _con[parent])
    11. 				{
    12. 					swap(_con[child], _con[parent]);
    13. 					child = parent;
    14. 					parent = (child - 1) / 2;
    15. 				}
    16. 				else
    17. 				{
    18. 					break;
    19. 				}
    20. 			}
    21. 		}
    22.  
    23. 		void push(const T& x)
    24. 		{
    25. 			_con.push_back(x);
    26. 			adjust_up(_con.size() - 1);
    27. 		}
    28.  
    29. 		void adjust_down(size_t parent)
    30. 		{
    31. 			size_t child = parent * 2 + 1;
    32. 			while (child<_con.size()) 
    33. 			{
    34. 				if (child + 1 < _con.size() && _con[child + 1] > _con[child])
    35. 				{
    36. 					++child;
    37. 				}
    38.  
    39. 				if (_con[child] > _con[parent])
    40. 				{
    41. 					swap(_con[child], _con[parent]);
    42. 					parent = child;
    43. 					child = parent * 2 + 1;
    44. 				}
    45. 				else
    46. 				{
    47. 					break;
    48. 				}
    49. 			}
    50. 		}
    51.  
    52. 		void pop()
    53. 		{
    54. 			swap(_con[0], _con[_con.size() - 1]);
    55. 			_con.pop_back();
    56. 			adjust_down(0); 
    57. 		}
    58.  
    59. 		bool empty()
    60. 		{
    61. 			return _con.empty();
    62. 		}
    63.  
    64. 		size_t size()
    65. 		{
    66. 			return _con.size();
    67. 		}
    68.  
    69. 		const T& top()
    70. 		{
    71. 			return _con[0];
    72. 		}
    73. 	private:
    74. 		Container _con;
    75. 	};

    上面是默认的大堆。如果想要它是小堆，要怎么办呢?

    如下图修改：

     这样做的优势是，我们只需要传不同的仿函数即可修改为升序或者降序。不传默认是大堆。

    自定义类型

    如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

    上面是日期类，Date类型，比较时，只需要重载运算符即可。如果我们传的是Date*又该怎么办呢？

    可以看到，第二行每次的结果都是不一样的。空间并不一定越晚开，地址就越高。 这里不能通过重载运算符解决，因为重载必须包含自定义类型，而指针是内置类型。解决方法是：专门写一个仿函数。

    从这个样例可以得出，仿函数不仅可以控制比较逻辑，还可以控制如何比较。

    测试完整代码

     queue.h

    1. #pragma once
    2. #include
    3.  
    4. namespace qjh
    5. {
    6. 	template<class T, class Container = deque> //有了Container就可以根据需要实现链式栈或数组栈了
    7. 	class queue
    8. 	{
    9. 	public:
    10. 		void push(const T& x)
    11. 		{
    12. 			_con.push_back(x);
    13. 		}
    14.  
    15. 		void pop()
    16. 		{
    17. 			_con.pop_front();
    18. 		}
    19.  
    20. 		size_t size()
    21. 		{
    22. 			return _con.size();
    23. 		}
    24.  
    25. 		bool empty()
    26. 		{
    27. 			return _con.empty();
    28. 		}
    29.  
    30. 		const T& front()
    31. 		{
    32. 			return _con.front();
    33. 		}
    34.  
    35. 		const T& back()
    36. 		{
    37. 			return _con.back();
    38. 		}
    39. 	private:
    40. 		Container _con;
    41. 	};
    42.  
    43. 	template<class T>
    44. 	struct less
    45. 	{
    46. 		bool operator()(const T& x, const T& y)
    47. 		{
    48. 			return x < y;
    49. 		}
    50. 	};
    51.  
    52. 	template<class T>
    53. 	struct greater
    54. 	{
    55. 		bool operator()(const T& x, const T& y)
    56. 		{
    57. 			return x > y;
    58. 		}
    59. 	};
    60.  
    61. 	//大堆
    62. 	template<class T,class Container=vector,class Compare=less>
    63. 	class priority_queue
    64. 	{
    65. 	public:
    66. 		void adjust_up(size_t child)
    67. 		{
    68. 			Compare com; 
    69. 			int parent = (child - 1) / 2;
    70. 			while (child > 0)
    71. 			{
    72. 				//if (_con[child] > _con[parent])
    73. 				//if (_con[parent]<_con[child] )
    74. 				if (com(_con[parent] , _con[child]))
    75. 				{	
    76. 					swap(_con[child], _con[parent]);
    77. 					child = parent;
    78. 					parent = (child - 1) / 2;
    79. 				}
    80. 				else
    81. 				{
    82. 					break;
    83. 				}
    84. 			}
    85. 		}
    86.  
    87. 		void push(const T& x)
    88. 		{ 
    89. 			_con.push_back(x);
    90. 			adjust_up(_con.size() - 1);
    91. 		}
    92.  
    93. 		void adjust_down(size_t parent)
    94. 		{
    95. 			Compare com;
    96. 			size_t child = parent * 2 + 1;
    97. 			while (child<_con.size()) 
    98. 			{
    99. 				//if (child + 1 < _con.size() && _con[child + 1] > _con[child])
    100. 				//if (child + 1 < _con.size() && _con[child]<_con[child + 1] )
    101. 				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))				
    102. 				{
    103. 					++child;
    104. 				}
    105.  
    106. 				//if (_con[child] > _con[parent])
    107. 				//if ( _con[parent]< _con[child])
    108. 				if (com(_con[parent] , _con[child]))
    109. 				{
    110. 					swap(_con[child], _con[parent]);
    111. 					parent = child;
    112. 					child = parent * 2 + 1;
    113. 				}
    114. 				else
    115. 				{
    116. 					break;
    117. 				}
    118. 			}
    119. 		}
    120.  
    121. 		void pop()
    122. 		{
    123. 			swap(_con[0], _con[_con.size() - 1]);
    124. 			_con.pop_back();
    125. 			adjust_down(0); 
    126. 		}
    127.  
    128. 		bool empty()
    129. 		{
    130. 			return _con.empty();
    131. 		}
    132.  
    133. 		size_t size()
    134. 		{
    135. 			return _con.size();
    136. 		}
    137.  
    138. 		const T& top()
    139. 		{
    140. 			return _con[0];
    141. 		}
    142. 	private:
    143. 		Container _con;
    144. 	};
    145. }

    stack.h

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5.  
    6. namespace qjh
    7. {
    8.  
    9. 	//设计模式
    10. 	//适配器模式--转换
    11. 	//stack> st1;
    12. 	//stack> st2;
    13. 	template<class T,class Container=deque> //有了Container就可以根据需要实现链式栈或数组栈了
    14. 	class stack
    15. 	{
    16. 	public:
    17. 		void push(const T& x)
    18. 		{
    19. 			_con.push_back(x);
    20. 		}
    21.  
    22. 		void pop()
    23. 		{
    24. 			_con.pop_back();
    25. 		}
    26.  
    27. 		size_t size()
    28. 		{
    29. 			return _con.size();
    30. 		}
    31.  
    32. 		bool empty()
    33. 		{
    34. 			return _con.empty();
    35. 		}
    36.  
    37. 		const T& top()
    38. 		{
    39. 			return _con.back();
    40. 		}
    41. 	private:
    42. 		Container _con;
    43. 	};
    44. }

    test.cpp

    1. #include
    2. using namespace std;
    3.  
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include"stack.h"
    9. #include"queue.h"	
    10.  
    11. void test_queue1()
    12. {
    13. 	qjh::queue<int> q;
    14. 	q.push(1);
    15. 	q.push(2);
    16. 	q.push(3);
    17. 	q.push(4);
    18.  
    19. 	while (!q.empty())
    20. 	{
    21. 		cout << q.front() << " ";
    22. 		q.pop();
    23. 	}
    24. 	cout << endl;
    25. }
    26.  
    27.  
    28. void test_stack1()
    29. {
    30. 	qjh::stack<int> st;
    31. 	st.push(1);
    32. 	st.push(2);
    33. 	st.push(3);
    34. 	st.push(4);
    35.  
    36. 	while (!st.empty())
    37. 	{
    38. 		cout << st.top() << " ";
    39. 		st.pop();
    40. 	}
    41. 	cout << endl;
    42. }
    43.  
    44. void test_priority_queue1()
    45. {
    46. 	//默认大的优先级高，底层是大堆
    47. 	//priority_queue pq;
    48.  
    49. 	//大堆
    50. 	//qjh::priority_queue pq; //类模板，传类型 
    51. 	//小堆
    52. 	qjh::priority_queue<int,vector<int>,greater<int>> pq; //类模板，传类型 
    53.  
    54. 	pq.push(2);
    55. 	pq.push(1);
    56. 	pq.push(4);
    57. 	pq.push(3);
    58. 	pq.push(7);
    59. 	pq.push(8);
    60.  
    61.  
    62. 	while (!pq.empty())
    63. 	{
    64. 		cout << pq.top() << " ";
    65. 		pq.pop();
    66. 	}
    67. 	cout << endl;
    68.  
    69. 	//vector v = { 3,1,7,4,6,3 };
    70. 	默认升序
    71. 	//sort(v.begin(), v.end());
    72. 	//for (auto e : v)
    73. 	//{
    74. 	//	cout << e << " ";
    75. 	//}
    76. 	//cout << endl;
    77.  
    78. 	降序
    79.  
    80. 	//sort(v.begin(), v.end(),greater()); //匿名对象，函数模板
    81. 	//for (auto e : v)
    82. 	//{
    83. 	//	cout << e << " ";
    84. 	//}
    85. 	//cout << endl;
    86. }
    87.  
    88. class Date
    89. {
    90. 	friend ostream& operator<<(ostream& _cout, const Date& d);
    91. public:
    92. 	Date(int year = 1900, int month = 1, int day = 1)
    93. 		: _year(year)
    94. 		, _month(month)
    95. 		, _day(day)
    96. 	{}
    97. 	bool operator<(const Date& d)const
    98. 	{
    99. 		return (_year < d._year) ||
    100. 			(_year == d._year && _month < d._month) ||
    101. 			(_year == d._year && _month == d._month && _day < d._day);
    102. 	}
    103. 	bool operator>(const Date& d)const
    104. 	{
    105. 		return (_year > d._year) ||
    106. 			(_year == d._year && _month > d._month) ||
    107. 			(_year == d._year && _month == d._month && _day > d._day);
    108. 	}
    109.  
    110. private:
    111. 	int _year;
    112. 	int _month;
    113. 	int _day;
    114. };
    115.  
    116. ostream& operator<<(ostream& _cout, const Date& d)
    117. {
    118. 	_cout << d._year << "-" << d._month << "-" << d._day;
    119. 	return _cout;
    120. }
    121.  
    122.  
    123. struct GreaterPDate
    124. {
    125. 	bool operator()(const Date* p1, const Date* p2)
    126. 	{
    127. 		return *p1>*p2;
    128. 	}
    129. };
    130.  
    131. void test_priority_queue2()
    132. {
    133. 	qjh::priority_queue, greater> pq; 
    134.  
    135. 	Date d1(2024, 4, 8);
    136. 	pq.push(d1);
    137. 	pq.push(Date(2024,4,10));
    138. 	pq.push({2024,2,15});
    139.  
    140.  
    141. 	while (!pq.empty())
    142. 	{
    143. 		cout << pq.top() << " ";
    144. 		pq.pop();
    145. 	}
    146. 	cout << endl;
    147.  
    148. 	qjh::priority_queue, GreaterPDate> pqptr;
    149.  
    150. 	pqptr.push(new Date(2024, 4, 14));
    151. 	pqptr.push(new Date(2024, 4, 11));
    152. 	pqptr.push(new Date(2024, 4, 15));
    153.  
    154.  
    155. 	while (!pqptr.empty())
    156. 	{
    157. 		cout << *(pqptr.top()) << " ";
    158. 		pqptr.pop();
    159. 	}
    160. 	cout << endl;
    161. }
    162.  
    163. //仿函数/函数对象
    164. //它的对象可以像函数一样的去使用
    165. template<class T>
    166. struct Less
    167. {
    168. 	bool operator()(const T& x, const T& y)
    169. 	{
    170. 		return x < y;
    171. 	}
    172. };
    173.  
    174. int main()
    175. {
    176. 	//test_stack1();
    177. 	//test_queue1();
    178. 	test_priority_queue2();
    179. 	//Less lessfunc;
    180. 	//cout << lessfunc(1, 2) << endl;
    181. 	//cout << lessfunc.operator()(1, 2) << endl;
    182. 	return 0;
    183. }

  • 相关阅读:
    【归并排序】| 详解归并排序核心代码之合并两个有序数组 力扣88
    FastDFS搭建及整合Nginx实现文件上传
    kafka面试连环问（2），你能撑到哪一问？
    【操作系统】为什么需要内核
    大厂搅局网约车，聚合平台别有用心？
    服务器神秘挂起：一场惊心动魄的内核探案
    Autocad绘制的基于工控机的电加热炉的强电电路图
    FS03MR12A6MA1LBBPSA1 1200V 400A 紧凑型 六单元模块
    Hive数据定义语言-DDL-入门基础（含四个实践案例）
    产品思维训练 | 你的项目总是不能按期上线，你会如何解决？
  • 原文地址：https://blog.csdn.net/qinjh_/article/details/137747999