C++使用模板类实现链式栈

2023-07-26 14:22:06 73

本文实例为大家分享了C++使用模板类实现链式栈的具体代码，供大家参考，具体内容如下

一、实现程序：

1.Stack.h

#ifndefStack_h
#defineStack_h

template
classStack{
public:
Stack(){};//构造函数
voidPush(constTx);//新元素进栈
boolPop();//栈顶元素出栈
virtualboolgetTop(T&x)const=0;//读取栈顶元素，由x返回
virtualboolisEmpty()const=0;//判断栈空否
//virtualboolisFull()const=0;//判断栈满否,因为链式栈不存在不满的情况
virtualintgetSize()const=0;//计算栈中元素个数
};


#endif/*Stack_h*/

2.LinkedStack.h

#ifndefLinkedStack_h
#defineLinkedStack_h
#include
#include"Stack.h"
usingnamespacestd;

template
structLinkNode{
Tdata;
LinkNode*link;
};

//类的前置声明
template
classLinkedStack;

//友元函数的声明
template
ostream&operator<<(ostream&out,LinkedStack&s);
template
classLinkedStack:publicStack{
public:
LinkedStack();//构造函数
~LinkedStack();//析构函数
voidPush(constTx);//进栈
boolPop();//出栈
boolgetTop(T&x)const;//读取栈顶元素
boolisEmpty()const;//判断栈是否为空
intgetSize()const;//求栈的元素个数
voidmakeEmpty();//清空栈的内容
friendostream&operator<<(ostream&out,LinkedStack&s);//重载输出函数
private:
LinkNode*top;//栈顶指针，即链头指针
};
template
LinkedStack::LinkedStack(){
//构造函数，置空栈
top=newLinkNode();//引入头指针：不存放数据
top->link=NULL;
}
template
LinkedStack::~LinkedStack(){
//析构函数,释放内存空间
makeEmpty();
}
template
voidLinkedStack::Push(constTx){
//进栈：将元素值x插入到链式栈的栈顶，即链头
LinkNode*newNode=newLinkNode();//创建包含x的新结点
if(newNode==NULL){
cerr<<"内存空间分配失败！"<data=x;
newNode->link=top->link;//指向头指针的下一个结点：即栈中第一个存放有效数据的结点
top->link=newNode;//头指针往前移
}
template
boolLinkedStack::Pop(){
//出栈：删除栈顶结点
if(isEmpty())
returnfalse;//栈空，不出栈
LinkNode*p=top->link;//暂存栈顶元素
top->link=p->link;//栈顶指针退到新的栈顶位置
deletep;
p=NULL;
returntrue;
}

template
boolLinkedStack::getTop(T&x)const{
//读取栈顶元素
if(isEmpty())
returnfalse;
x=top->link->data;//栈不空，返回栈顶元素的值。这里top为头指针，所以栈顶元素为：top->link
returntrue;
}

template
boolLinkedStack::isEmpty()const{
//判断栈是否为空
if(top->link==NULL)//栈为空
returntrue;
returnfalse;
}

template
intLinkedStack::getSize()const{
//求栈的元素个数
intlen=0;

LinkNode*current=top->link;
while(current!=NULL){
len++;
current=current->link;
}
returnlen;
}

template
voidLinkedStack::makeEmpty(){
//清空栈的内容
LinkNode*current=top->link;
while(current!=NULL){
top->link=current->link;//保存链式栈准备要删除的结点的下一个结点，防止丢失
deletecurrent;//释放
current=NULL;//先指向空
current=top->link;//再指向剩下链表的首结点
}
}

template
ostream&operator<<(ostream&out,LinkedStack&s){
//重载输出函数
LinkNode*current=s.top->link;
while(current!=NULL){
out<data<<"";
current=current->link;
}
returnout;
}
#endif/*LinkedStack_h*/

3.main.cpp

#include"LinkedStack.h"
usingnamespacestd;

intmain(intargc,constchar*argv[]){
intn,x,choice,len;//val存储值，choose存储用户的选择
boolfinished=false;
LinkedStackL;//对象

while(!finished){
cout<<"1:建栈："<>choice;
switch(choice){
case1:
cout<<"请输入要进栈的数的个数:";
cin>>n;
cout<<"请输入要进栈的数(以空格隔开)："<>x;
L.Push(x);
}
break;
case2:
cout<<"请输入要进栈的数:";
cin>>x;
L.Push(x);
break;
case3:
if(L.Pop())
cout<<"出栈成功!"<
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C++使用模板类实现链式栈

热门推荐

随机推荐