当前位置：网站首页>stack和queue和优先级队列（大堆和小堆）模拟实现和仿函数讲解
stack和queue和优先级队列（大堆和小堆）模拟实现和仿函数讲解
2022-07-29 04:50:00 【韩悬子】
1.适配器简单了解
当我们写stack之前我们先来简单了解下适配器，就以我们手机充电为例子，大家都知道我们家用电是220，手机充电有个充电线，而手机充电的电源适配器，用不了那么高的电，会相应的降低，这样子会没有那么危险，而适配器最重要的作用是转换，转换成我想要的东西
2.stack模拟实现
写之前我们就要用到stack的适配器了，deque有了它实现栈就特别简单了，栈是先进后出
#pragma once
namespace stk
{
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();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
void test_stack()
{
stack<int> s;
//stack<int, vector<int>> s;
//stack<int, list<int>> s;
//stack<int, string> s; //
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(300);
while (!s.empty())
{
cout << s.top() << " ";
s.pop();
}
cout << endl;
}
};
这样子就写完了，可以看到写栈的代码特别简单，而且少，也好理解，因为写这个栈只要调用库里面封装好的函数就行了
上面test的代码
stack s;
stack<int, vector> s;
stack<int, list> s;
stack<int, string> s;
这些不同类型的都可以运行不会报错，
除了 stack<int, string> s; 为什么呢？
运行报告
会出现截断或者溢出的问题
2.queue模拟实现
和栈不一样的是先进先出
#pragma once
namespace que
{
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& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
void test_queue()
{
//queue<int> q;
queue<int, list<int>> q;
//queue<int, vector<int>> q; // 不行
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
}
这里要注意的是vector是不支持的，因为vector不支持头删
3.优先级队列
优先级队列我放在队列后面的
// 优先级队列 -- 大堆 < 小堆 >
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[parent], _con[child]);
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())
{
if (child+1 < _con.size() && _con[child] < _con[child+1])
{
++child;
}
if (_con[parent] < _con[child])
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
assert(!_con.empty());
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
void test_priority_queue()
{
priority_queue<int> pq;
pq.push(2);
pq.push(5);
pq.push(1);
pq.push(6);
pq.push(8);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
这样子就可以了，但是这样子控制大堆或者小堆就很麻烦，这个时候我们就用仿函数
仿函数其实是赋值来的但是看起来很像函数
template<class T>
struct less
{
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y) const
{
return x > y;
}
};
我们在模板里面加上greater，再把向上调整，和向下调整改下，我们就是小堆
代码
template<class T>
struct less
{
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y) const
{
return x > y;
}
};
// 优先级队列 -- 大堆 < 小堆 >
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
void AdjustUp(int child)
{
Compare comFunc;
int parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if (comFunc(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
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)
{
Compare comFunc;
size_t child = parent * 2 + 1;
while (child < _con.size())
{
//if (child+1 < _con.size() && _con[child] < _con[child+1])
if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1]))
{
++child;
}
//if (_con[parent] < _con[child])
if (comFunc(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
assert(!_con.empty());
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
void test_priority_queue()
{
/*less<int> LessCom; cout << LessCom(1, 2) << endl; greater<int> GreaterCom; cout << GreaterCom(1, 2) << endl;*/
//priority_queue<int> pq;
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(2);
pq.push(5);
pq.push(1);
pq.push(6);
pq.push(8);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
运行结果
我们不加上greator，因为我们默认是less是大堆
4.仿函数
仿函数的优点是用来代替函数指针
因为c++是c衍生过来的，所以c++是会支持c的用法
下面为了支持函数指针为什么怎么写，如果不指定函数地址，那么就会调用构造函数，如果没有写构造函数就是随机值，写了如果没有函数的地址，那么指向的就是空指针，那么函数的地址是什么，函数名就可以当函数的地址，所以才有了下面的写法
priority_queue<int, vector<int>, bool(*)(int, int)> pq(ComIntLess);
// 优先级队列 -- 大堆 < 小堆 >
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
Compare _comFunc;
public:
priority_queue(const Compare& comFunc = Compare())
:_comFunc(comFunc)
{
}
void AdjustUp(int child)
{
//Compare comFunc;
int parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[parent] < _con[child])
if (_comFunc(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
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)
{
//Compare comFunc;
size_t child = parent * 2 + 1;
while (child < _con.size())
{
//if (child+1 < _con.size() && _con[child] < _con[child+1])
if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1]))
{
++child;
}
//if (_con[parent] < _con[child])
if (_comFunc(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
assert(!_con.empty());
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
bool ComIntLess(int x1, int x2)
{
return x1 > x2;
}
void test_priority_queue()
{
//priority_queue<int, vector<int>, greater<int>> pq;
//priority_queue<int, vector<int>> pq;
priority_queue<int, vector<int>, bool(*)(int, int)> pq(ComIntLess);
pq.push(2);
pq.push(5);
pq.push(1);
pq.push(6);
pq.push(8);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
-
运行结果
如果没用函数指针默认就是大堆，因为之前用仿函数实现了，如果用函数指针实现大堆和上面实现小堆一样，其实可以看的出来函数指针比起仿函数来讲真的是麻烦太多了
接下来要比较下面的代码怎么用sort来比较
// 商品
struct Goods
{
string _name;
double _price;
size_t _saleNum;
};
void test_goods()
{
Goods gds[4] = {
{
"苹果", 2.1, 1000}, {
"香蕉", 3.0, 200}, {
"橙子", 2.2,300}, {
"菠萝", 1.5,50} };
}
这样子？
看到报错了，要比较可以用operator<
可以看到没有问题了，但是这只能比较价格啊，要是我想比较其他怎么办？而且继续用operator也不行因为只有一个相同的参数，也构不成函数重载。
这个时候就要看仿函数了
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <deque>
#include <functional>
#include <assert.h>
using namespace std;
#include"stack.h"
#include"queue.h"
// 商品
struct Goods
{
string _name;
double _price;
size_t _saleNum;
//bool operator<(const Goods& g) const
//{
// return _price < g._price;
//}
};
struct LessPrice
{
bool operator()(const Goods& g1, const Goods& g2) const
{
return g1._price < g2._price;
}
};
struct GreaterPrice
{
bool operator()(const Goods& g1, const Goods& g2) const
{
return g1._price > g2._price;
}
};
struct LessSaleNum
{
bool operator()(const Goods& g1, const Goods& g2) const
{
return g1._saleNum < g2._saleNum;
}
};
struct GreaterSaleNum
{
bool operator()(const Goods& g1, const Goods& g2) const
{
return g1._saleNum > g2._saleNum;
}
};
void test_goods()
{
int i = 0;
Goods gds[4] = {
{
"苹果", 2.1, 1000}, {
"香蕉", 3.0, 200}, {
"橙子", 2.2,300}, {
"菠萝", 1.5,50} };
sort(gds, gds + 4, LessPrice());
for (i = 0; i < 4; i++)
{
cout << gds[i]._name << " ";
cout << gds[i]._price << " ";
cout << gds[i]._saleNum << " ";
}
cout << endl;
sort(gds, gds + 4, GreaterPrice());
for (i = 0; i < 4; i++)
{
cout << gds[i]._name << " ";
cout << gds[i]._price << " ";
cout << gds[i]._saleNum << " ";
}
cout << endl;
sort(gds, gds + 4, LessSaleNum());
for (i = 0; i < 4; i++)
{
cout << gds[i]._name << " ";
cout << gds[i]._price << " ";
cout << gds[i]._saleNum << " ";
}
cout << endl;
sort(gds, gds + 4, GreaterSaleNum());
for (i = 0; i < 4; i++)
{
cout << gds[i]._name << " ";
cout << gds[i]._price << " ";
cout << gds[i]._saleNum << " ";
}
cout << endl;
}
int main()
{
test_goods();
return 0;
}
运行结果
可以看到很舒服，想比较什么就调用什么
边栏推荐
- Makefile(make)常见规则(二)
- [c language] PTA 7-51 sum the first n terms of odd part sequence
- 使用更灵活、更方便的罗氏线圈
- Pycharm reports an error when connecting to the virtual machine database
- 央企建筑企业数字化转型核心特征是什么？
- Configure st-gcn environment record [Google lab]
- How to build a mobile studio network?
- I++ and ++i details
- C language implementation of three chess
- EMI interference troubleshooting with near-field probe and current probe
猜你喜欢
让你的正则表达式可读性提高一百倍
File operation (Advanced C language)
Actual combat of flutter - DIO of request encapsulation (II)
SGuard64.exe ACE-Guard Client EXE：造成磁盘经常读写，游戏卡顿，及解决方案
Reveal安装配置调试
Laya中的A星寻路
Use jupyter (2) to establish shortcuts to open jupyter and common shortcut keys of jupyter
Redux quick start
How to avoid damage of oscilloscope current probe
C language implementation of three chess
随机推荐
EF core: one to one, many to many configuration
def fasterrcnn_resnet50_fpn（）实例测试
Un7.28: common commands of redis client.
Auto.js脚本开发入门
【Express连接MySQL数据库】
GCC基础知识
正确的用户拖拽方式
How to avoid damage of oscilloscope current probe
EMI interference troubleshooting with near-field probe and current probe
[c language] PTA 7-50 output Fahrenheit Celsius temperature conversion table
Various configurations when pulsar starts the client (client, producer, consumer)
Corresponding order of 18 and 25coco data of openpose and joint points
Mysql:The user specified as a definer (‘root‘@‘%‘) does not exist 的解决办法
There are objections and puzzles about joinpoint in afterreturning notice (I hope someone will leave a message)
Use more flexible and convenient Rogowski coil
Auto.js脚本开发环境搭建
i++与++i详解
常见的限流方式
Hengxing Ketong invites you to the 24th China expressway informatization conference and technical product exhibition in Hunan
Mongo Shell交互式命令窗口