前言

本期分享：STL中的栈和队列。
在数据结构初阶时，我们已经学习这来那个两种数据结构，如今来看STL中的，不过是更加标准化。而实现起来，会简单得超乎你想象！
文中不足错漏之处望请斧正！

stack & queue

STL中的栈和队列是容器适配器。容器适配器是对某种已有容器的再次封装。
比如栈的结构，需要尾部操作，可以对vector再次封装来得到栈；队列需要头尾操作，可以对list再次封装来得到队列。

stack

认识

后进先出的容器适配器。（用deque作为底层容器）

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

实现

STL中用到了一个新的数据结构deque作为stack的底层容器，我们下文会稍作了解。但我们这里直接用一下vector实现，助于了解学习即可。

template <class T, class Container = vector<T>>
class Stack
{
public:
    void Push(T val) { _con.push_back(val);}
    void Pop() { _con.pop_back();}
    T& Back() { return _con.back();}
    bool Empty() { return _con.empty();}
    size_t Size() { return _con.size();}
private:
    Container _con;
};

queue

认识

先进先出的容器适配器。（用deque作为底层容器）

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

实现

到这里，我们又发现deque的存在了，deque我不认识，但是我们可以推理：既然它可以同时用于栈和队列，那么他头尾操作效率一定不低。但是为什么要用deque？栈和队列可以用同一种容器来适配。

template <class T, class Container = list<T>>
class Queue
{
public:
    void Push(T val) { _con.push_back(val);}
    void Pop() { _con.pop_front();}
    T& Front() { return _con.front();}
    T& Back() { return _con.back();}
    bool Empty() { return _con.empty();}
    size_t Size() { return _con.size();}
private:
    Container _con;
};

没有迭代器？

他俩的出入规则不符合迭代器的用法。

deque

deque（Double-Ended Queue）是一种双端队列。

template < class T, class Alloc = allocator<T> > class deque;

接口

• push_back 和 push_front
• pop_back 和 pop_front
• insert 和 erase
• operator[]
• …

结构

deque的内部实现使用了一块分段连续的存储空间。有一个指针数组起到中央控制的作用，每个指针指向一段连续空间。

这样的结构便于在任意位置进行插入和删除操作，不需要移动被删除元素后面的所有元素。

由于空间连续，deque也能提高缓存命中率。

虽然deque支持随机访问，但因为deque 的元素不一定是连续的，对于大量随机访问的情况下，效率可能会比数组低。

优缺点

啥都能做，但啥都差点。

随机访问，中间插入和删除是痛点。

排序开销极大（结构劣势）。

适合做stack和queue的默认适配容器（没有中间操作）。

优先级队列

优先级高的先出的队列。底层其实是堆。

template <
	class T, 
	class Container = vector<T>,
  class Compare = less<typename Container::value_type> 
	> class priority_queue;

看到优先级，很容易让人想起堆。是的，默认容器为vector，也是因为堆的结构是完全二叉树，适合用vector存储。而Compare，用于比较的仿函数，决定了优先级如何确定。

实现

template<class T>
struct Less
{
    bool operator()(const T& e1, const T& e2) { return e1 < e2;}
};

template<class T>
struct Greater
{
    bool operator()(const T& e1, const T& e2) { return e1 > e2;}
};

//默认大堆
template <class T, class Container = vector<T>, class Compare = Less<T>>
class PriorityQueue
{
public:
    PriorityQueue() {}
    
    void Push(T val)
    {
        _con.push_back(val);
        AdjustUp(_con.size()-1);
    }
    
    void Pop()
    {
        _con[0] = _con.back();
        _con.pop_back();
        AdjustDown(0);
    }
    
    T Top() { return _con[0];}
    bool Empty() { return _con.empty();}
    size_t Size() { return _con.size();}
    
private:
    void AdjustUp(int child)
    {
        int parent = (child - 1) / 2;
        while(child > 0)
        {
            if(Compare()(_con[parent], _con[child]))
            {
                swap(_con[parent], _con[child]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else break;
        }
    }
    
    void AdjustDown(int parent)
    {
        int child = parent * 2 + 1;
        while(child < _con.size())
        {
            if(child+1 < _con.size() && Compare()(_con[child], _con[child+1])) ++child;
            
            if(Compare()(_con[parent], _con[child]))
            {

                swap(_con[parent], _con[child]);
                parent = child;
                child = parent * 2 + 1;
            }
            else break;
        }
    }
private:
    Container _con;
};

今天的分享就到这里了，感谢您能看到这里。

这里是培根的blog，期待与你共同进步！