devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++】——Stack与Queue（含优先队列（详细解读）_c++ quene和stack

作者：繁依Fanyi0 | 2024-06-15 23:31:16

赞

踩

c++ quene和stack

前言

之前数据结构中是栈和队列，我们分别用的顺序表和链表去实现的，但是对于这里的栈和队列来说，他们是一种容器，更准确来说是一种容器适配器

✨什么是容器适配器？

 从他们的模板参数可以看出，第二个参数模板是一个容器，并不像vector和list一样是一个内存池

至于deque后面会介绍

这里写传容器的原因就是，栈和队列是直接复用了其他的容器，用他们的功能实现自己的功能，就比如每家的电压和自己手机充电器的电压是不一样的，但是我用一个适配器就可以转换出来

 

一  Stakc的介绍和使用

1.1 Stakc介绍

  1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
  2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
  3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作
  4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

Stack是没有迭代器的，因为栈不能说是去遍历每个元素，而是后进先出的结构，所以设计迭代器没有任何意义，虽然可以去设计

 

1.2  栈的使用 

 对于之前数据结构来说，我们需要自己写一个栈，这里就直接引入头文件就行。

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<vector>
  4. #include<list>
  5. #include<stack>
  6. using namespace std;
  7. int main()
  8. {
  9. 	stack<int> st;
  10. 	st.push(1);
  11. 	st.push(2);
  12. 	st.push(3);
  13. 	st.push(4);
  14. 	st.push(5);
  15. 	int n = st.size();
  16. 	while (n--)
  17. 	{
  18. 		cout << st.top() << " ";
  19. 		st.pop();
  20. 	}
  21. 	cout << endl;
  22. }

 

这里只是一个简单的演示

下面来做一个题目：

155. 最小栈

提示

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次

 思路：

对于这道题目来说，要拿出最小的那个元素，那么我们必须去记录，如果我们用一个变量去保存这个最小值肯定是不行的，因为我们用这个变量保存一个最小值以后，然后我们再删这个最小值，那当前最小就不知道是谁了，得重新来一遍，这样虽然可行，但是在时间效率上可能会很低

所以解决这道题可以用两个栈去模拟，一个栈存最小值，一个栈做为入栈，只要比最小栈的最小元素还小的时候（就是栈顶元素）就可以加入到这个最小栈里面，我们删除数据的时候，如果删除的数据和栈顶元素相等，那么我们把最小栈的元素删除，否则不动。

有了思路，现在来写代码就简单很多了

  1. class MinStack {
  2. public:
  3.     MinStack() {
  4.  
  5.     }
  6.     
  7.     void push(int val) {
  8.         _elem.push(val);//先入
  9.         if(_min.empty()||val<=_min.top())//如果最小栈是空或者当前值比最小栈的栈顶元素还小就加入
  10.         {
  11.             _min.push(val);
  12.         }
  13.     }
  14.     
  15.     void pop() {
  16.         if(_elem.top()==_min.top())//相等就一起删，最后最小栈栈顶元素就是最小的
  17.         {
  18.             _min.pop();
  19.         }
  20.         _elem.pop();
  21.     }
  22.     
  23.     int top() {
  24.         return _elem.top();//其他函数按规则来就行
  25.     }
  26.     
  27.     int getMin() {
  28.         return _min.top();
  29.     }
  30.     private:
  31.     std::stack<int> _elem;//设置两个栈
  32.     std::stack<int> _min;
  33.     
  34. };
  35.  
  36. /**
  37.  * Your MinStack object will be instantiated and called as such:
  38.  * MinStack* obj = new MinStack();
  39.  * obj->push(val);
  40.  * obj->pop();
  41.  * int param_3 = obj->top();
  42.  * int param_4 = obj->getMin();
  43.  */

  二  Queue的介绍和使用

2.1 队列的介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作 :
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

 

2.2  队列的使用 

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<vector>
  4. #include<list>
  5. #include<stack>
  6. #include<queue>
  7. using namespace std;
  8. int main()
  9. {
  10. 	queue<int>q;
  11. 	q.push(1);
  12. 	q.push(2);
  13. 	q.push(3);
  14. 	q.push(4);
  15. 	int n = q.size();
  16. 	while (n--)
  17. 	{
  18. 		cout << q.front() << " ";
  19. 		q.pop();
  20. 	}
  21. 	cout << endl;
  22. 	return 0;
  23. }

三  优先级队列的介绍和使用

3.1 优先队列介绍

   1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
    2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元 素)。
    3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
    4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
    empty()：检测容器是否为空
    size()：返回容器中有效元素个数
    front()：返回容器中第一个元素的引用
    push_back()：在容器尾部插入元素 

    pop_back()：删除容器尾部元素
   5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

优先队列有三个模板参数，一个是 数据类型，一个是容器，一个是比较模板

到这里我们可以得知优先队列默认就是一个大堆

其中比较这里的比较采用的是模板，并不是之前的函数，但是这里可以用比较函数去进行，也就是用一个函数指针，但是c++不喜欢这种做法，并引伸出了仿函数

✨仿函数

仿函数就是把一个写成函数的形式

  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. };

这里是一个比较大小的仿函数，同时也是一个模板类型， 如果确定类型也可以不用写成模板类型

我们可以直接用这个作为比较函数，完成比较。

3.2 优先队列的使用

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<vector>
  4. #include<list>
  5. #include<stack>
  6. #include<queue>
  7. #include <functional>
  8. using namespace std;
  9. // greater算法的头文件
  10. int main()
  11. {
  12. 	// 默认情况下，创建的是大堆，其底层按照小于号比较
  13. 	vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
  14. 	priority_queue<int> q1;
  15. 	for (auto& e : v)  q1.push(e);
  16. 	cout << q1.top() << endl;
  17. 	// 如果要创建小堆，将第三个模板参数换成greater比较方式
  18. 	priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
  19. 	cout << q2.top() << endl;
  20. 	return 0;
  21. }
  22.

优先队列优先是大堆，这里第三个模板参数的改变也就意味比较函数的改变

四 三种容器的模拟实现

4.1 stack模拟实现

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

4.2  queue模拟实现

 

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

4.3  优先队列的模拟实现

  1. #pragma once
  2. template<class T,class Container=vector<T>>
  3. class Priority_queue
  4. {
  5. public:
  6. 	Priority_queue()//无参构造
  7. 	{}
  8. 	//迭代器构造
  9. 	template<class InputIterator>
  10. 	Priority_queue(InputIterator first, InputIterator last):_con(first,last)
  11. 	{
  12. 		for (int i = (_con.size() - 1) / 2; i >= 0; i--)
  13. 		{
  14. 			adjust_down(i);
  15. 		}
  16. 	}
  17. 	//向上调整
  18. 	void adjust_up(int child)
  19. 	{
  20. 		int father = (child-1)/2;
  21. 		while (child > 0)
  22. 		{
  23. 			if (_con[father] < _con[child])
  24. 			{
  25. 				swap(_con[child], _con[father]);
  26. 				child = father;
  27. 				father = (child - 1) / 2;
  28. 			}
  29. 			else
  30. 			{
  31. 				break;
  32. 			}
  33. 		}
  34. 	}
  35. 	//向下调整
  36. 	void adjust_down(int father)
  37. 	{
  38. 		int child = father * 2 + 1;
  39. 		while (child < _con.size())
  40. 		{
  41. 			if (child + 1 < _con.size() && _con[child] < _con[child + 1])
  42. 			{
  43. 				child++;
  44. 			}
  45. 			if (_con[father] < _con[child])
  46. 			{
  47. 				swap(_con[father], _con[child]);
  48. 				father = child;
  49. 				child = father * 2 + 1;
  50. 			}
  51. 			else
  52. 			{
  53. 				break;
  54. 			}
  55. 		}
  56. 	}
  57. 	void push(const T& x)
  58. 	{
  59. 		_con.push_back(x);
  60. 		adjust_up(_con.size() - 1);
  61. 	}
  62. 	void pop()
  63. 	{
  64. 		swap(_con[0], _con[_con.size() - 1]);
  65. 		_con.pop_back();
  66. 		adjust_down(0);
  67. 	}
  68. 	const T& top()
  69. 	{
  70. 		return _con[0];
  71. 	}
  72. 	bool empty()
  73. 	{
  74. 		return _con.empty();
  75. 	}
  76. 	size_t size()
  77. 	{
  78. 		return _con.size();
  79. 	}
  80. private:
  81. 	Container _con;//容器对象
  82. };

测试

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<vector>
  4. #include<list>
  5. #include<stack>
  6. #include<queue>
  7. #include <functional>
  8. using namespace std;
  9. #include"priority_queue.h"
  10. int main()
  11. {
  12. 	vector<int>v = { 3,4,5,1,8,7,8 };
  13. 	Priority_queue<int>p(v.begin(), v.end());
  14. 	int n = p.size();
  15. 	while (n--)
  16. 	{
  17. 		cout << p.top() << " ";
  18. 		p.pop();
  19. 	}
  20. 	cout << endl;
  21. 	return 0;
  22. }

 

 

上面的模拟构造并没有使用第三个参数，也就是没有仿函数，优先队列其实是复用了vector容器，看似是堆，但内部结构是一个可变的数组，其中的每个操作步骤也就是在操作数组里面的元素

还有一个加入仿函数的例子

  1. #pragma once
  2. template<class T,class Container=vector<T>,class Compare=Less<T>>
  3. class Priority_queue
  4. {
  5. public:
  6. 	Priority_queue()//无参构造
  7. 	{}
  8. 	//迭代器构造
  9. 	template<class InputIterator>
  10. 	Priority_queue(InputIterator first, InputIterator last):_con(first,last)
  11. 	{
  12. 		for (int i = (_con.size() - 1) / 2; i >= 0; i--)
  13. 		{
  14. 			adjust_down(i);
  15. 		}
  16. 	}
  17. 	//向上调整
  18. 	void adjust_up(int child)
  19. 	{
  20. 		int father = (child-1)/2;
  21. 		while (child > 0)
  22. 		{
  23. 			if (_com(_con[father] , _con[child]))
  24. 			{
  25. 				swap(_con[child], _con[father]);
  26. 				child = father;
  27. 				father = (child - 1) / 2;
  28. 			}
  29. 			else
  30. 			{
  31. 				break;
  32. 			}
  33. 		}
  34. 	}
  35. 	//向下调整
  36. 	void adjust_down(int father)
  37. 	{
  38. 		int child = father * 2 + 1;
  39. 		while (child < _con.size())
  40. 		{
  41. 			if (child + 1 < _con.size() && _com(_con[child] , _con[child + 1]))
  42. 			{
  43. 				child++;
  44. 			}
  45. 			if (_com(_con[father] , _con[child]))
  46. 			{
  47. 				swap(_con[father], _con[child]);
  48. 				father = child;
  49. 				child = father * 2 + 1;
  50. 			}
  51. 			else
  52. 			{
  53. 				break;
  54. 			}
  55. 		}
  56. 	}
  57. 	void push(const T& x)
  58. 	{
  59. 		_con.push_back(x);
  60. 		adjust_up(_con.size() - 1);
  61. 	}
  62. 	void pop()
  63. 	{
  64. 		swap(_con[0], _con[_con.size() - 1]);
  65. 		_con.pop_back();
  66. 		adjust_down(0);
  67. 	}
  68. 	const T& top()
  69. 	{
  70. 		return _con[0];
  71. 	}
  72. 	bool empty()
  73. 	{
  74. 		return _con.empty();
  75. 	}
  76. 	size_t size()
  77. 	{
  78. 		return _con.size();
  79. 	}
  80. private:
  81. 	Container _con;//容器对象
  82. 	Compare _com;//仿函数对象
  83. };

 注意模板参数的变化和比较大小代码的变化，仿函数是写在外面的，具体怎么比，按自己的需求来

测试：

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<iostream>
  3. #include<vector>
  4. #include<list>
  5. #include<stack>
  6. #include<queue>
  7. #include <functional>
  8. using namespace std;
  9. #include"priority_queue.h"
  10.  
  11. template<class T>
  12. class Less
  13. {
  14. public:
  15. 	bool operator()(const T& x,const T& y)
  16. 	{
  17. 		return x < y;
  18. 	}
  19. };
  20. template<class T>
  21. class Greater
  22. {
  23. public:
  24. 	bool operator()(const T& x, const T& y)
  25. 	{
  26. 		return x >  y;
  27. 	}
  28. };
  29. int main()
  30. {
  31. 	vector<int>v = { 3,4,5,1,8,7,8 };
  32. 	Priority_queue<int,vector<int>,Greater<int>>  p(v.begin(), v.end());
  33. 	int n = p.size();
  34. 	while (n--)
  35. 	{
  36. 		cout << p.top() << " ";
  37. 		p.pop();
  38. 	}
  39. 	cout << endl;
  40. 	return 0;
  41. }

 

 五  deque

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

 和vector和list比起来，它比vector头插的效率高，和list比，它支持随机访问，且空间利用率比list高，但是它都无法替代他们两个，反倒成了stack和queue的底层容器

对于deque来说，它是一个指针数组，这些指针指向一片片空间，它并不真正的连续，而是由这些空间拼接而成

 从上面我们可知道的是，如果我们在中间插入数据，那么就会面临两种选择

1.扩容，这样减少了挪动数据，但是使得每个数组的空间大小不一样，这里数组空间的大小不一样就会导致我们在查找数据的时候需要一个个访问，这样就导致效率变得很低

2.挪动数据，也就是保持数组长度的不变，但是这样挪动的数据就太多了，也会导致效率变低，但是好处就是我们在访问元素的时候，效率会很高，假设每个数组都是10，我们要访问第i个元素，那么我先用i-=第一层的元素个数，然后x=i/10,这里的x就是第几层（层数从0开始），然后y=i%10这里的y是第几个，这样就可以快速的定位了

因为deque有这些缺点，所以也不能替代vector和list

总结

以上就是全部内容了，希望喜欢，多多支持

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/724235
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号