容器适配器 stack、queue、priority

容器适配器 stack、queue、priority_queue

stack 是一种容器适配器,为什么叫它适配器呢？适配器是啥意思?

就是把一种接口转换为另一种接口, 在 C++ 封装了一些基本的容器，使之具备了新的调用接口（函数功能），就比如把 deque 封装一下变为一个具有 stack 功能的数据结构，新得到的数据结构就叫适配器，C++ 中适配器一共有三种，分别是 stack，queue ，priority_queue;

queue (队列)也是一种容器适配器，从队尾端插入元素，队头端弹出元素

优先级队列 priority_queue 也是容器适配器，其底层结构并不是 deque, 而是 vector 数组，第一个元素总是最大的，依次降之，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority_queue 可以看做是堆,：默认情况下 priority_queue 是大堆

基本操作

// 默认情况下，创建的是大堆，其底层按照小于号比较
    vector<int> v{  3,2,7,6,0,4,1,9,8,5 };
    priority_queue<int> q1(v.begin(),v.end());
    cout << q1.top() << endl;//9
    // 如果要创建小堆，将第三个模板参数换成greater比较方式
    priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
    cout << q2.top() << endl;//0

如果优先级队列放的是自定义数据类型，还需要程序猿重载 > 和 < 符号以及 cout<< ，有时候还需要提供比较器的规则

stack 和 queue 为什么不选择 list 或 vector 最为底层结构？

stack 是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，所以其实 vector 和 list 都可以作为 stack 的底层结构，但是为什么选择 deque 是因为 stack 和 queue 不需要遍历，只需要固定在一端或两端操作即可，还有一个理由就是 stack 在元素增长的时候，deque 比 vector 效率高，而且内存使用率也高。

stack 模拟实现

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;
};

queue 模拟实现

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;
};