STL-queue

简介

queue 直译为队列，队列为一种先进先出的数据结构（First In First Out，FIFO），queue有一个入口和一个出口，它只允许在尾端压入数据并在首端弹出数据

queue是容器适配器，无迭代器，不允许随机访问

类模板

template<
    class T,               //数据类型
	class Container = deque<T>  //底层容器
> class queue

成员函数

以下时间复杂度是以 deque 作为 Container时的

容量相关

1. size() - 返回 queue 中元素数 O(1)
2. empty() - 当前 queue 是否为空 O(1)

元素访问相关

1. front() - 访问队首元素 O(1)
2. back() - 访问队尾元素 O(1)

修改器相关

1. push() -压入元素到队首 O(1)
2. pop() - 弹出对尾元素 O(1)
3. swap() - 交换元素 (C++11)
4. emplace() - 压入元素到 queue 队尾 ，调用构造函数，并对底层容器排序 (C++11)

deque实现queue

template <class T,
	class Container = deque<T> 
> class queue
	{
	void push(const T& e)
	{
	    c.push_front(e);
	}
	void pop()
	{
	    c.pop_back();
	}
	T& front()
	{
	    return c.front();
	}
	T& back()
	{
	    return c.back();
	}
	size_t size() const
	{
	    return c.size();
	}
	bool empty() const
	{
	    return c.empty();
	}
	void emplace(const T&& e)   //c++11
	{
	    c.emplace_back(forward<T>(e));
	}
    protected:
	    Container c;
	}