STL容器适配器之stack与queue

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

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

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

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

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

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

一、stack与queue的简单使用

template  > class stack;
template  > class queue;
1
2

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

1.stack的使用

stack 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;
1
2
3
4
5
6
7
8
9
10
11
12
13

2.queue的使用

queue 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;
1
2
3
4
5
6
7
8
9
10
11
12
13

二、模拟实现stack与queue

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

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

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

1.stack

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

    private:
        Container con_;
    };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.queue

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

    private:
        Container con_;
    };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

三、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 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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数组扩容，然后当前数组挪动数据，但是会使得[]的效率进一步下降，每个数组的大小就不是固定值了，所以库里面没有这样设计；

4.deque的使用场景

​ 1.用来适配stack和queue的默认容器；

​ deque高频的头插头删和尾插尾删效率不错，而vector有扩容和头插头删效率问题，list一个一个的申请空间缓存利用率不高。