STL源码剖析（十一）序列式容器之stack、queue、priority_queue

STL实现了stack和queue还有priority_queue ，stack是栈，queue是队列，priority_queue 是优先级队列

从使用上来说，它们属于容器。从实现上来说，它们属于容器适配器，为什么这么说呢？因为stack和queue还有priority_queue它们都是借助于其他容器实现的

一、stack

1.1 stack的数据结构

我们知道，栈是一种先进先出的数据结构，下面看一下stack的定义

template <class T, class Sequence = deque<T> >
class stack {...
protected:Sequence c;...
};

它内部定义了一个序列式容器，从类的模板参数来看，默认使用的是deque

stack是没有迭代器的，因为它只支持固定的顺序访问，所以不支持迭代器随机访问

1.2 stack的操作

入栈

void push(const value_type& x) { c.push_back(x); }

push是将元素入栈，从实现上看，它是将数据添加到容器的尾部

出栈

reference top() { return c.back(); }

top访问栈顶的元素，从实现上看，它是访问容器最后一个元素

void pop() { c.pop_back(); }

pop是将栈顶数据删除，从实现上看，它是删除容器的最后一个元素

从上面看，只要支持push_back、back、pop_back等方法的容器，就可以作为stack的内部容器，因此我们前面学过的vector、list都行，可以使用下面方法指定

stack<int, vector<int>>
stack<int, list<int>>

二、queue

2.1 queue的数据结构

队列是一种先进先出的数据结构，其定义如下

template <class T, class Sequence = deque<T> >
class queue {...
protected:Sequence c;...
};

它内部定义了一个序列式容器，从类的模板参数来看，默认使用的是deque

queue是没有迭代器的，因为它只支持固定的顺序访问，所以不支持迭代器随机访问

2.2 queue的操作

入队列

void push(const value_type& x) { c.push_back(x); }

push是将数据入队列，从实现上，它是将数据添加到容器的尾部

出队列

reference front() { return c.front(); }

front是访问队列的第一个元素，从实现上，它是访问容器的第一个元素

void pop() { c.pop_front(); }

pop是删除队列首元素，从实现上，它是删除容器的第一个元素

从上面看，queue内部的容器需要实现push_back、pop_front的操作的双向开口的容器，所以list也可以作为queue内部容器，可以如下定义

queue<int, list<int>>

三、priority_queue

priority_queue是优先级队列，优先级队列是一种特殊的队列，它不是按时间顺序的先进先出，而是给每个元素一个优先级，然后按照其优先级来决定出队列的顺序

优先级队列的底部一般是使用堆实现，堆是一种基于顺序存储的完全二叉树，又分大根堆和小根堆

这里对堆的算法不详细说明，主要介绍STL中是通过什么方式实现优先级队列的

3.1 priority_queue的数据结构

template <class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type> >
class  priority_queue {...
protected:Sequence c;Compare comp;      ...
};

可以看到priority_queue中定义的两个成员，一个是c，一个是comp

c是一个序列式容器，上面说过，优先级队列常基于堆实现，堆是一种基于顺序存储的完全二叉树，所以这个容器必须是顺序存储的容器（可以随机访问），从模板参数来看，默认使用的是vector

comp是比较优先级，上面说，优先级队列中的每个元素都有一个优先级，那这个优先级是怎么体现的呢？就是通过comp进行比较，comp是一个仿函数，这里默认使用的是less，其定义如下

template <class T>
struct less : public binary_function<T, T, bool> {bool operator()(const T& x, const T& y) const { return x < y; }
};

至于仿函数是什么，它是一种行为类似于函数的对象，总实现上，它通过重载operator()操作符来实现

priority_queue只支持固定的顺序访问，所以它也没有迭代器

3.2 priority_queue的操作

构造函数

priority_queue(InputIterator first, InputIterator last) : c(first, last) { make_heap(c.begin(), c.end(), comp); }

首先填充内部容器c，然后通过make_heap算法来构造一个堆，make_heap是STL实现的一个算法，它的作用是构建一个堆，这里不展开讨论

入队列

void push(const value_type& x) {c.push_back(x);push_heap(c.begin(), c.end(), comp); //上溯算法
}

首先将元素添加到容器的尾部，然后调用push_heap对堆进行重新排序，push_heap是STL实现的一个算法，它的作用是将最后一个元素放置到堆中恰当的置位

出队列

const_reference top() const { return c.front(); }

top是访问队列首元素，从实现上，它是访问容器的第一个元素

void pop() {pop_heap(c.begin(), c.end(), comp); //下放算法c.pop_back();
}

pop是将队列首元素删除，从实现上，它首先将通过pop_heap删除堆中首元素，然后再将容器最后一个元素删除。pop_heap是STL实现的一个算法，它的作用是将堆的第一个元素放置到顺序存储空间的最后