STL容器适配器之stack与queue

1.stl里的stack与queue和string、vector、list等容器不一样，它们是容器适配器；

2.容器适配器的本质是一种复用，不需要自己实现储存结构，而是根据需求提供接口，储存结构靠其他容器。反向迭代器是由正向迭代器适配出来的；

3.适配器这种思想是一种设计模式；

4.stack与queue没有迭代器，不允许随便去遍历；

5.逆波兰表达式(后缀表达式)。平常我们写的算术表达式是中缀表达式，对于计算机不好识别优先级，所以计算机将中缀表达式转换成了后缀表达式。操作数顺序不变，运算符按照优先级进行了排列；

6.编译器只会向上查找，不向下找，这样是为了提高编译速度；

一、stack与queue的简单使用

template <class T, class Container = deque<T> > class stack;
template <class T, class Container = deque<T> > class queue;

其他容器的第二个模板参数都是空间配置器，而容器适配器都是使用其他容器；

1.stack的使用

在这里插入图片描述

stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
cout << st.size() << endl;
while (!st.empty())
{
    cout << st.top() << " ";
    st.pop();
}
cout << endl;

2.queue的使用

在这里插入图片描述

queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
cout << q.size() << endl;
while (!q.empty())
{
    cout << q.front() << " ";
    q.pop();
}
cout << endl;

二、模拟实现stack与queue

1.为了支持容器适配器，vector与list都提供了front()和back()接口；

2.类模板参数也支持缺省参数；

3.对于队列使用vector强行适配要挪动数据，效率低，所以库里面不支持vector适配，使用了pop_front();

1.stack

namespace Stack
{
    template <class T, class Container = deque<T>>
    class stack
    {
    public:
        void push(const T &val)
        {
            con_.push_back(val);
        }
        void pop()
        {
            con_.pop_back();
        }
        T &top()
        {
            return con_.back();
        }
        size_t size()
        {
            return con_.size();
        }
        bool empty()
        {
            return con_.empty();
        }

    private:
        Container con_;
    };
}

2.queue

namespace Queue
{
    template <class T, class Container = deque<T>>
    class queue
    {
    public:
        void push(const T &val)
        {
            con_.push_back(val);
        }
        void pop()
        {
            con_.pop_front();
        }
        T &front()
        {
            return con_.front();
        }
        T &back()
        {
            return con_.back();
        }
        size_t size()
        {
            return con_.size();
        }
        bool empty()
        {
            return con_.empty();
        }

    private:
        Container con_;
    };
}

三、deque双端队列

1.deque不是队列，而是可以前后都可以进行插入和删除的容器；

2.deque的迭代器是随机迭代器；

3.deque没有reserve()，有扩容逻辑，但是不可以一次开好空间；

1.deque的接口

Element access:

operator[]
at
front
back

Modifiers:

assign
push_back
push_front
pop_back
pop_front
insert
erase
swap
clear
emplace 
emplace_front 
emplace_back

2.对比vector与list

vector：优势：1.支持下标随机访问；2.CPU可以一片一片加载，实现高速缓存，缓存利用率高；劣势：1.存在扩容问题，异地扩容，然后拷贝数据，释放旧空间；2.存在中间和头部插入删除问题；

list：优势：1.任意位置都可以插入删除，按需申请释放；劣势：1.不支持下标访问；

3.deque的实现

先开辟n段连续的空间，每段空间的大小是固定的，再开辟一个中控数组(指针数组)。中控数组的中间部分开始，n个指针存放n段连续空间的地址。如果中控数组的空间满了，就进行扩容，代价比起vector的扩容要小得多，仅仅拷贝指针变量即可。

第一个buff数组从后往前插入。

在这里插入图片描述

迭代器的设计十分复杂，first指向buff的起始位置，last指向buff的末尾，cur指向当前访问的位置，node是一个二级指针指向中控数组，便于访问其他buff。start迭代器指向第一个buff，finish迭代器指向最后一个buff*it和判断!=使用的是cur，++使用的是使用了4个指针。

3.1特点

相较于vector，极大的解决了扩容问题、头插头删问题，但是[]的实现就比较复杂，需要先计算再哪一个buff数组里，然后计算哪一个buff的哪一个位置。如：1.先计算在不在第一个buf数组，在就按位置访问；2.不在第一个buff数组，减去第一个buff数组的大小，然后先除后模每个buff数组的最大空间，就找到在哪个buff数组的哪个位置，之后才能访问；

相较于list，支持了下标访问，CPU高速缓存效率高，但是中间插入的效率很低，如：1.可以考虑挪动数据，但是代价太大；2.扩容，对当前buff数组扩容，然后当前数组挪动数据，但是会使得[]的效率进一步下降，每个数组的大小就不是固定值了，所以库里面没有这样设计；