C++stack、queue

stack和queue就是我们熟知的栈和队列，同样是stl的一部分，但是不同于其他数据结构，他们两个没有迭代器。

相比于其他stl中的容器，stack/queue的接口少了很多，因为stack/queue本质上其实是通过容器适配器适配出来的（后面的文章中会讲到容器适配器）

1.stack

empty:判断栈是否为空

size:获取栈中有效数据的数量

top:获取栈顶元素

push:入栈

pop:出栈

swap:交换两个栈

    stack<int> st0;
    st0.push(1);
    st0.push(3);
    st0.push(5);
    st0.push(7);
    while (!st0.empty())
    {
        cout << st0.top() << " ";
        st0.pop();
    }
    cout << "\n";

2.queue

empty:判断链表是否为空

size:获取链表中有效数据的数量

front:获取队列头节点

back:获取队列尾节点

push:入队列

pop:出队列

swap:交换两个队列

    queue<int> q0;
    q0.push(1);
    q0.push(2);
    q0.push(3);
    q0.push(4);
    q0.push(5);
    while (!q0.empty())
    {
        cout << q0.front() << " ";
        q0.pop();
    }
    cout << "\n";

3.priority_queue

priority_queue直译过来是“优先级队列”的意思，底层也是通过适配器加上堆的操作适配出来的，可以把priority_queue看作是堆一样的数据结构，不过默认是大堆（默认大的元素优先级高）

empty:判断堆是否为空

size:获取堆中有效数据数量

top:获取堆顶元素

push:向priority_queue中插入一个元素

pop:删除堆顶元素

swap:交换两个堆

priority_queue<int> heap0;//默认是大堆
heap0.push(5);
heap0.push(1);
heap0.push(9);
heap0.push(3);
heap0.push(8);
heap0.push(4);
while (!heap0.empty())
{
    cout << heap0.top() << " ";
    heap0.pop();
}
cout << "\n";
priority_queue<int,vector<int>,greater<int>> heap1;//通过提供自定义比较函数greater构建小堆
heap1.push(5);
heap1.push(1);
heap1.push(9);
heap1.push(3);
heap1.push(8);
heap1.push(4);
while (!heap1.empty())
{
    cout << heap1.top() << " ";
    heap1.pop();
}
cout << "\n";

4.deque

deque是双端队列，综合了vector和Listening的优点，为什么这么说呢。
先来看vector，vector在插入数据的时候（除了在尾部比较方便），需要将后面的数据挪动，若果是在头部插入数据，那么后面的所有数据都需要往后挪，消耗很大，但是vector的优点是支持[i],也就是下标访问，以至于vector的随机访问非常方便（消耗也少）
我们再来看list，list不同于vector，vector是连续的空间，list是通过一个一个的节点连接起来的，这样的结构不管是在头部还是尾部插入数据都非常方便，只需要控制指针将节点连接起来即可，但是缺点在于访问非常的麻烦，需要遍历一遍才能找到想要的节点，这样就会有过大的消耗
综合了vector和list的优点和缺点，deque双端队列就诞生了
deque的底层结构是下面这样的：

 数据是存放在缓冲区中，map是一个指针数组，存放指向缓冲区的指针，在插入的时候，若果缓冲区满了或者要在头部/尾部插入数据，只需要开辟新的缓冲区，然后往map中存放新缓冲区的指针即可。

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩
容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其
是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实
际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看
到的一个应用就是，STL用其作为stack和queue的底层数据结构。