当前位置：首页 > news >正文

c++:stack,queue,priority_queue模拟实现

news 2024/11/9 0:20:29

一、stack模拟实现

namespace mystack
{template<class T, class Con = deque<T>>class stack{public:void push(const T& x){_c.push_back(x);}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.size()==0;}private:Con _c;};

二、queue模拟实现

template<class T, class Con = deque<T>>class queue{public:void push(const T& x){_c.push_back(x);}void pop(){_c.pop_front();}T& back(){return _c.back();}const T& back()const{return _c.back();}T& front(){return _c.front();}const T& front()const{return _c.front();}size_t size()const{return _c.size();}bool empty()const{return _c.size()==0;}private:Con _c;};

三、priority_queue模拟实现

    template <class T, class Container = vector<T>, class Compare = less<T> >class priority_queue{public:priority_queue(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first!=last){push(*first);++first;}}bool empty() const{return c.empty();}size_t size() const{return c.size();}const T& top() const{return c.front();}void Adjustup(int child){int parent = (child - 1) / 2;while (child>0){if (comp(c[child] , c[parent])){std::swap(c[child], c[parent]);child = parent;parent = (child - 1) / 2;}else{//孩子小于父亲就退出break;}}}void push(const T& x){c.push_back(x);Adjustup(c.size()-1);}void Adjustdown(int parent){int child = parent * 2 + 1;while (child < c.size()){if (c.size() > (child + 1)&& comp(c[child] , c[child + 1])){//找出两个孩子节点中较大的那个++child;}//父亲小于孩子if (comp(c[child] , c[parent])){std::swap(c[child], c[parent]);parent = child;child = parent * 2 + 1;}else {break;}}}void pop(){if (!empty()){std::swap(c[0], c[c.size() - 1]);c.pop_back();Adjustdown(0);}}private:Container c;Compare comp;};

这里的比较是自己实现的operator()来实现比较的，叫仿函数。库里传less建大堆，传greater建小堆，我为了好理解实现的是反过来的。

    template <class T>struct less{public:bool operator()(const T&x, const T& y) {return x < y;}};template <class T>struct greater{public:bool operator()(const T& x, const T& y) {return x> y;}};