本文原创
queue 同 stack 一样,也是基于 deque 实现的 container adaptor,只不过 stack 是 LIFO 结构,queue 是 FIFO 结构:
template <class _Tp, class _Sequence = deque<_Tp> > class queue { friend bool operator==(const queue&, const queue&); friend bool operator<(const queue&, const queue&); public: typedef typename _Sequence::value_type value_type; typedef typename _Sequence::size_type size_type; typedef _Sequence container_type; typedef typename _Sequence::reference reference; typedef typename _Sequence::const_reference const_reference; protected: _Sequence c; public: queue() : c() {} explicit queue(const _Sequence& __c) : c(__c) {} /* 与 deque 相比,禁止 push_front() 和 pop_back() */ 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(); } }; template <class _Tp, class _Sequence> bool operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) { return __x.c == __y.c; // 调用 deque 的 operator==() } template <class _Tp, class _Sequence> bool operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) { return __x.c < __y.c; // 调用 deque 的 operator<() }
queue 无法使用 vector 来实现,因为 vector 不支持 pop_front() 操作。