STL源码：queue

蔚落 2022-08-07 08:40 182阅读 0赞

queue是先进先出（FIFO）的数据结构，有两个口：允许从尾部加入元素、取得头部的元素。**没有其他任何方法可以存取queue的其它元素，即queue不允许遍历行为**。

**SGI STL以deque作为缺省情况下的queue底部结构**，queue的实现很简单，代码十分简短。

queue没有迭代器。

**为什么STL queue称为容器适配器而不是容器？**

答：由于queue以底部容器完成其所有工作，而具有**这种“修改某物接口，形成另外一种风貌”的性质，称为**adapter（配置器），因此STL queue往往不归为容器，被视为容器适配器。

# STL queue源码 #

// 如果编译器不能根据前面模板参数推导出后面使用的默认参数类型,
    	// 那么就需要手工指定, 本实作queue内部容器默认使用deque
    	// 由于queue要求在队尾追加元素, 在队头获取和移除元素
    	// 所以非常适合使用deque
    #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
    	template <class T, class Sequence = deque<T> >
    #else
    	template <class T, class Sequence>
    #endif
    class queue
    {
    	// 讲解见<stl_pair.h>中的运算符剖析
    	friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
    	friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
    
    public:
    	// 由于queue仅支持对队头和队尾的操作, 所以不定义STL要求的
    	// pointer, iterator, difference_type
    	typedef typename Sequence::value_type value_type;
    	typedef typename Sequence::size_type size_type;
    	typedef typename Sequence::reference reference;
    	typedef typename Sequence::const_reference const_reference;
    
    protected:
    	Sequence c;   // 这个是我们实际维护的容器,底层容器
    
    public:
    
    	// 这些是STL queue的标准接口, 都调用容器的成员函数进行实现
    	// 其接口和stack实现很接近, 参考<stl_stack.h>
        //以下完全利用Sequence c的操作完成queue的操作
    	bool empty() const { return c.empty(); }
    	size_type size() const { return c.size(); }
    	reference front() { return c.front(); }
    	const_reference front() const { return c.front(); }
    	reference back() { return c.back(); }
    	const_reference back() const { return c.back(); }
    	void push(const value_type& x) { c.push_back(x); }
    	void pop() { c.pop_front(); }
    };
    
    // 详细讲解见<stl_pair.h>
    template <class T, class Sequence>
    bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y)
    {
    	return x.c == y.c;
    }
    
    template <class T, class Sequence>
    bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y)
    {
    	return x.c < y.c;
    }

# list实现的queue #

list也和deque一样，是双向开口的数据结构，list也可以作为底部结构并封闭其开口，形成一个queue。

代码如下：

#include <queue>
    #include <list>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main() {
    	queue<int, list<int> > iqueue;
    	iqueue.push(1);
    	iqueue.push(3);
    	iqueue.push(6);
    
    	cout << iqueue.size() << endl;
    	cout << iqueue.front() << endl;
    
    	iqueue.pop(); cout << iqueue.front() << endl;
    	cout << iqueue.size() << endl;
    }