c++--stack,queue,priority_queue

Love The Way You Lie 2024-03-30 16:10 164阅读 0赞

前言

对于栈和队列我们是不陌生的,在数据结构阶段已经学习过,记得当时我们还是用c语言将它一步一步造出来,因为压栈与出栈正好满足数组的尾插与头删,数组的代价是及小的。对于队列是头出队列,尾插。所以就栈的实现就用的数组,队列实现就用链表。在c++中呢,vector和list就完美解决。priority_queue叫优先级队列,实质就是大小堆,堆的实现就是数组。

在很多时候stack,queue,priority_queue他们都叫做适配器,这里简单的提一下,它们就好比是农夫山泉,不生产水,是大自然的搬运工。也就意味着它“不生产代码,只是代码的搬运工”。下面我们通过底层代码的实现,就能看出这一特性。


目录

前言

一、stack-栈

1.1 stack的使用

1.2stack的模拟实现

二、queue-队列

2.1queue的使用

2.2queue的模拟实现

2.3容器适配器

三、deque

3.2deque的原理介绍

3.3deque—插入

3.4deque的接口

四、priority_queue-优先级队列

4.1priority_queue的使用

4.2模拟实现

编辑

五、仿函数/函数对象

5.1仿函数的实现

5.2仿函数的使用

5.2仿函数的用法(进阶版)



一、stack-栈

stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。

924a1fef9b07480b8c3709850af85def.png


1.1 stack的使用

下面这些接口的使用我相信大家已经是游刃有余了,这里就不用过多演示,若不熟悉查文档即可。
































函数说明 接口说明
stack() 构造空的栈
empty() 检测stack是否为空
size() 返回stack中元素的个数
top() 返回栈顶元素的引用
push() 将元素val压入stack中
pop() 将stack中尾部的元素弹出
  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. while (!s.empty())
  9. {
  10. cout << s.top() << " ";
  11. s.pop();
  12. }
  13. }

1.2stack的模拟实现

对stack的实现,现在只关注它的实现全是调用。关于deque,Container下面我们就会进行探究。

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

二、queue-队列

队列也是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。

dd3c23c0ac0d4d9c97baad612d42e710.png


2.1queue的使用

队列的接口其实与栈的接口基本一样,而且使用方法也是一样。




































函数声明 接口说明
queue() 构造空的队列
empty() 检测队列是否为空,是返回true,否则返回false
size() 返回队列中有效元素的个数
front() 返回队头元素的引用
back() 返回队尾元素的引用
push() 在队尾将元素val入队列
pop() 将队头元素出队列
  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. while (!q.empty())
  9. {
  10. cout << q.front() << " ";
  11. q.pop();
  12. }
  13. cout << endl;
  14. }

2.2queue的模拟实现

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

queue的模拟实现也是非常简单的,都是复用其他人代码。栈和队列的实现中,我们发现都有class Container = deque

在queue和stack中都有这样一段话。

Queue:

queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.
翻译:

队列是一种容器适配器,专门设计用于在 FIFO 上下文(先进先出)中运行,其中元素插入容器的一端并从另一端提取。

Stacks:

Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.

翻译:

堆栈是一种容器适配器,专门设计用于在后进先出(后进先出)环境中操作,其中元素仅从容器的一端插入和提取。

class Container = deque在这里就是容器适配器。

2.3容器适配器

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

设计模式的使用将提高软件系统的开发效率和软件质量,节省开发成本。有助于初学者深入理解面向对象思想,设计模式使设计方案更加灵活,方便后期维护修改。

在stack,queue中 deque接口转换到Container中。deque是什么呢?我们不是说stack可以用vector,queue用list吗,怎么这里用的deque。

三、deque

在容器适配器为什么会选择deque,那么就必须得从vector,list的优缺点说起


3.1vector,list的优缺点

vector:

stack可以随机访问,但是头部中部插入删除效率低,并且还需要扩容

list:

虽然queue在任何地方插入删除效率高,但是不支持随机访问,CPU高速缓存命中率低

对于deque就完美兼容vector,list的优点。所以对于接口选择就是deque。

3.2deque的原理介绍

deque文档

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

edd275adf67a481fa0d1b4d246d7abfe.png

这个是deque一段的buffer数组,所以deque并不是真正连续的空间,它是由一段一段这样的buffer数组链接而成,一段一段的buffer数组被放在中控,这个中控就是一个指针数组,实际上deque类似于一个动态的二维数组, 如图:51e44bbbf622425eb4d3e608549c5ed5.png

这里的缓冲区就是buffer数组,用于存放数据。map就是中控器,就是存放指针。当map空间不够后,会再开辟一个中控-map。

3.3deque—插入

插入操作—头插ffbeb4a881a84ea69a2058dd925db857.png

插入操作—尾插

f89275f607584af3b07efb5cc6ccbfd5.png

查找:即相当于二维数组一样,先找map中的地址(第一层),然后在找buffer(第二层)

缺点:

那么我们发现它下标访问有一定的消耗,没有vector快。当我们中间插入时候,它的中间插入的时候需要挪动数据,与list相比也是有消耗的。

deque不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到 某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作 为stack和queue的底层数据结构。

我们通过发现deque其实是没有想象中那样完美的,它与vector和list相比是不够极致的。vector是吕布,list是诸葛亮,那么deque就是魏延。所以更多的时候我们更需要极致。

deque的底层实现是比较复杂的,不仅仅是上诉简单两句的问题。

9f621516e6324b478fa0274e866b08d0.png

根据上图,对于deque的维护是通过两个迭代器,start和finsh。因为daque是作为stack和queue的底层默认容器,一般来说deque是不需要进行中间插入的,那么start和finsh就很好的处理头插和尾插。它通过frist和last指向头尾,头插通过start的frist,如果满了node链接map新开辟buffer的指针位置。尾插通过finish的last控制。如果top()和back(),即通过start的cur和finish的cur控制。、

3.4deque的接口

deque文档的接口e3462bb923654189a575f4dc2eb84080.png

8048ad75cd4e46ee9105678068974c54.png

25cc01c583ee49148a0bd058111edf0a.pngffbd20c8f6d94f54b7de717ab19d906b.png

通过stack,queue的接口与deque的接口对比,发现直接调用deque是非常适合充当stack,queue的默认容器。stack,queue就是直接调用deque的接口。

四、priority_queue-优先级队列

优先队列是一种容器适配器,而它实质就是堆。是否还记得堆是完全二叉树中用数组实现的,因为数组正好满足堆下标随机存取的需求,标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。相对deque,vector更加极致。priority_queue是默认大根堆。


4.1priority_queue的使用

priority_queue的使用来说也是比较简单的,接口也比较少。




























函数声明 接口说明
priority_queue()/priority_queue(first, last) 构造一个空的优先级队列
empty( )

检测优先级队列是否为空,是返回true,否则返回

false

top( ) 返回优先级队列中最大(最小元素),即堆顶元素
push(x) 在优先级队列中插入元素x
pop() 删除优先级队列中最大(最小)元素,即堆顶元素

对于priority_queue的头文件,我们通过手册发现,priority_queue与queue都是一个头文件。

713c487749ae44a4a07e7ecbcd2f878e.png

接口演示:

  1. //默认大根堆
  2. void test()
  3. {
  4. priority_queue<int> p;
  5. p.push(7);
  6. p.push(1);
  7. p.push(9);
  8. p.push(2);
  9. p.push(3);
  10. p.push(4);
  11. while (!p.empty())
  12. {
  13. cout << p.top() << " ";
  14. p.pop();
  15. }
  16. }

结果:9 7 4 3 2 1

小根堆 —greater

  1. void test()
  2. {
  3. priority_queue<int, vector<int>, greater<int> > p;
  4. p.push(7);
  5. p.push(1);
  6. p.push(9);
  7. p.push(2);
  8. p.push(3);
  9. p.push(4);
  10. while (!p.empty())
  11. {
  12. cout << p.top() << " ";
  13. p.pop();
  14. }
  15. }

结果:1 2 3 4 7 9

4.2模拟实现

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

如果对向上/向下调整忘记了的,就可以看下面图片回忆。

向上调整

" class="reference-link">c37a481e57ae46aaab38b443d90eb0f5.png

向下调整d844881756da41e4a7fa342d9197acf2.png

五、仿函数/函数对象

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


5.1仿函数的实现

这里是实现的比较大小的仿函数

  1. #include <iostream>
  2. using namespace std;
  3. //仿函数/函数对象
  4. namespace qhx
  5. {
  6. template<class T>
  7. class less
  8. {
  9. public:
  10. bool operator()(const T& x, const T& y)
  11. {
  12. return x < y;
  13. }
  14. };
  15. template<class T>
  16. class greater
  17. {
  18. public:
  19. bool operator()(const T& x, const T& y)
  20. {
  21. return x>y;
  22. }
  23. };
  24. };
  25. int main()
  26. {
  27. qhx::less<int> lessFunc;
  28. if (lessFunc(3, 2))
  29. cout << "yes" << endl;
  30. else
  31. cout << "no" << endl;
  32. return 0;
  33. }

5.2仿函数的使用

冒泡排序

  1. template <class T>
  2. void BubbleSort(T* a, int n)
  3. {
  4. for (int i = 0; i < n; i++)
  5. {
  6. int flag = 0;
  7. for (int j = 1; j < n - i; j++)
  8. {
  9. if (a[j - 1] > a[j])
  10. swap(&a[j - 1], &a[j]);
  11. flag = 1;
  12. }
  13. if (flag == 0)
  14. break;
  15. }
  16. }

在C语言时期,冒泡函数进行比较的时候,是需要进入冒泡函数内部改变”>”,”<”。或者是通过函数指针的方式,在多增加一个函数参数。

方法一:

if (a[j - 1] > a[j]) //改变其大与小

对于封装的好的函数来说,这样对使用者是非常不友好的,那么就可以通过接口的方式,增加函数指针。

方法二:

void BubbleSort(T* a, int n,bool(*pcom)(int,int))

方法二的话,这个方法是比较搓的,使用的函数时需要传太多变量,阅读性也不够强。那么c++中函数模板就起到了重要的作用了。我们可以增加一个模板参数,再增加给函数的参数,通过类型的对象去比较,可以想函数一样去是使用。

  1. template <class T,class compaer>
  2. // 冒泡排序
  3. void BubbleSort(T* a, int n,compaer com)
  4. {
  5. for (int i = 0; i < n; i++)
  6. {
  7. int flag = 0;
  8. for (int j = 1; j < n - i; j++)
  9. {
  10. //if (a[j - 1] > a[j])
  11. if (com(a[j - 1] , a[j]))
  12. swap(a[j - 1], a[j]);
  13. flag = 1;
  14. }
  15. if (flag == 0)
  16. break;
  17. }
  18. }
  19. void test_less()
  20. {
  21. qhx::less<int> lessFunc;
  22. if (lessFunc(3, 2))
  23. cout << "yes" << endl;
  24. else
  25. cout << "no" << endl;
  26. }
  27. void test_BubbleSort()
  28. {
  29. qhx::less<int> lessFunc;
  30. int arr[] = { 1, 2, 4, 9, 8, 3, 6, 7 };
  31. //BubbleSort(arr, sizeof(arr) / sizeof(arr[0]),lessFunc);
  32. BubbleSort(arr, sizeof(arr) / sizeof(arr[0]), lessFunc);
  33. for (auto e : arr)
  34. {
  35. cout << e << " ";
  36. }
  37. }
  38. int main()
  39. {
  40. test_BubbleSort();
  41. return 0;
  42. }

运行结果:9 8 7 6 4 3 2 1

这里的less是根据优先级队列来定义的,这里是降序,greater就是升序。

注意:这里模板参数是类,函数调用类模板增加的代码内存时不多的。例如上述只增加1个字节。

5.2仿函数的用法(进阶版)

这里是比较Daet—自定义类型的大小。我们有Date类型比较大小的方式后,但是对于Date*的比较是没有的,故此,我们创建一个struct(类-默认公共类),然后通过函数模板的调用,实现了比较非自定义变量指针的大小。

  1. #include <iostream>
  2. #include <queue>
  3. #include <functional>
  4. using namespace std;
  5. class Date
  6. {
  7. public:
  8. Date(int year = 1900, int month = 1, int day = 1)
  9. : _year(year)
  10. , _month(month)
  11. , _day(day)
  12. {}
  13. bool operator<(const Date& d)const
  14. {
  15. return (_year < d._year) ||
  16. (_year == d._year && _month < d._month) ||
  17. (_year == d._year && _month == d._month && _day < d._day);
  18. }
  19. bool operator>(const Date& d)const
  20. {
  21. return (_year > d._year) ||
  22. (_year == d._year && _month > d._month) ||
  23. (_year == d._year && _month == d._month && _day > d._day);
  24. }
  25. friend ostream& operator<<(ostream& _cout, const Date& d)
  26. {
  27. _cout << d._year << "-" << d._month << "-" << d._day;
  28. return _cout;
  29. }
  30. private:
  31. int _year;
  32. int _month;
  33. int _day;
  34. };
  35. struct PDateLess
  36. {
  37. bool operator()(const Date* d1, const Date* d2)
  38. {
  39. return *d1 < *d2;
  40. }
  41. };
  42. struct PDateGreater
  43. {
  44. bool operator()(const Date* d1, const Date* d2)
  45. {
  46. return *d1 > *d2;
  47. }
  48. };
  49. void TestPriorityQueue()
  50. {
  51. // 大堆,需要用户在自定义类型中提供<的重载
  52. priority_queue<Date> q1;
  53. q1.push(Date(2018, 10, 29));
  54. q1.push(Date(2018, 10, 28));
  55. q1.push(Date(2018, 10, 30));
  56. cout << q1.top() << endl;
  57. // 如果要创建小堆,需要用户提供>的重载
  58. priority_queue<Date, vector<Date>, greater<Date>> q2;
  59. q2.push(Date(2018, 10, 29));
  60. q2.push(Date(2018, 10, 28));
  61. q2.push(Date(2018, 10, 30));
  62. cout << q2.top() << endl;
  63. // 大堆
  64. priority_queue<Date*, vector<Date*>, PDateLess> q3;
  65. q3.push(new Date(2018, 10, 29));
  66. q3.push(new Date(2018, 10, 28));
  67. q3.push(new Date(2018, 10, 30));
  68. cout << *q3.top() << endl;
  69. // 小堆
  70. priority_queue<Date*, vector<Date*>, PDateGreater> q4;
  71. q4.push(new Date(2018, 10, 29));
  72. q4.push(new Date(2018, 10, 28));
  73. q4.push(new Date(2018, 10, 30));
  74. cout << *q4.top() << endl;
  75. }
  76. int main()
  77. {
  78. TestPriorityQueue();
  79. return 0;
  80. }

发表评论

表情:
评论列表 (有 0 条评论,164人围观)

还没有评论,来说两句吧...

相关阅读