本文原创
stack 并不是一种 container,而是一种 container adaptor,借用 deque 的成员函数实现自身的操作:
template <class _Tp, class _Sequence = deque<_Tp> > class stack { friend bool operator==(const stack&, const stack&); friend bool operator<(const stack&, const stack&); 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: stack() : c() {} explicit stack(const _Sequence& __s) : c(__s) {} /* push, top, pop 都在 deque 尾端操作 */ bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference top() { return c.back(); } const_reference top() const { return c.back(); } void push(const value_type& __x) { c.push_back(__x); } void pop() { c.pop_back(); } }; template <class _Tp, class _Seq> bool operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) { return __x.c == __y.c; // 默认调用 deque 的 operator==() } template <class _Tp, class _Seq> bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) { return __x.c < __y.c; // 默认调用 deque 的 operator<() }
从 stack 调用 deque 的成员函数来看,vector 也支持这些操作,因此 stack 也可以藉由 vector 来实现,只需显式设置第二个模板参数即可。