c++实现栈的基本操作-创新互联
栈的定义
成都创新互联公司是专业的九江网站建设公司,九江接单;提供成都网站建设、网站建设,网页设计,网站设计,建网站,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附件:http://down.51cto.com/data/2367581s1; 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 }
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
本文题目:c++实现栈的基本操作-创新互联
分享网址:http://scyanting.com/article/doohdc.html