模拟实现：
namespace bit { #include<deque> template<class T, class Con = deque<T>> class stack { public: stack() {} 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.empty(); } private: Con _c; }; template<class T, class Con = deque<T>> class queue { public: queue() {} 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.empty(); } private: Con _c; }; };priority_queue:
namespace bit { //函数对象 less template<class T> struct less { bool operator()(const T& left, const T& right) { return left < right; } }; //函数对象 greater template<class T> struct greater { bool operator()(const T& left, const T& right) { return left > right; } }; namespace bit { //函数对象 less template<class T> struct less { bool operator()(const T& left, const T& right) { return left < right; } }; //函数对象 greater template<class T> struct greater { bool operator()(const T& left, const T& right) { return left > right; } }; template <class T, class Container = std::vector<T>, class Compare = less<T> > class priority_queue { public: //创建空的优先级队列 priority_queue():c() {} template <class InputIterator> priority_queue(InputIterator first, InputIterator last) :c(first, last) { //将c中的元素调整为堆的结构，默认为大堆 int count = c.size(); int root = ((count - 2) >> 1); for (; root >= 0; root--) AdjustDown(root); } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } // 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性 const T& top() const { return c.front(); } void push(const T& x) { c.push_back(x); //push_heap(c.begin(), c.end(), comp); 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 (Com(c[parent], c[child])) { std::swap(c[child], c[parent]); child = parent; parent = ((child - 1) >> 1); } else return; } } //向下调整 void AdjustDown(int parent) { int child = parent * 2 + 1; while (child < c.size()) { // 找以parent为根的较大的孩子 if (child + 1 < c.size() && Com(c[child], c[child+1])) child += 1; // 检测双亲是否满足情况 if (Com(c[parent], c[child])) { std::swap(c[child], c[parent]); parent = child; child = parent * 2 + 1; } else return; } } private: Container c; Compare Com; }; };
