stack和queue是容器适配器(container adaptor)
stack是设置成LIFO(后进先出)
queue是设置成FIFO(先进先出)
一.stack
1.stack的接口
这个接口也就只有这些实现起来也不叫简单，我们就直接看代码吧
2.stack的实现(用vector)
这里使用的方法是has-a就是类中有vector的成员也可以用遗传的方法实现
template<class T>
class Stack
{
public:
Stack()
{}
void push(const T& v) { _c.push_back(v); }
void pop()
{
_c.pop_back();
}
T& top()
{
return _c.back();
}
const T& top()const
{
return _c.back();
}
size_t size()const
{
return _c.size();
}
bool empty()const
{
return _c.empty();
}
private:
std::vector<T> _c;
};
二.queue
1.queue的接口
我们注意queue这个是先进先出的
2.queue的实现
template<class T>
class Queue
{
public:
Stack()
{
}
void push(const T& v) { _c.push_back(v); }
void pop()
{
_c.pop_front();
}
T& top()
{
return _c.front();
}
const T& top()const
{
return _c.front();
}
size_t size()const
{
return _c.size();
}
bool empty()const
{
return _c.empty();
}
private:
std::lisy<T> _c;
};
通过实现stack和queue的一些接口我们不需要关注他们的底层如何实现的我们就可以使用这些接口体现了封装的概念
三.priority_queue
优先级队列是一个容器适配器，根据严格的若排序标准，他的第一个元素默认是最大的。
此上下文类似于堆，再堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
优先级队列被实现为容器适配器，容器适配器即将特定的容器类封装作为底层的类，queue提供一套特殊的成员函数访问元素。元素也从尾部弹出，其称为优先队列的顶部
他底层的容器可以是各种容器，也可以是特殊设计的容器类，容器可以通过随机访问迭代器访问，支持一下操作
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素
vector和deque满足要求，如果没有特定的priority_queue类实例化指定 容器默认情况使用vector
需要支持随机访问来保持堆的结构容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作
1.priority_queuq的接口
优先级队列默认情况下使用的是vector其作为底层存储的容器，再vector上使用了堆算法将vector中元素构造成堆的结构，因此priority_queue的接口是堆，所以需要用到堆的位置，都可以考虑priority_queue,注意默认情况下priority_queue是大堆
void TestPriorityQueue()
{
//默认情况下是大堆，底层使用小于号比较的 <
vector<int> v{ 3,2,7,6,0,4,1,9,8,5 };
priority_queue<int> q1;
for (auto& e : v)
q1.push(e);
cout << q1.top() << endl;
// 如果要创建小堆，将第三个模板参数换成greater比较方式 >
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
}
如果priority_queue中存的是自定义类型的元素他的比较会调用这个类型的重载比较
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;
};
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;
}
2.priority_queue的实现
实现堆的关键点在于向上调整和向下调整算法
void AdjustUp(int child)
{
int parent = (child - 1) >> 1;
while (child)
{
if (comp(c[parent], c[child]))
{
T tmp = c[parent];
c[parent] = c[child];
c[child] = tmp;
child = parent;
parent = (child - 1) >> 1;
}
else
{
return;
}
}
}
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while(child<c.size())
{
if (child+1<c.size()&&comp(c[child], c[child + 1]))
{
child += 1;
}
if (comp(c[parent], c[child]))
{
std::swap(c[parent], c[child]);
parent = child;
child = 2 * parent + 1;
}
else return;
}
}
这是建堆的核心，我们在设计这个类就比较方便实现他的接口了
奥对了这个地方实现优先级队列如果想要频繁切换大小的优先级的话这里设计仿函数更加方便。这里库里面默认是大堆且比较的仿函数用的是less我们也复刻一下。
template<class T>
struct less
{
bool operator()(const T& left,const T& right)const
{
return left < right;
}
};
template<class T>
struct greater
{
bool operator()(const T& left, const T& right)const
{
return left > right;
}
};
这个仿函数其实是一个类这个类重载了()我们可以看到需要传两个参数比较会返回bool值(如果是less就返回第一个参数是否小于第二个)。
特别说一下这里用迭代器区间构造这个堆---先用类里面的容器把数据拷贝一份(不管是不是堆)然后从后往前调用向上调整算法(保证这一小部分是一个堆)然后在--往前弄(我们的底层是一个数组这里就用的是小标的方式)
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: c(first, last)
{
int count = c.size();
int root = (count - 2) / 2;
for (; root >= 0; --root)
{
AdjustDown(root);
}
}
其他的就比较简单了
template<class T>
struct less
{
bool operator()(const T& left,const T& right)const
{
return left < right;
}
};
template<class T>
struct greater
{
bool operator()(const T& left, const T& right)const
{
return left > right;
}
};
template <class T, class Container = vector<T>, class Compare = greater<T> >
class priority_queue
{
public:
priority_queue()
:c()
{
}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: c(first, last)
{
int count = c.size();
int root = (count - 2) / 2;
for (; root >= 0; --root)
{
AdjustDown(root);
}
}
bool empty() const
{
return size() == 0;
}
size_t size() const
{
return c.size();
}
T& top()
{
return c.front();
}
void push(const T& x)
{
c.push_back(x);
AdjustUp(c.size() - 1);
}
void pop()
{
if (empty())
{
return;
}
std::swap(c.front(), c.back());
c.pop_back();
AdjustDown(0);
}
private:
void AdjustUp(int child)
{
int parent = (child - 1) >> 1;
while (child)
{
if (comp(c[parent], c[child]))
{
T tmp = c[parent];
c[parent] = c[child];
c[child] = tmp;
child = parent;
parent = (child - 1) >> 1;
}
else
{
return;
}
}
}
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while(child<c.size())
{
if (child+1<c.size()&&comp(c[child], c[child + 1]))
{
child += 1;
}
if (comp(c[parent], c[child]))
{
std::swap(c[parent], c[child]);
parent = child;
child = 2 * parent + 1;
}
else return;
}
}
private:
Container c;
Compare comp;
};
四.思考
这里我这样子写不知道为什么这里会报一个模板实例化的问题有人知道是怎么回事吗?(VS2022)
这是怎么回事但是不影响程序运行
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2301_79976033/article/details/165992494
