[STL --stack_queue详解]stack、queue，deque,priority_queue，容器适配器

stack

stack介绍

1、stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2、stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

 stack的使用

常用操作：

push	尾部插入
pop	尾部删除元素
top	取栈顶元素
empty	判空操作

stack的模拟实现

从stack的接口中，我们发现stack是一种特殊的vector，因此可以用vector完全模拟实现stack;

namespace bit {/*template<class T>class stack {private:T* _a;int _top;int _capacity;};*///可维护性//设计模式//适配器  -- 转换template<class T,class Container =vector<T>>class stack {public:void push(const T&x) {_con.push_back(x);}void pop() {_con.pop_back();}bool empty() {return _con.empty();}const T& top() {return _con.back();}size_t size() {return _con.size();}private:Container _con;};
}

当然用list,deque也可以模拟实现栈；

bit::stack<int, list<int>>s;
bit::stack<int, vector<int>>s;
bit::stack<int, deque<int>>s;

queue

queue介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

queue的使用

push	队尾插入
pop	对头删除
front	返回对头元素的引用
back	返回队尾元素的引用
empty	队列是否为空
size	队列元素有效个数

priority_queue 

这里的priority_queue是按照优先级出的，底层实现是堆结构；

这里补充一下要用到的堆的知识点：

堆向上调整：

		void AdjustUp(int child) {int parent = (child - 1)/2;while (child>0) {if (_con[parent]< _con[child]) {swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else {break;}}}

堆向下调整：

void AdjustDown(int parent) {int child = parent * 2 + 1;while (child < _con.size()) {if (child+1<_con.size() && _con[child] < _con[child + 1]) {child++;}if (_con[parent] < _con[child]) {swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else {break;}}}

在模拟实现优先队列前，我们先了解一下仿函数：

 仿函数是什么？

看一段代码：

class Func {
public:
    //operator()就是函数名
    void operator()() {
        cout << "func调用" << endl;
    };
};

调用：

    Func f;
    f();
    f.operator()();

 仿函数（Functor） 是一种行为类似函数的对象，它可以被用作函数并接受参数。在C++中，仿函数通常是重载了函数调用运算符operator()的类对象。通过重载operator()，仿函数可以像函数一样被调用，并且可以保存状态信息。

这样利用仿函数，我们就可以把向上调整和向下调整修改调用仿函数：

这样我们需要大堆或者小堆的话就不要每次都修改<，>了，

    template<class T,class Container = vector<T>,class Compare=myless<T>>

 只需要：

默认是大堆；

小堆： 

   bit::priority_queue<int, vector<int>, bit::mygreater<int>>q1(v.begin(), v.end());

下面让我们来模拟实现优先队列：

namespace bit {//仿函数template<class T>class myless {public:bool operator()(const T& x, const T& y) {return x < y;}};//仿函数template<class T>class mygreater {public:bool operator()(const T& x, const T& y) {return x > y;}};template<class T,class Container = vector<T>,class Compare=myless<T>>class priority_queue {public:template <class InputIterator>priority_queue(InputIterator first, InputIterator last) {while (first != last) {_con.push_back(*first);first++;}//建堆(从倒数第一个非叶子节点开始向下调整)for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) {AdjustDown(i);}}void AdjustUp(int child) {Compare comfunc;int parent = (child - 1)/2;while (child>0) {if (comfunc(_con[parent], _con[child])) {swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else {break;}}}void AdjustDown(int parent) {Compare comfunc;int child = parent * 2 + 1;while (child < _con.size()) {if (child+1<_con.size() && comfunc(_con[child] , _con[child + 1])) {child++;}if (comfunc(_con[parent] , _con[child])) {swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else {break;}}}void push(const T& x) {_con.push_back(x);AdjustUp(_con.size()-1);}void pop() {swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top() {return _con[0];}bool empty() {return _con.empty();}size_t size() {return _con.size();}private:Container _con;//底层核心};
}

queue的模拟实现

由于queue是一个双端操作，这里最后不要使用vector在模拟实现，如果用的话反而会比较麻烦。

可以选择list和deque来模拟实现；

    bit::queue<int, list<int>>s;
    bit::stack<int, deque<int>>s;

namespace bit {template<class T,class Container = list<T>>class queue {public:void push(const T& x) {_con.push_back(x);}void pop() {_con.pop_front();}bool empty() {return _con.empty();}size_t size() {return _con.size();}const T&top() {return _con.front();}private:Container _con;};
}

deque简单介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

简单的说，deque在功能上就是vector和list的结合。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。
 

什么是适配器？

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque。