The STL queue template is found in <queue>. A simplified declaration of the queue template would look something like:

template<class T>
class queue
{
public:
    queue();
    bool empty() const;
    unsigned size() const;
    T& top();
    const T& top() const;
    void push(const T& x);
    void pop();
protected:
    deque<T> c;
};

In reality, the queue class is an adapter class that can be implemented by containers other than the deque container. In particular the list<> class is appropriate. The container, in turn, may use a custom allocator other than ::new(). The container must supply the following members where T0 is a suitable integral type such as unsigned or unsigned long:

    typedef T value_type;
    typedef T0 size_type;
    Cont(const allocator_type& al);
    bool empty() const;
    size_type size() const;
    allocator_type get_allocator() const;
    value_type& front();
    const value_type& front() const;
    value_type& back();
    const value_type& back() const;
    void push_back(const value_type& x);
    void pop_front();

The full declaration of a queue looks something like:

template<class T, class Cont = deque<T> >
class queue
{
public:
    typedef Cont::allocator_type allocator_type;
    typedef Cont::value_type value_type;
    typedef Cont::size_type size_type;
    explicit queue(const allocator_type& al = allocator_type()) const;
    bool empty() const;
    size_type size() const;
    allocator_type get_allocator() const;
    value_type& top();
    const value_type& top() const;
    void push(const value_type& x);
    void pop();
protected:
    Cont c;
};