栈的定义

栈（Stack）又称堆栈，是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。

栈有两种实现的方式。一种是顺序存储，和数组类似；一种是链式存储，和单链表类似。

下面主要用顺序存储去实现它，和链式存储相比，主要有下面几个优点：

（1）方便我们进行管理；数组就是只可以在一边进行操作。

（2）应用顺序存储的效率比较高。假如用链式存储的话，在插入删除等操作时，需要遍历整个链表，比较浪费时间；还有一点是CPU的高速缓存的利用率低，每次操作往高级缓存中加载时会多加载一些没有用的空间，不仅浪费时间，还容易“污染”内存。

2.栈的主要的函数接口

voidPush(constT&s);//插入数据voidPop();//删除数据boolempty();//判断是否为空size_tsize();//元素个数T&Top();//取出最后进入的元素但不删除voidprint();//输出函数

3.栈的定义

template<typenameT>//定义为模板类，实现不同的数据存储classStack{public:Stack()//构造函数:_ptr(NULL),_top(0),_capacity(0){}Stack(constStack<T>&s)//拷贝构造{_capacity=s._capacity;_top=s._top;_ptr=newT[_capacity];for(size_ti=0;i<_top;i++)//不能使用memcpy函数，（必须考虑浅拷贝的//问题）{_ptr[i]=s._ptr[i];}}Stack<T>&operator=(constStack<T>&s)//赋值运算符的重载{if(_capacity<s._capacity)//判断容量是否足够{_capacity=s._capacity;_ptr=newT[_capacity];}_top=s._top;for(size_ti=0;i<_top;i++){_ptr[i]=s._ptr[i];}return*this;}~Stack()//析构函数{if(_ptr){delete_ptr;}}protected:T*_ptr;//保存数据的指针size_t_top;//存储的数据个数size_t_capacity;//开辟的容量｝

4.接口的实现

voidPush(constT&s)//插入数据{_Check_capacity();//使用这个函数判断是否需要开辟空间_ptr[_top]=s;_top++;}voidPop()//删除数据{if(_top)//必须保证数据个数不能为负数{_top--;}}boolempty()//判空{return_top==0;}size_tsize()//数据个数{return_top;}T&Top()//输出最后插入的数据{if(!empty()){return_ptr[_top-1];}}voidprint()//输出{for(size_ti=_top;i>0;--i){cout<<_ptr[i-1]<<"";}cout<<endl;}

5.测试结果

voidtestStack(){Stack<int>s1;s1.Push(0);s1.Push(1);s1.Push(2);s1.Push(3);s1.print();//输出结果3210s1.Pop();s1.print();//输出结果210cout<<s1.empty()<<endl;//输出结果0cout<<s1.size()<<endl;//输出结果3cout<<s1.Top()<<endl;//输出结果2}

附件：http://down.51cto.com/data/2367581