c++中的Stack与Queue

一·queue与stack：
1.queue介绍：
①队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供 一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。 

②只要是能满足对队列功能函数实现的容器，都可以作为它的底层容器。

底层容器具备条件：

empty：检测队列是否为空.

size：返回队列中有效元素的个数.

front：返回队头元素的引用.

back：返回队尾元素的引用.

push_back：在队列尾部入队列.

pop_front：在队列头部出队列.

③但是默认的是deque（一种双端队列，后续讲到）。

2.queue模拟实现：
#pragma once
namespace sq {
    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;
 
    };
}
 

3stack介绍：
同上面queue也是容器适配器，本身不是容器，但是有底层容器，像list，vector这样的容器都可以做，但是默认是deque。

4stack模拟实现：
#pragma once
namespace sq {
    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;
    };
}
 
 

二·priority_queue（优先队列）：
1·介绍：
①容器适配器，它的第一个元素是最大的元素。

②理想结构类似于堆，只能访问它的top（访问队头，删队头时候与队尾互换，再删除）。

③底层容器用vector和list都可以，但是一般默认为vector。

④含有的接口函数：

priority_queue()与priority_queue(first, last) 构造一个空的优先级队列，也可以用迭代器区间初始化。

empty( ) 检测优先级队列是否为空，是返回true，否 则返回false。

top( ) 返回优先级队列中最大(最小元素)，即堆顶元 素。

push(x) 在优先级队列中插入元素x。

pop() 删除优先级队列中最大(最小)元素，即堆顶元 素。

2·仿函数：
即一种模版，它重载了operator()；使得该模版类的对象可以像函数一样使用。如：

 template<class T>
 class Great {
 public:
     bool operator()(const T& a, const T& b) {
         return a > b;
     }
 };
 
 template<class T>
 class Less {
 public:
     bool operator()(const T& a, const T& b) {
         return a < b;
     }
 };
仿函数特性：

在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态。

仿函数即使定义相同，也可能有不同的类型。

仿函数通常比一般函数速度慢。

仿函数使程序代码变简单。

3·模拟实现：
#pragma once
#include<vector>
namespace pq
 
{
    template<class T>
    class Great {
    public:
        bool operator()(const T& a, const T& b) {
            return a > b;
        }
    };
 
    template<class T>
    class Less {
    public:
        bool operator()(const T& a, const T& b) {
            return a < b;
        }
    };
 
   
 
    template <class T, class Container = vector<T>, class Compare = pq::Less<T> >
 
 
    //默认less大堆
    class priority_queue
 
    {
 
    public:
        //保证原来堆都是有一定大小堆序的，故上调
        void upadjust(int  child) {
            int parent = (child-1)/2;
            while (child > 0) {
                if (com(c[parent],c[child])) {
                    swap(c[child] ,c[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
 
                }
                else {
                    break;
                }
            }
 
        }
        void downadjust(int parent) {
            int child = 2 * parent + 1;
            while (child<c.size()) {
                if (child+1<c.size()&&com(c[child], c[child + 1])) {
                    child++;
                }
                
                if (com(  c[parent],c[child])) {
                    swap(c[child], c[parent]);
                    parent=child;
                    child = 2 * parent + 1;
 
 
                }
                else {
                    break;
                }
            }
 
 
        }
        priority_queue() {
 
        }
 
        template <class InputIterator>
 
        priority_queue(InputIterator first, InputIterator last) {
            while (first != last) {
                c.push_back(*first);
                upadjust(c.size() - 1);
                first++;
           }
 
        }
 
      const  bool empty() const {
            return c.empty();
        }
 
        const size_t size() const {
            return c.size();
        }
 
       const T& top() const {
            return c.front();
        }
 
        void push(const T& x) {
            c.push_back(x);
            upadjust(c.size() - 1);
        }
 
            void pop() {
            swap(c[0], c[c.size() - 1]);
            c.pop_back();
            downadjust(0);
        }
 
    private:
 
        Container c;
 
        Compare com;
 
    };
 
}

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

简单来说就是：它自己不是容器，用的其他的容器进行封装然后再使用，那么这个类就是容器适配器。

比如queue和stack的实现它们就是容器适配器，但它们不是容器，而是对底层容器进行封装，即对deque封装。

如：

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

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

如：

访问它就可以利用类似二维数组，但是它的底层实现是复杂的，如要判断数据相对位置，控制四个指针的指向。故通常作为了解即可。

当然可以理解为它是vector和list结合，但并不完全。与vector相比，它头插，头删，尾插，可以直接进行，不用大量挪动以及容量不足的时候扩大量空间，与list相比，它的底层空间中控数组里面存着的指针所指向的数组是连续的，这样就可以提高一定空间利用率。

但是不可能能完全综合了优点，还存在个致命的缺点：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其 是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际遍历不用它。 故这里只是在stack和queue的封装，底层用了它。

那为什么这里会用deque而不是vector或者list：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进 行操作。

2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的 元素增长时，deque不仅效率高，而且内存使用率高。