C++——栈、队列、优先级队列

C++——栈、队列、优先级队列

一、栈——stack

（一）stack的原理

  stack就是一个“后进先出”的栈，元素从尾部插入，从尾部取出；

（二）stack的接口

	1、push()-----入栈；2、pop()------出栈；3、empty()----判断栈是否为空；4、top()------获取栈顶元素；5、size()-----获取栈中元素个数；

(三）stack模拟实现

  stack是通过其他的容器来进行适配实现的，只要该容器内部能够实现上面的几个接口，就可以用来实现stack适配器；
  C++底层使用的是deque双端队列来实现的stack；这里模拟实现我使用的是vector容器来实现；

template<class T>
class my_stack
{
public://构造my_stack(){}void push(const T& val){_v.push_back(val);}void pop(){_v.pop_back();}T& top(){return _v.back();}const T& top() const{return _v.back();}size_t size() const{return _v.size();}bool empty(){return _v.empty();}private:vector<T> _v;
};

二、队列——queue

（一）queue的原理

  queue是一个“先进先出”的队列，元素从队尾插入，从队头取出；

（二）queue接口

	1、push()-------入队；2、pop()--------出队；3、front()------获取队首元素；4、back()-------获取队尾元素；5、empty()------判断队列是否为空；6、size()-------获取队列元素个数；

（三）queue模拟实现

  queue是通过其他的容器来进行适配实现的，只要该容器内部能够实现上面的几个接口，就可以用来实现queue适配器；
  C++底层使用的是deque双端队列来实现的queue；这里模拟实现我使用的是list容器来实现；

template<class T>
class my_queue
{
public:my_queue(){}void push(const T& val){_lst.push_back(val);}void pop(){_lst.pop_front();}T& front(){return _lst.front();}const T& front() const{return _lst.front();}T& back(){return _lst.back();}const T& back() const{return _lst.back();}size_t size() const{return _lst.size();}bool empty(){return _pty();}private:list<T> _lst;
};

三、优先级队列——priority_queue

（一）priority_queue的实现原理

  priority_queue是通过堆来进行实现的，priority_queue默认的每次出队都会获取到堆中最大的元素，所以priority_queue默认为大根堆；

（二）priority_queue的接口

	1、push()------入队；2、pop()-------出队；3、empty()-----判断队列是否为空；4、top()-------获取堆顶元素；

（三）priority_queue的模拟实现

  priority_queue的模板参数有三个，第一个是元素的类型，第二个是所使用的容器类型（默认使用vector容器），第三个是可以自定义堆的类型（默认为大根堆）；

template<class T>
class Less
{
public://重载()运算符bool operator()(const T& val1, const T& val2){return val1 < val2;}
};template<class T>
class Greater
{
public:bool operator()(const T& val1, const T& val2){return val1 > val2;}
};template<class T, class Container = vector<T>, class Compare = Less<T>>
class my_priority_queue
{
public:my_priority_queue() {}template<class InputIterator>my_priority_queue(InputIterator first, InputIterator last){while (first != last){push(*first);first++;}}//向上调整void shiftUp(size_t child){size_t parent = (child - 1) / 2;while (child > 0){if (_com(_v[parent], _v[child])){swap(_v[child], _v[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}//向下调整void shiftDown(size_t parent, size_t sz){size_t child = parent * 2 + 1;while (child < sz){if (child + 1 < sz && _com(_v[child], _v[child + 1]))child++;if (_com(_v[parent], _v[child])){swap(_v[parent], _v[child]);parent = child;child = parent * 2 + 1;}elsebreak;}}void push(const T& val){_v.push_back(val);shiftUp(_v.size() - 1);}void pop(){swap(_v[0], _v[_v.size() - 1]);_v.pop_back();shiftDown(0, _v.size());}T& top(){return _v.front();}bool empty(){return _v.empty();}size_t size(){return _v.size();}private:Container _v;Compare _com;
};