Stack（栈）

stack是先进后出的数据结构，只能在栈顶(尾部)进行数据存取。换言之，stack不允许有遍历行为。把元素推入stack的操作称为push，把元素退出stack的操作称为pop。

如果以deque为底部结构并封闭其头端开口，便轻而易举地形成了一个stack。SGI STL便以deque作为缺省情况下的stack底部结构，stack的实现因而非常简单。stack以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为adapter(配接器)。STL stack往往不被归类为container，而被归类container adapter。

template<class T, class Sequence = deque<T>>
class stack{
    //__STL_NULL_TMPL_ARGS会展开为<>
    friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
    friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
    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:
    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(); }
    void pop() { c.pop_back(); }  
};

template<class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y){
    return x.c == y.c;
}
template<class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y){
    return x.c < y.c;
}

stack由于结构的特殊性，不提供迭代器。

也可以使用list作为stack的底层容器。