C++ 如何实现顺序栈(使用模板类)
更新时间:2022年7月25日 17:02 点击:264 作者:ChanJose
一、思路
- 1.用数组存储栈中的元素;
- 2.用top保存栈顶的位置;
- 3.进栈:top加1,然后在数组中的top位置插入x;
- 4.出栈:top减1
二、遇到问题
1.父类中有函数为纯虚函数,定义子类对象时,出现:“ XXX is an abstract class”
原因:
(a)一定要确保父类所有的纯虚函数都要被实现,否则子类依然不能被实例化;
(b)一定要确保继承的函数和父类声明的虚函数的形参类型与返回值类型一致,否则父类的虚函数没有实例化;
父类:virtual void Push() 会出现 "xxx referenced from"应该是指没有定义
原因这个是虚函数,要在父类里面有定义才行;纯虚函数则不需要在父类中定义
2.重载函数出错:ostream& operator<<(ostream &out, SeqStack<T> &s)
因为:友元函数在其它文件使用和定义(声明和定义、定义和使用在两个不同的文件)要加前置说明
同时要加<T>:
三、实现程序
1.Stack.h:
#ifndef Stack_h #define Stack_h const int maxSize = 50; template <class T> class Stack { public: Stack(){}; // 构造函数 void Push(const T x); // 新元素进栈 bool Pop(); // 栈顶元素出栈 virtual bool getTop(T &x) const = 0; // 读取栈顶元素,由x返回 virtual bool isEmpty() const = 0; // 判断栈空否 virtual bool isFull() const = 0; // 判断栈满否 virtual int getSize() const = 0; // 计算栈中元素个数 }; #endif /* Stack_h */
2.SeqStack.h
#ifndef SeqStack_h #define SeqStack_h #include <iostream> #include "Stack.h" using namespace std; const int stackIncreament = 20; // 栈溢出时扩展空间的增量 //类的前置声明 template <typename T> class SeqStack; //友元函数的声明 template <typename T> ostream& operator<<(ostream &out, SeqStack<T> &s); template <class T> class SeqStack: public Stack<T> { // 顺序栈的类定义 public: SeqStack(int sz=50); // 构造函数,建立一个空栈 ~SeqStack(); // 析构函数 void Push(const T x); // 把x插入到栈顶,如果栈满,进行溢出处理 bool Pop(); // 如果栈为空,不进行出栈,否则把栈顶元素出栈 bool getTop(T &x) const; // 返回栈顶元素的值 bool isEmpty()const; // 判断栈是否为空 bool isFull()const; // 栈是否满 int getSize()const; // 返回栈中元素的个数 void makeEmpty(); // 清空栈的内容 friend ostream& operator<< <T>(ostream &out, SeqStack<T> &s); // 输出栈中元素的重载操作 private: T *elements; // 存放栈中元素的栈数组 int top; // 栈顶指针 int maxSize; // 栈最大可容纳的元素个数 void overflowProcess(); // 栈的溢出处理 }; template <class T> SeqStack<T>::SeqStack(int sz) { // 构造函数,建立一个空栈 top = -1; maxSize = sz; elements = new T[maxSize]; // 创建栈的数组空间 if(elements == NULL) { cerr << "内存空间分配失败!" << endl; exit(1); } } template <class T> SeqStack<T>::~SeqStack() { // 析构函数 delete []elements; } template <class T> void SeqStack<T>::overflowProcess() { // 栈的溢出处理 T *newArray = new T[maxSize + stackIncreament]; if(newArray == NULL) { cerr << "存储空间分配失败!" << endl; exit(1); } // 将elements数组中的值复制到新数组中 for(int i = 0; i <= top; i++) newArray[i] = elements[i]; maxSize = maxSize + stackIncreament; delete []elements; elements = newArray; // 复制数组 } template <class T> void SeqStack<T>::Push(const T x) { // 把x插入到栈顶,如果栈满,进行溢出处理 if(isFull() == true) // 栈满则溢出处理 overflowProcess(); elements[++top] = x; // top自增1,并存储x } template <class T> bool SeqStack<T>::Pop() { // 如果栈为空,不进行出栈,否则把栈顶元素出栈 if(isEmpty()) // 判断栈空否,若空则返回false return false; top--; // 栈顶减1,相当于把这个栈顶元素删掉 return true; } template <class T> bool SeqStack<T>::getTop(T &x)const { // 返回栈顶元素的值 if(isEmpty()) // 判断栈空否,若空则返回false return false; x = elements[top]; // 返回栈顶元素的值 return true; } template <class T> bool SeqStack<T>::isEmpty()const { // 判断栈是否为空 if(top == -1) return true; return false; } template <class T> bool SeqStack<T>::isFull()const { // 判断栈是否为空 if(top == maxSize-1) return true; return false; } template <class T> int SeqStack<T>::getSize()const { // 返回栈中元素的个数 return top+1; } template <class T> void SeqStack<T>::makeEmpty() { // 清空栈的内容 top = -1; // 将top赋值-1,相当于清空数组内容 } template <class T> ostream& operator<<(ostream &out, SeqStack<T> &s) { // 友元函数 // 输出栈中元素的重载操作 out << "top=" << s.top << endl; // 输出栈顶位置 for(int i = 0; i <= s.top; i++) // 逐个输出栈中元素的值 out << i << ":" << s.elements[i] << endl; return out; }
3.main.cpp
#include <iostream> #include "SeqStack.h" using namespace std; int main(int argc, const char * argv[]) { bool finished = false; int choice, n, val; // choice:选择 SeqStack<int> obj; while(!finished) { cout << "\n*********菜单*********\n"; cout << "1:建栈\n"; cout << "2:压栈\n"; cout << "3:出栈\n"; cout << "4:取栈顶元素的值\n"; cout << "5:栈是否为空\n"; cout << "6:栈是否满\n"; cout << "7:获取栈中元素的个数\n"; cout << "8:清空栈的内容\n"; cout << "9:输出栈中的所有元素\n"; cout << "10:退出\n"; cout << "请输入选择[1-10]:\n"; cin >> choice; switch(choice) { case 1: cout << "请输入要进栈的元素个数:"; cin >> n; cout << "请输入要进栈的元素值:" << endl; for(int i = 0; i < n; i++) { cin >> val; obj.Push(val); } break; case 2: cout << "请输入要进栈的元素值:" << endl; cin >> val; obj.Push(val); break; case 3: if(obj.Pop()) cout << "出栈成功!" << endl; else cout << "出栈失败!" << endl; break; case 4: if(obj.getTop(val)) cout << "栈顶元素为:" << val << endl; else cout << "栈为空!" << endl; break; case 5: if(obj.isEmpty()) cout << "栈为空!" << endl; else cout << "栈不为空!" << endl; break; case 6: if(obj.isFull()) cout << "栈满!" << endl; else cout << "栈不满!" << endl; break; case 7: int size; size = obj.getSize(); cout << "栈中的元素个数为:" << size << endl; break; case 8: obj.makeEmpty(); break; case 9: cout << obj << endl; // 重载输出<< break; case 10: finished = true; break; default: cout << "输入错误,请重新输入!" << endl; } // switch } // while return 0; }
以上为个人经验,希望能给大家一个参考,也希望大家多多支持猪先飞。
原文出处:https://blog.csdn.net/chuanzhouxiao/article/details/86032278
上一篇: C语言链表实现学生信息管理系统程序设计
下一篇: 一文详解C++中动态内存管理
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25