stack源码

stack概述

stack是一种先进后出的数据结构，它只有一个出口，允许新增元素、移除元素、取得最顶端元素，但每次只能处理顶端元素，也就是说，stack不允许遍历行为。

stack定义

以某种既有容器作为底部结构，将其接口改变，使之符合"先进后出"的特性，形成一个stack，是很容易做到的，deque是双向开口的数据结构，若以deque以底部结构并封闭其开头，便轻易举起形成一个stack。

由于stack系以底部容器完成其所有工作，而具有这种性质，称为adapter(配接器)，因此，STL stack往往不被归类为container(容器)，而被归类为container adapter。

template <class T,class Sequence=deque<T> >
class stack{
    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:
    //以下完全利用Sequence c的操作，完成stack的操作
    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();}
    //deque是两头可进出，stack是末端进，末端出
    void push(const value_type&x){c.push_back(x);}
    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没有迭代器

stack只能处理其顶端元素，不能随机访问，所以不提供迭代器。

以list作为stack的底层容器

除了deque之外，list也是双向开口的数据结构。上述stack源码中使用的底层容器的函数有empty、size、back、push_back、pop_back，list也都具备，因此，若以list为底部结构并封闭其头端开口，一样能够形成一个stack，示范如下：

#include<iostream>
#include<stack>
#include<list>
#include<algorithm>
using namespace std;

int main(){
    stack<int,list<int> > istack;
    istack.push(1);
    istack.push(3);
    istack.push(5);
    istack.push(7);

    cout<<istack.size()<<endl; //4
    cout<<istack.top()<<endl; //7

    istack.pop();cout<<istack.top()<<endl; //5
    istack.pop();cout<<istack.top()<<endl; //3
    istack.pop();cout<<istack.top()<<endl; //1

    cout<<istack.size()<<endl; //1
    return 0;
}