• 机械转码日记【22】stack，queue与priority_queue

    目录

    前言

    1.stack和queue的使用： 

    1.1stack（栈）

    1.2.queue（队列）

    1.3priority_queue（优先级队列（堆））

    2.OJ题

    2.1 最小栈

    2.2栈的压入弹出序列

    2.3逆波兰表达式求值

    3.容器适配器

    3.1什么是适配器

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

    3.3deque的简单介绍

    4.stack和queue的模拟实现

    5.priority_queue的模拟实现

    6.仿函数

    6.1仿函数的应用

    7.deque

    8.反向迭代器

    前言

    这篇博客我们主要来学习一下stl的stack，queue，和priority_queue，它们分别是数据结构中的栈，队列和堆这篇博客我们还会了解到容器适配器模式和仿函数的写法。

    list叫做容器，queue和stack叫容器适配器，我们看到它的模板参数就可以看出来，list的模板参数是一个空间配置器，stack和queue的模板参数是一个容器。

    1.stack和queue的使用： 

    1.1stack（栈）

    栈和我们之前学过的STL类模板对比来说，最大的不同是不支持迭代器，因为不是每种容器都需要迭代器去遍历，对于栈这种数据结构来说，迭代器遍历显得没那么重要。 

     如上图所示，它只提供了以上几个成员函数。

    1. void test_stack()
    2. 	{
    3. 		stack<int> s;
    4. 		s.push(1);
    5. 		s.push(2);
    6. 		s.push(3);
    7. 		s.push(4);
    8.  
    9. 		while (!s.empty())
    10. 		{
    11. 			cout << s.top() << " ";
    12. 			s.pop();
    13. 		}
    14. 		cout << endl;
    15. 	}

    栈的使用如上，我们向栈里面push了四个数据，每次打印栈顶的数据，然后将栈顶数据出栈，如此循环，直到栈为空。

    1.2.queue（队列）

    queue也一样，它的成员函数也只有以下几个：

     它的使用方式如下：

    1. 	void test_queue()
    2. 	{
    3. 		queue<int> q;
    4. 		q.push(1);
    5. 		q.push(2);
    6. 		q.push(3);
    7. 		q.push(4);
    8.  
    9. 		while (!q.empty())
    10. 		{
    11. 			cout << q.front() << " ";
    12. 			q.pop();
    13. 		}
    14. 		cout << endl;
    15. 	}

    我们先往队列里面push四个数据，然后打印队头的数据，接着是的队头数据出队列，如此循环，直到队列为空：

    1.3priority_queue（优先级队列（堆））

    优先级队列，它的底层实际上一个堆（虽然它叫队列），它可以在任意位置插入数据，默认是一个大堆。

    注意：

    1. 优先级队列不需要包括额外的头文件，只需要#include就行了
    2. 优先级队列默认是一个大堆，这个时候只需要priority_queue pq;就可以构造一个大堆，如果需要构造一个小堆，需要传入仿函数：priority_queue, greater> pq;

    创建一个大堆： 

    1. 	void test_priority_queue()
    2. 	{
    3. 		priority_queue<int> pq;
    4. 		pq.push(2);
    5. 		pq.push(5);
    6. 		pq.push(1);
    7. 		pq.push(6);
    8. 		pq.push(8);
    9.  
    10. 		while (!pq.empty())
    11. 		{
    12. 			cout << pq.top() << " ";
    13. 			pq.pop();
    14. 		}
    15. 		cout << endl;
    16. 	}

    创建一个小堆： 

    1. 	void test_priority_queue()
    2. 	{
    3. 		priority_queue<int, vector<int>, greater<int>> pq;//仿函数，奇怪的是传的是greater这个仿函数来创建小堆
    4.  
    5. 		pq.push(2);
    6. 		pq.push(5);
    7. 		pq.push(1);
    8. 		pq.push(6);
    9. 		pq.push(8);
    10.  
    11. 		while (!pq.empty())
    12. 		{
    13. 			cout << pq.top() << " ";
    14. 			pq.pop();
    15. 		}
    16. 		cout << endl;
    17. 	}
    18.

    2.OJ题

    2.1 最小栈

    最小栈

    1. class MinStack {
    2. public:
    3.     MinStack() {
    4.  
    5.     }
    6.     
    7.     void push(int val) {
    8.         _st.push(val);
    9.         if(_min.empty()||val<=_min.top())//最小栈没数据或插入的值小于等于最小值就让最小栈值进数据
    10.         {
    11.             _min.push(val);
    12.         }
    13.     }
    14.     
    15.     void pop() {
    16.         if(_st.top()==_min.top())//如果栈顶数据和最小栈数据相等就让最小栈栈顶元素出栈
    17.         {
    18.             _min.pop();
    19.         }
    20.         _st.pop();
    21.     }
    22.     
    23.     int top() {
    24.         return _st.top();
    25.     }
    26.     
    27.     int getMin() {
    28.         return _min.top();
    29.     }
    30. private:
    31.     stack<int> _st;
    32.     stack<int> _min;
    33.  
    34. };

    2.2栈的压入弹出序列

    栈的压入弹出序列

     

    1. class Solution {
    2. public:
    3.     bool IsPopOrder(vector<int> pushV,vector<int> popV) {
    4.         stack<int> st;
    5.         int j = 0;
    6.         for(int i = 0; isize();i++)
    7.         {
    8.             //入栈
    9.             st.push(pushV[i]);
    10.             while(!st.empty()&&st.top()==popV[j])
    11.             {
    12.                 st.pop();
    13.                 j++;
    14.             }
    15.         }
    16.         return st.empty();
    17.     }
    18. };

    2.3逆波兰表达式求值

    逆波兰表达式求值

    1. class Solution {
    2. public:
    3.     int evalRPN(vector& tokens) 
    4.     {
    5.         stack<int> s;//存储数字的栈
    6.         for (size_t i = 0; i < tokens.size(); ++i)
    7.         {
    8.             string& str = tokens[i];//把vector取出来看看是什么字符
    9.             // str为数字
    10.             if (!("+" == str || "-" == str || "*" == str || "/" == str))
    11.             {
    12.                 s.push(atoi(str.c_str()));
    13.             }
    14.             else
    15.             {
    16.                  // str为操作符
    17.                 int right = s.top();
    18.                 s.pop();
    19.                 int left = s.top();
    20.                 s.pop();
    21.                 switch (str[0])
    22.                 {
    23.                      case '+':
    24.                      s.push(left + right);
    25.                      break;
    26.                      case '-':
    27.                      s.push(left - right);
    28.                      break;
    29.                      case '*':
    30.                      s.push(left * right);
    31.                      break;
    32.                      case '/':
    33.                      s.push(left / right);
    34.                      break;
    35.                 }
    36.             }
    37.         }
    38.         return s.top();
    39.     }
    40. };

    3.容器适配器

    3.1什么是适配器

    适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

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

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

    3.3deque的简单介绍

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

    4.stack和queue的模拟实现

    stack和queue的模拟实现比较简单，只需要调用deque的库函数就可以实现适配：

    1. using namespace std;
    2. #include
    3. template<class T, class Container = deque>
    4. 	class stack
    5. 	{
    6. 	public:
    7. 		void push(const T& x)
    8. 		{
    9. 			_con.push_back(x);
    10. 		}
    11.  
    12. 		void pop()
    13. 		{
    14. 			_con.popback();
    15. 		}
    16.  
    17. 		const T& top()
    18. 		{
    19. 			return _con.back();//不要用[]，因为别的容器不一定支持
    20. 		}
    21.  
    22. 		size_t size()
    23. 		{
    24. 			return _con.size();
    25. 		}
    26.  
    27. 		bool empty()
    28. 		{
    29. 			return _con.empty();
    30. 		}
    31.  
    32. 	private:
    33. 		Container _con;
    34.  
    35. 	};

    大家可以试试用vector和list代替deque传参stack也能正常运行。

    1. template<class T, class Container = deque>
    2. 	class queue
    3. 	{
    4. 	public:
    5. 		void push(const T& x)
    6. 		{
    7. 			_con.push_back(x);
    8. 		}
    9.  
    10. 		void pop()
    11. 		{
    12. 			_con.popfront();
    13. 		}
    14.  
    15. 		const T& top()
    16. 		{
    17. 			return _con.back();//不要用[]，因为别的容器不一定支持
    18. 		}
    19.  
    20. 		size_t size()
    21. 		{
    22. 			return _con.size();
    23. 		}
    24.  
    25. 		bool empty()
    26. 		{
    27. 			return _con.empty();
    28. 		}
    29.  
    30. 	private:
    31. 		Container _con;
    32.  
    33. 	};

    queue就不能传vector代替deque传参了，因为人家没有实现popfront。

    5.priority_queue的模拟实现

    priority_queue默认的模板参数用的是vector，而不是deque，因为vector对随机访问的效率高，deque适合在头尾插入删除（虽然支持随机访问和中间的插入删除，但是效率比vector低）

    priority_queue的模拟需要边插入边进行堆排序，我们需要回忆一下建立堆的博客，其实就是向上调整和向下调整，插入一个数据之后需要进行向上调整，pop掉一个数据之后需要进行向下调整。

    1. template<class T, class Container = vector>
    2. 	class priority_queue
    3. 	{
    4.  
    5. 	public:
    6. 		void push(const T& x)
    7. 		{
    8. 			_con.push_back(x);
    9. 			AdjustUp(_con.size() - 1);//插入之后一个向上调整
    10.  
    11. 		}
    12.  
    13. 		void pop()
    14. 		{
    15. 			assert(_con.empty());
    16. 			swap(_con[0], _con[_con.size() - 1]);//先进先出，所以先把第一个位置的数据出掉，然后把交换后的第一个数据向下调整
    17. 			_con.pop_back();
    18. 			AdjustDown(0);
    19. 		}
    20.  
    21.  
    22. 		//
    23. 		//向上调整
    24. 		void AdjustUp(int child)//默认是大堆,用<用大堆
    25. 		{
    26. 			//找父亲
    27. 			int parent = (child - 1) / 2;
    28. 			while (child > 0)
    29. 			{
    30. 				//和父亲比较，如果父亲小于孩子，说明不是大堆，交换孩子和父亲
    31. 				if (_con[parent] < _con[child])
    32. 				{
    33. 					swap(_con[parent], _con[child]);
    34. 					//更新孩子和父亲的位置
    35. 					child = parent;
    36. 					parent = (child - 1) / 2;
    37. 				}
    38. 				else//不小就跳出
    39. 				{
    40. 					break;
    41. 				}	
    42. 			}
    43. 		}
    44.  
    45. 		//向下调整
    46. 		void AdjustDown(int parent)//默认是大堆,用<用大堆
    47. 		{
    48. 			//找孩子
    49. 			int child = parent * 2 + 1;//左孩子
    50. 			while (child < _con.size())
    51. 			{
    52. 				//选出左右孩子大的那个
    53. 				if (child + 1 < _con.size()&&_con[child]<_con[child+1])//右孩子存在且右孩子更大
    54. 				{
    55. 					child++;
    56. 					
    57. 				}
    58. 				if (_con[parent] < _con[child])
    59. 				{
    60. 					swap(_con[parent], _con[child]);
    61. 					parent = child;
    62. 					child = parent * 2 + 1;
    63. 				}
    64. 				else
    65. 				{
    66. 					break;
    67. 				}
    68. 			}
    69. 		}
    70.  
    71. 		const T& top()//引用返回减少拷贝，且堆数据不允许随意修改，用const引用返回
    72. 		{
    73. 			return _con[0];
    74. 		}
    75.  
    76. 		size_t size()
    77. 		{
    78. 			return _con.size();
    79. 		}
    80.  
    81. 		bool empty()
    82. 		{
    83. 			return _con.empty();
    84. 		}
    85. 	private:
    86. 		Container _con;
    87. 	};

    但是有个细节就是向上调整和向下调整不能写死，写死了创建小堆就很麻烦，像上面我们写死了就比较麻烦，创建小堆的时候如果写死了，就需要再定义一个创建小堆的向上调整和向下调整，但是实际使用中我们是传一个仿函数就行了。

    因此我们先来写两个仿函数less和greater：

    1.     template<class T>
    2. 	struct less
    3. 	{
    4. 		//重载的是()这个运算符
    5. 		bool operator()(const T& x, const T& y)const//const对象也能用
    6. 		{
    7. 			return x < y;
    8. 		}
    9. 	};
    10.  
    11. 	template<class T>
    12. 	struct greater
    13. 	{
    14. 		//重载的是()这个运算符
    15. 		bool operator()(const T& x, const T& y)const//const对象也能用
    16. 		{
    17. 			return x > y;
    18. 		}
    19. 	};

    如此看，使用起来就像一个函数，所以叫仿函数： 

    1. less LessCom;
    2. cout << LessCom(1, 2) << endl;
    3.  
    4. greater<int> GreaterCom;
    5. cout << GreaterCom(1, 2) << endl;

    我们改造一下上面写的优先级队列，增加上仿函数作为模板参数：

    1.     template<class T, class Container = vector,class Compare = less>
    2. 	class priority_queue
    3. 	{
    4. 		Compare comnFunc;
    5. 	public:
    6. 		void push(const T& x)
    7. 		{
    8. 			_con.push_back(x);
    9. 			AdjustUp(_con.size() - 1);//插入之后一个向上调整
    10.  
    11. 		}
    12.  
    13. 		void pop()
    14. 		{
    15. 			assert(_con.empty());
    16. 			swap(_con[0], _con[_con.size() - 1]);//先进先出，所以先把第一个位置的数据出掉，然后把交换后的第一个数据向下调整
    17. 			_con.pop_back();
    18. 			AdjustDown(0);
    19. 		}
    20.  
    21.  
    22. 		//
    23. 		//向上调整
    24. 		void AdjustUp(int child)//默认是大堆,用<用大堆
    25. 		{
    26. 			
    27. 			//找父亲
    28. 			int parent = (child - 1) / 2;
    29. 			while (child > 0)
    30. 			{
    31. 				//和父亲比较，如果父亲小于孩子，说明不是大堆，交换孩子和父亲
    32. 				if (comnFunc(_con[parent], _con[child]))
    33. 				{
    34. 					swap(_con[parent], _con[child]);
    35. 					//更新孩子和父亲的位置
    36. 					child = parent;
    37. 					parent = (child - 1) / 2;
    38. 				}
    39. 				else//不小就跳出
    40. 				{
    41. 					break;
    42. 				}	
    43. 			}
    44. 		}
    45.  
    46. 		//向下调整
    47. 		void AdjustDown(int parent)//默认是大堆,用<用大堆
    48. 		{
    49. 			Compare comnFunc;
    50. 			//找孩子
    51. 			int child = parent * 2 + 1;//左孩子
    52. 			while (child < _con.size())
    53. 			{
    54. 				//选出左右孩子大的那个
    55. 				if (child + 1 < _con.size()&& comnFunc(_con[child] ,_con[child + 1]))//右孩子存在且右孩子更大
    56. 				{
    57. 					child++;
    58. 					
    59. 				}
    60. 				if (comnFunc(_con[parent], _con[child]))
    61. 				{
    62. 					swap(_con[parent], _con[child]);
    63. 					parent = child;
    64. 					child = parent * 2 + 1;
    65. 				}
    66. 				else
    67. 				{
    68. 					break;
    69. 				}
    70. 			}
    71. 		}
    72.  
    73. 		const T& top()//引用返回减少拷贝，且堆数据不允许随意修改，用const引用返回
    74. 		{
    75. 			return _con[0];
    76. 		}
    77.  
    78. 		size_t size()
    79. 		{
    80. 			return _con.size();
    81. 		}
    82.  
    83. 		bool empty()
    84. 		{
    85. 			return _con.empty();
    86. 		}
    87. 	private:
    88. 		Container _con;
    89. 	};

    6.仿函数

    仿函数的优势是很多时候能够替代函数指针，函数指针其实是一个非常复杂的东西，一度令我很头疼，比如下面：

    是不是感觉这么一大堆很复杂，和我们的仿函数比起来一点也不简洁，所以C++发明了仿函数。

    6.1仿函数的应用

    greater和less两个仿函数是库里面已经为我们写好的，但是有时候我们需要自己显式写出一个仿函数，比如sort函数就需要用到自己写的仿函数：

     假设我们有一个商品，需要我们进行排序，应该怎么办呢？

    1. // 商品
    2. 	struct Goods
    3. 	{
    4. 		string _name;//名字
    5. 		double _price;//价格
    6. 		size_t _saleNum;//销量
    7. 	};
    Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} };

    以上的商品数组，你会如何排序呢？

    那么这个时候就需要用到我们的仿函数了，根据我们排序的标准，去实现不同的仿函数，比如价格升序： 

    1. // 商品
    2. struct Goods
    3. {
    4. 	string _name;//名字
    5. 	double _price;//价格
    6. 	size_t _saleNum;//销量
    7. };
    8.  
    9. struct LessPrice//价格升序
    10. {
    11. 	bool operator()(const Goods& g1, const Goods& g2) const
    12. 	{
    13. 		return g1._price < g2._price;
    14. 	}
    15. };
    16.  
    17. void testFunctional()
    18. {
    19. 	Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} };
    20. 	sort(gds, gds + 4, LessPrice());
    21. }

     运行结果为：

     同理，也可以实现别的排序方式的仿函数：

    1. struct GreaterPrice//价格降序
    2. {
    3. 	bool operator()(const Goods& g1, const Goods& g2) const
    4. 	{
    5. 		return g1._price > g2._price;
    6. 	}
    7. };
    8.  
    9. struct LessSaleNum//商品名字升序
    10. {
    11. 	bool operator()(const Goods& g1, const Goods& g2) const
    12. 	{
    13. 		return g1._saleNum < g2._saleNum;
    14. 	}
    15. };
    16.  
    17.  
    18. struct GreaterSaleNum//销量降序
    19. {
    20. 	bool operator()(const Goods& g1, const Goods& g2) const
    21. 	{
    22. 		return g1._saleNum > g2._saleNum;
    23. 	}
    24. };

    7.deque

    deque是用来适配list和stack的容器适配器，我们进行一个简单的了解：

    deque产生的理由是vector和list有一些共同的缺点：vector是连续的空间，优点是适合尾插尾删，适合随机访问，缺点是不适合头部或者中部的插入删除，效率低，需要挪动数据，此外vector扩容有一定性能的消耗，还可能存在一定程度的空间浪费。list是不连续的空间，优点是任意位置的插入删除效率高O（1）,可以按需申请释放空间。缺点是不支持随机访问。

     结合它们的优缺点，deque这个双端队列就应运而生。

    它的结构如上图所示，它其实是一段段连续的空间，用一个叫做中控数组的指针数组记录每一段连续的空间的第一个位置，虽然中控数组满了也需要扩容，但是扩容的代价要比vector低得多。

    deque的优缺点如下：

     

    8.反向迭代器

    通过前面几节的学习，我们已经大概了解了适配器的这样一种模式，其实反向迭代器也是适配器模式。

    我们想一想，反向迭代器和正向迭代器相比，有什么区别呢？好像除了++和--不一样，别的都一样，所以我们能不能用正向迭代器去封装适配一下，生成对应的反向迭代器呢？

     源代码如下：

    1. 	template <class Iterator,class Ref,class Ptr>
    2. 	struct Reverse_iterator
    3. 	{
    4. 		Iterator _it;
    5. 		typedef Reverse_iterator Self;
    6. 		Reverse_iterator(Iterator _it)
    7. 			:_it(it)
    8. 		{
    9.  
    10. 		}
    11. 		Ref operator*()
    12. 		{
    13. 			Iterator tmp = *it;
    14. 			return *(--tmp);
    15. 		}
    16.  
    17. 		Ptr operator->()
    18. 		{
    19. 			return &(operator*());
    20. 		}
    21.  
    22. 		Self& operator++()
    23. 		{
    24. 			--_it;
    25. 			return *this;
    26. 		}
    27.  
    28. 		Self& operator--()
    29. 		{
    30. 			++_it;
    31. 			return *this;
    32. 		}
    33.  
    34. 		bool operator!=(const Self& s)
    35. 		{
    36. 			return _it != s._it;
    37. 		}
    38. 	};
    39.  
    40.         typedef __list_iterator iterator;
    41. 		typedef __list_iteratorconst T&, const T*> const_iterator;
    42.  
    43.         // 反向迭代器适配支持
    44. 		typedef Reverse_iterator reverse_iterator;
    45. 		typedef Reverse_iteratorconst T&, const T*> const_reverse_iterator;
    46.  
    47.         const_reverse_iterator rbegin() const
    48. 		{
    49. 			return const_reverse_iterator(end());
    50. 		}
    51.  
    52. 		const_reverse_iterator rend() const
    53. 		{
    54. 			return const_reverse_iterator(begin());
    55. 		}
    56.  
    57.         reverse_iterator rbegin()
    58. 		{
    59. 			return reverse_iterator(end());
    60. 		}
    61.  
    62. 		reverse_iterator rend()
    63. 		{
    64. 			return reverse_iterator(begin());
    65. 		}
  • 相关阅读:
    四分之一车体模型车辆载重预测
    Raiden Network（二）—— Mediated transfers（多跳支付里的中介传输）
    gbase8s数据库的逻辑日志、物理日志和两种特殊情形的学习
    R3live&Fastlio2
    不删除D盘的情况下扩容c盘（扩容成功
    TypeScript 介绍和开发环境搭建
    Hadoop3教程（二十六）：（生产调优篇）NameNode核心参数配置与回收站的启用
    CentOS7 内核升级
    Turtlebot2简单控制
    C语言的缺陷与陷阱
  • 原文地址：https://blog.csdn.net/qq_52378490/article/details/125474712