[数据结构]栈之顺序栈的类模板实现

2024-09-08 08:08

本文主要是介绍[数据结构]栈之顺序栈的类模板实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

栈的数组实现形式,采用动态分配数组,不够时可以调整栈的大小。

Stack.h文件:主要定义栈的抽象基类,提供公共的接口函数。


#ifndef STACK
#define STACK
//栈的抽象基类template<class T>
class Stack
{
public:Stack(){}~Stack(){}virtual void Push(const T& x)=0;virtual bool Pop(T& x)=0;virtual bool getTop(T& x)const=0;virtual bool IsEmpty()const=0;virtual bool IsFull()const=0;virtual int getSize()const=0;
};#endif

下面顺序栈的继承类:


/
#include"Stack.h"
#include <iostream>
#include <cstdlib>
#include <cassert>
using namespace std;const int stackIncreament=20;
template<class T>
class SeqStack:public Stack<T>
{
public:SeqStack(const int sz=50):top(-1),maxSize(sz),elements(new T[sz]){assert(elements!=NULL);}SeqStack(const SeqStack<T>& rhs);SeqStack<T>& operator=(const SeqStack<T>& rhs);~SeqStack(){delete []elements;}void Push(const T& x);bool Pop(T& x);bool getTop(T& x)const;bool IsEmpty()const{return (top==-1)?true:false;}//要覆盖,基类和继承类的const性质也要一样。函数的形式要形式要完全一样才能同名覆盖。bool IsFull()const{return (top==maxSize-1)?true:false;}int getSize()const{return top+1;}void MakeEmpty(){top=-1;}friend ostream& operator<< <T>(ostream& out,const SeqStack<T> &rhs);//加了一个<Type>才是正确的,不加会报错。类模板引起的一些问题private:void overflowProcess();
private:T *elements;int top;int maxSize;
};template<class T>
void SeqStack<T>::overflowProcess()
{T *ptr=new T[maxSize+stackIncreament];if(ptr==NULL){cerr<<"err"<<endl;exit(1);}for(int i=0;i<=top;++i)ptr[i]=elements[i];delete []elements;elements=ptr;maxSize=maxSize+stackIncreament;
}template<class T>
void SeqStack<T>::Push(const T& x)
{if(IsFull())overflowProcess();elements[++top]=x;
}template<class T>
bool SeqStack<T>::Pop(T& x)
{if(IsEmpty()) return false;x=elements[top--];return true;
}template<class T>
bool SeqStack<T>::getTop(T& x)const
{if(IsEmpty()) return false;x=elements[top];return true;
}template<class T>
ostream& operator<<(ostream& out,const SeqStack<T> &rhs)
{out<<"top= "<<rhs.top<<endl;for(int i=0;i<=rhs.top;++i)out<<"elements: "<<rhs.elements[i]<<" ";out<<endl;return out;
}template<class T>
SeqStack<T>::SeqStack(const SeqStack<T>& rhs)
{T *ptr=new T[rhs.maxSize];if(ptr==NULL){cerr<<"err"<<endl;exit(1);}for(int i=0;i<=rhs.top;++i)ptr[i]=rhs.elements[i];elements=ptr;maxSize=rhs.maxSize;top=rhs.top;
}template<class T>
SeqStack<T>& SeqStack<T>::operator=(const SeqStack<T>& rhs)
{T *ptr=new T[rhs.maxSize];if(ptr==NULL){cerr<<"err"<<endl;exit(1);}for(int i=0;i<=rhs.top;++i)ptr[i]=rhs.elements[i];elements=ptr;maxSize=rhs.maxSize;top=rhs.top;return *this;
}


下面是测试函数:


int main(int argc, char* argv[])
{SeqStack<int> s(5);int a=1;int b=2;int c=3;int d=4;int e=5;s.Push(a);s.Push(b);s.Push(c);s.Push(d);s.Push(e);cout<<s;cout<<"getSize(): "<<s.getSize()<<endl;cout<<"IsEmpty(): "<<s.IsEmpty()<<endl;cout<<"IsFull(): "<<s.IsFull()<<endl;int t;s.Pop(t);s.Pop(t);cout<<s;s.getTop(t);cout<<"getTop() "<<t<<endl;s.Push(a);s.Push(b);s.Push(c);s.Push(d);s.Push(e);cout<<s;s.MakeEmpty();cout<<s;s.Push(e);s.Push(e);cout<<s;SeqStack<int> s1(s),s2;cout<<s1;s2=s;cout<<s2;system("pause");return 0;
}

下面是测试结果:


top= 4
elements: 1 elements: 2 elements: 3 elements: 4 elements: 5
getSize(): 5
IsEmpty(): 0
IsFull(): 1
top= 2
elements: 1 elements: 2 elements: 3
getTop() 3
top= 7
elements: 1 elements: 2 elements: 3 elements: 1 elements: 2 elements: 3 elements
: 4 elements: 5
top= -1


top= 1
elements: 5 elements: 5
top= 1
elements: 5 elements: 5
top= 1
elements: 5 elements: 5
请按任意键继续. . .


注意事项:

1.在集成类同名覆盖基类的纯虚函数或者同名函数时,函数形式要完全一样。返回值要一样,const性也要一样,否则视为不同的函数,为函数的重载

2.类模板中的友元函数声明比较特殊,要多加一点类型。如下:

在里面声明友元函数时
ostream& operator<< <Type>(ostream& output,CirQueue<Type>& cq);//多加一个<Type>

否则会报错,在函数的定义时就不要加了。

3.容易敲错单词,键盘要熟练。写程序时,头脑一定要保持清晰,否则不要继续,不然调试很麻烦。











这篇关于[数据结构]栈之顺序栈的类模板实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1147577

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n