栈的定义
成都创新互联公司是专业的九江网站建设公司，九江接单;提供成都网站建设、网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行九江网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作! 栈（Stack）又称堆栈，是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。
栈有两种实现的方式。一种是顺序存储，和数组类似；一种是链式存储，和单链表类似。
下面主要用顺序存储去实现它，和链式存储相比，主要有下面几个优点：
（1）方便我们进行管理；数组就是只可以在一边进行操作。
（2）应用顺序存储的效率比较高。假如用链式存储的话，在插入删除等操作时，需要遍历整个链表，比较浪费时间；还有一点是CPU的高速缓存的利用率低，每次操作往高级缓存中加载时会多加载一些没有用的空间，不仅浪费时间，还容易“污染”内存。
2.栈的主要的函数接口
void Push(const T & s);//插入数据
void Pop();//删除数据
bool empty();//判断是否为空
size_t size();//元素个数
T & Top();//取出最后进入的元素但不删除
void print();//输出函数
3.栈的定义
template //定义为模板类，实现不同的数据存储
class Stack
{
public:
Stack()//构造函数
:_ptr(NULL)
, _top(0)
,_capacity(0)
{
}
Stack(const Stack & s)//拷贝构造
{
_capacity = s._capacity;
_top = s._top;
_ptr = new T[_capacity];
for (size_t i = 0; i < _top; i++)//不能使用memcpy函数，（必须考虑浅拷贝的 //问题）
{
_ptr[i] = s._ptr[i];
}
}
Stack & operator=(const Stack & s)//赋值运算符的重载
{
if (_capacity < s._capacity)//判断容量是否足够
{
_capacity = s._capacity;
_ptr = new T[_capacity];
}
_top = s._top;
for (size_t i = 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.接口的实现
void Push(const T & s)//插入数据
{
_Check_capacity();//使用这个函数判断是否需要开辟空间
_ptr[_top] = s;
_top++;
}
void Pop()//删除数据
{
if (_top)//必须保证数据个数不能为负数
{
_top--;
}
}
bool empty()//判空
{
return _top==0;
}
size_t size()//数据个数
{
return _top;
}
T & Top()//输出最后插入的数据
{
if (!empty())
{
return _ptr[_top-1];
}
}
void print()//输出
{
for (size_t i = _top; i > 0; --i)
{
cout << _ptr[i-1] << " ";
}
cout << endl;
}5.测试结果
void testStack()
{
Stack s1;
s1.Push(0);
s1.Push(1);
s1.Push(2);
s1.Push(3);
s1.print();//输出结果3 2 1 0
s1.Pop();
s1.print();//输出结果2 1 0
cout << s1.empty() << endl;//输出结果0
cout << s1.size() << endl;//输出结果 3
cout << s1.Top() << endl;//输出结果 2
}
附件：http://down.51cto.com/data/2367581
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
文章名称：c++实现栈的基本操作-创新互联
分享链接：
http://cdxtjz.cn/article/doohdc.html
