目录
栈和队列的实现
优先级队列的实现
仿函数
栈和队列的实现
在C++的STL中栈和队列是两种容器适配器。容器适配器是通过封装其他容器的接口来实现的一种特殊容器。
Stack的底层可以是deque，也可以是list和vector。queue的底层可以是deque，也可以是list（vector头删效率低）。不同的底层容器需要传递不同的模板参数来实现。
所有的操作都是复用的其他容器的操作，但是他们内部不提供迭代器，如果要遍历内部元素取栈顶/取对头，再删除即可。
#pragma once
#include<deque>
namespace lzk
{ //在测试文件中打开了sdt且包含了头文件//就不用在deque前面标明stdtemplate<class T, class Container = std:: deque<T>>class stack{public:void push_back(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top() const{return _con.back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}#pragma once
#include<deque>
namespace lzk
{template< class T, class Container = deque<T>>class queue{public:void push_back(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& front(){return _con.front();}const T& fonst() const{return _con.front();}T& back(){return _con.back();}const T& back() const{return _con.back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}优先级队列的实现
优先级队列的底层是vector，vector中的元素是按堆（默认是大堆）的结构来排列的。如果要排列不同的堆结构需要显示传递模板参数。
实现优先级队列需要复用vector中的接口，需要了解堆的调整算法，在插入时，向上调整；在删除时，向下调整，还需要实现仿函数。
仿函数
仿函数是C++中一种行为类似函数的对象，它通过重载函数调用运算符operator()来实现。仿函数比普通函数更灵活，可以拥有状态，并且可以作为模板参数传递。在比较需求不同时，可以通过传递不同的函数对象来满足需求。
//仿函数template<class T>class less{public://重载()bool operator()(const T &x, const T& y){return x < y;}};template<class T>class less<T*>{public://重载()bool operator()(const T* const &x, const T* const & y){return x < y;}};//使用不同类别的仿函数可以按需求来比较数据template<class T>class greater{public:bool operator()(const T& x, const T& y){return x > y;}};template<class T>class greater<T*>{public:bool operator()(const T* const & x, const T*const & y){return *x > *y;}};
template<class T, class Container = std::vector<T>, class compare = less<T>>class priority_queue{public:void push(const T& x){_con.push_back(x);//AdjustUp();AdjustUp(_con.size() - 1); }void AdjustUp(int child){//compare是一个类型，可以实例化对象compare com;int parent = (child - 1) / 2;while (parent >= 0){//if (_con[child] > _con[parent])//利用仿函数//if(com(&_con[parent] , &_con[child]))if(com(_con[parent] , _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (parent - 1) / 2;}else {break;}}}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//AdjustDown();AdjustDown(0);//adjustdown(0);}void AdjustDown(size_t parent){ compare com;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() && com(&_con[child] , &_con[child + 1]))if (child + 1 < _con.size() && com(_con[child] , _con[child + 1])){child++;}//if (com(&_con[parent] , &_con[child]))if (com(_con[parent] , _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = child * 2 + 1;}else {break;} }} //取堆顶数据const T& top() const{return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}"🚀 保持热爱，继续 Coding！"
