stack,queue,priority_queue的模拟实现及常用接口

#include<queue>
#include<iostream>
#include<list>
using namespace std;
int main()
{priority_queue<int> s1;s1.push(5);s1.push(3);s1.push(7);s1.push(2);s1.push(6);while (!s1.empty()){cout <<s1.top()<<" ";s1.pop();}return 0;
}

3.2 priority_queue的模拟实现

priority_queue的底层就是一个堆，因此它的模拟实现，和堆的类似

#include<vector>
namespace chuxin
{// 默认是大堆template<class T, class Container = vector<T>>class priority_queue{public:void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void AdjustDown(int parent){// 先假设左孩子小size_t child = parent * 2 + 1;while (child < _con.size())  // child >= n说明孩子不存在，调整到叶子了{// 找出小的那个孩子if (child + 1 < _con.size() && _con[child] < _con[child + 1]){++child;}if (_con[parent] < _con[child]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}

这种方法还是有缺陷，发现只能排降序，有没有一种方法既能排升序又能排降序？这时候就需要仿函数了

3.3 仿函数

来看看下面这段冒泡排序

void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){// 单趟int flag = 0;for (int i = 1; i < n - j; i++){if (a[i] < a[i - 1]){swap(a[i - 1], a[i]);flag = 1;}}if (flag == 0){break;}}
}

发现它的逻辑是排一个升序，如果要排一个降序怎么办，为了一个比较重载一个大部分相似的函数，显然不怎么好，而且比较的数据可能不同，有时候比较整形，有时候是浮点型，这时候就可以利用模版自己写一个比较函数，而这个函数称为仿函数

// 仿函数：本质是一个类，这个类重载operator(),他的对象可以像函数一样使用
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};
template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};
template<class Compare>
void BubbleSort(int* a, int n, Compare com)
{for (int j = 0; j < n; j++){// 单趟int flag = 0;for (int i = 1; i < n - j; i++){//if (a[i] < a[i - 1])if (com(a[i], a[i - 1])){swap(a[i - 1], a[i]);flag = 1;}}if (flag == 0){break;}}
}
int main()
{Less<int> LessFunc;Greater<int> GreaterFunc;// 函数对象cout << LessFunc(1, 2) << endl;cout << LessFunc.operator()(1, 2) << endl;int a[] = { 9,1,2,5,7,4,6,3 };BubbleSort(a, 8, LessFunc);BubbleSort(a, 8, GreaterFunc);BubbleSort(a, 8, Less<int>());BubbleSort(a, 8, Greater<int>());return 0;
}

此时就发现，改变是否是升降序，就可以利用两个类对象就可以做到，此时priority_queue的比较就是这样

#include<vector>
template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};
namespace chuxin
{// 默认是大堆template<class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{public:void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void AdjustDown(int parent){// 先假设左孩子小size_t child = parent * 2 + 1;Compare com;while (child < _con.size())  // child >= n说明孩子不存在，调整到叶子了{// 找出小的那个孩子//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}