stack、queue和priority_queue

目录 

一、栈（stack）

1.stack的使用

2.容器适配器

3.stack的模拟实现

二、队列（queue）

1.queue的使用

2.queue的模拟实现

三、双端队列（deque）

1.vector，list的优缺点

2.认识deque

四、priority_queue-优先级队列

1.priority_queue的使用

2.priority_queue的模拟实现

3.仿函数

---

一、栈（stack）

1.stack的使用

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

相信stack的使用大家都已经熟悉了，下面的所有接口也都很好理解：

测试代码：

#include<iostream>
#include<stack>
using namespace std;void test()
{stack<int> s;s.push(1);s.push(2);s.push(3);s.push(4);while (!s.empty()){cout << s.top() << " ";s.pop();}
}int main()
{test()return 0;
}

2.容器适配器

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

比如说，下面的stack和queue的实现就是一个很好的例子。

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

3.stack的模拟实现

我们之前提到过代码的复用，既然已经有现成的东西了，我为什么不用呢？

stack在我们看来是一个容器，数据只能后进先出，这个容器可以是vector，也可以是list甚至更多的数据结构。也就是说我们如果以vector作为stack的底层数据结构，stack的尾插就可以使用vector的push_back()，尾删就可以使用vector的pop_back()。以vector作为stack的底层数据结构也是一样的，只是使用了list的接口，这就是一种适配器的模式。

stack是一个模板类，有两个模板参数，T标识存储的数据类型，container表示实现stack的底层数据结构。

stack我们更常用vector作为被封装的类

#pragma once
#include<vector>
#include <list>namespace my_stack
{template<class T, class container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:container _con;};
}

二、队列（queue）

1.queue的使用

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

queue的接口也差不多：

测试代码：

#include<iostream>
#include<queue>
using namespace std;void test()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!s.empty()){cout << s.front() << " ";q.pop();}
}int main()
{test()return 0;
}

2.queue的模拟实现

依然是代码的复用，不过这次是先进先出。

queue我们更常用list作为被封装的类

#pragma once
#include<vector>
#include<list>namespace my_queue
{template<class T, class container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:container _con;};
}

三、双端队列（deque）

在stack和deque中都有一个缺省的被封装的类以实现适配器，这个缺省值为什么既不是vector也不是list，而是deque呢？最主要的原因还是vector，list各有其优缺点。

1.vector，list的优缺点

vector

优缺点：支持随机访问，但是头部和中部的插入删除效率低，并且还需要扩容操作。

list

优缺点：list在任何地方插入删除效率都很高，但是链表不支持随机访问，且CPU高速缓存命中率低（CPU在访问内存时往往是取一块较大的内存，然后再其中找对应的数据位置，链表开辟的每一个节点的地址位置时不确定的，所以相比于连续的vector，缓存的命中率低）

而deque这个类是一个缝合怪，它既有vector的随机访问，也有list的高效率插入删除。所以对于这里选择deque最好。

2.认识deque

（1）底层原理

我们再cplusplus网站中可以查看deque：

deque - C++ Reference (cplusplus.com)

这是deque实现的思路：

deque是由中控和一段一段的buffer数组组成的，也就是说deque并不是完全连续的空间，它是由一段一段这样的buffer数组通过算法拼接而成，而所谓中控其实是一个指针数组，每一个元素都保存着各个buffer的数组指针。我们可以大致理解为C语言中的二维数组或者C++的vector>。

它的头尾插大概是这样的：

查找也是一样，先在map找buffer，再在buffer找数据。

我们可以很明显地发现它的下标访问相比vector一定是复杂而又缓慢的。当deque在中间插入数据时，它挪动数据的算法可就比vector复杂多了，与list相比的消耗就更大了。

（2）迭代器

由于deque的迭代器设计也很复杂，所以deque不适合遍历操作。在遍历时，deque的迭代器要频繁地检测其是否移动到数组buffer的的边界，这就导致它的访问效率很低下。而在现实中，遍历操作的使用是很频繁的，所以需要线性结构时，大多数情况下都会考虑vector和list，deque的应用很少，而我们目前能看到的一个就是：在STL中作为stack和queue的底层数据结构。

我们大致看一下它的迭代器的实现：

deque的维护需要两个迭代器，分别是start和finsh。因为deque更多时候是作为stack和queue的底层默认容器来使用的，所以一般deque是不需要在中间插入数据的，那么有了分别指向数据头尾的start和finsh就可以很好地处理头插与尾插。迭代器中的frist和last指向buffer的头尾，如果buffer满了，就可以通过node链接到map主控再新开辟buffer。其中的头部和尾部数据获取top()和back()就通过start的cur和finish的cur控制。

总的来说，deque虽然集成了vector和list的优点，但它也不是完美的，而在写代码中我们大部分时间都会追求极致，它也就很少用到了。

四、priority_queue-优先级队列

优先级队列（priority_queue）虽然叫队列，但它不满足先进先出的条件，优先级队列会保证每次出队列的元素是队列所有元素中优先级最高的那个元素，这个优先级可以通过元素的大小等进行定义。比如定义元素越大（或越小）优先级越高，那么每次出队，都是将当前队列中最大（最小）的那个元素出队，它的底层其实就是一个堆，也就是二叉树的结构。

1.priority_queue的使用

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

测试代码：

#include<iostream>
using namespace std;
void test()
{priority_queue<int> p;p.push(7);p.push(1);p.push(9);p.push(2);p.push(3);p.push(4);while (!p.empty()){cout << p.top() << " ";p.pop();}
}
int main()
{test();return 0;
}

2.priority_queue的模拟实现

我这里建的是小堆，大堆也是同理，如果不记得向上向下调整，可以看这里：

(6条消息) 二叉树详解_聪明的骑士的博客-CSDN博客

template<typename T, class container = vector<T>>
class priority_queue
{
public:template<class iterator>priority_queue(iterator first, iterator last)//建堆:_con(first, last){for (size_t i = (_con.size() - 1 - 1) / 2; i >= 0; --i)//所有节点的父节点全部向下调整，size()减1得到尾下标，再减1除2得到父节点{adjust_down(i);}}void adjust_down(size_t parent){size_t min_child = parent * 2 + 1;while (min_child < _con.size()){if (min_child + 1 < _con.size() && _con[min_child] > _con[min_child + 1]){minchild++;}if (_con[min_child] < _con[parent]){std::swap(_con[min_child], _con[parent]);parent = min_child;min_child = parent * 2 + 1;}elsebreak;}}void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (parent >= 0){if (_con[parent] > _con[child]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}void push(const T& x){_con.push_back(x);_con.adjust_up(_cons.size() - 1);}void pop(){assert(!_con.empty());std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}const empty() const{return _con.empty();}size_t size() const{return _con.size();}private:container _con;
};

3.仿函数

（1）什么是仿函数

仿函数(functor)，就是使一个类的使用看上去像一个函数。本质就是在类中实现一个()的重载函数，这个类就有了类似函数的行为，就成为一个仿函数类了。

namespace function
{template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class more{public:bool operator()(const T& x, const T& y){return x > y;}};
}
int main()
{function::less<int> lessFunc;//创建一个变量if (lessFunc(3, 2))//用变量也可以达到函数的效果cout << "yes" << endl;elsecout << "no" << endl;return 0;
}

（2）仿函数的使用

我们写一个插入排序

namespace sort
{template<class T>void insert_sort(T* arr, size_t size){int i = 1;for (i = 1; i < size; ++i){int j = i;while (j > 0){if (arr[j - 1] < arr[j]){std::swap(arr[j - 1], arr[j]);--j;}elsebreak;}}}
}

排序一个数组

int main()
{int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };sort::insert_sort<int>(arr, sizeof(arr) / sizeof(arr[0]));for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){printf("%d ", arr[i]);}
}
//结果：0 1 2 3 4 5 6 7 8 9

我们发现，如果我们想把数组排为降序，那么就要改变底层代码中的arr[j - 1] < arr[j]变为arr[j - 1] > arr[j]，再大部分情况下，使用者都是不能看到代码的实现的，使用者也就不能更改为排降序。那么我们是否可以通过加一个函数指针来实现呢？

template

void insert_sort(T* arr, size_t size, bool (*ptr)(int, int))

函数指针最直观的特点就是它太不直观了，阅读性很低，而且这个函数还要传递更多的参数。

所以我们为什么部添加一个仿函数的模板参数来实现升降序的控制呢？

我们修改一下，就可以正常运行了：

template<class T, typename compare>
void insert_sort(T* arr, size_t size, typename compare)
{int i = 1;for (i = 1; i < size; ++i){int j = i;while (j > 0){if (compare(arr[j - 1], arr[j])){std::swap(arr[j - 1], arr[j]);--j;}else{break;}}}
}void test_insertSort()
{func::less<int> lessFunc;int arr[] = { 9,8,7,6,5,4,3,2,1,0 };insert_sort(arr, sizeof(arr) / sizeof(arr[0]), lessFunc);for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){printf("%d ", arr[i]);}
}int main()
{test_insertSort();return 0;
}

在比较内置类型时，可以直接使用大于小于号，而比较自定义类型的大小，我们可以通过大于小于的重载确定类型比较大小的方式。但是如果传递的参数是指针类型，我们传指针大部分时候都是为了比较指针指向的数据，如果只是比较指针的数值本身，就失去比较的意义了。

那么对于指针的比较就不应该沿用之前的比较方式，所以我们创建一个struct（类-默认公共类），然后通过函数模板的调用，实现了比较非自定义变量指针的大小，相当于堆指针的特殊化处理。

#include <iostream>
#include <queue>
#include <functional>using namespace std;class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}private:int _year;int _month;int _day;
};struct PDateLess
{bool operator()(const Date* d1, const Date* d2){return *d1 < *d2;}
};struct PDateGreater
{bool operator()(const Date* d1, const Date* d2){return *d1 > *d2;}
};void TestPriorityQueue()
{// 大堆，需要用户在自定义类型中提供<的重载priority_queue<Date> q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout << q1.top() << endl;// 如果要创建小堆，需要用户提供>的重载priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout << q2.top() << endl;// 大堆priority_queue<Date*, vector<Date*>, PDateLess> q3;q3.push(new Date(2018, 10, 29));q3.push(new Date(2018, 10, 28));q3.push(new Date(2018, 10, 30));cout << *q3.top() << endl;// 小堆priority_queue<Date*, vector<Date*>, PDateGreater> q4;q4.push(new Date(2018, 10, 29));q4.push(new Date(2018, 10, 28));q4.push(new Date(2018, 10, 30));cout << *q4.top() << endl;
}int main()
{TestPriorityQueue();return 0;
}