[数据结构]栈之链式栈的类模板实现

2024-09-08 08:08

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

栈的抽象基类的实现:(不用抽象基类也是可以的,为了使用虚函数方便)


#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;template<class T>  
struct LinkNode //链表节点类  
{  T data;  LinkNode<T>* link;  LinkNode(LinkNode<T>* ptr=NULL):link(ptr){}  LinkNode(const T& item,LinkNode<T>* ptr=NULL):data(item),link(ptr){}  
};template<class T>
class LinkedStack:public Stack<T>
{
public:LinkedStack():top(NULL){}LinkedStack(const LinkedStack<T>& rhs);LinkedStack<T>& operator=(const LinkedStack<T>& rhs);~LinkedStack(){makeEmpty();}void Push(const T& x);bool Pop(T& x);bool getTop(T& x)const;bool IsEmpty()const{return top==NULL?true:false;}bool IsFull()const{return false;}//无意义,不可能满int getSize()const;void makeEmpty();friend ostream& operator<< <T>(ostream& out,LinkedStack<T>& rhs);//加<T>private:LinkNode<T>* top;
};template<class T>
void LinkedStack<T>::makeEmpty()
{LinkNode<T>* p=NULL;while(top!=NULL){p=top;top=top->link;delete p;}
}template<class T>
void LinkedStack<T>::Push(const T& x)
{top=new LinkNode<T>(x,top);assert(top!=NULL);
}template<class T>
bool LinkedStack<T>::Pop(T& x)
{if(IsEmpty()) return false;LinkNode<T>* p=top;top=top->link;x=p->data;delete p;return true;
}template<class T>
bool LinkedStack<T>::getTop(T& x)const
{if(IsEmpty()) return false;x=top->data;return true;
}template<class T>
int LinkedStack<T>::getSize()const
{int k=0;LinkNode<T>* p=top;while(p!=NULL){++k;p=p->link;}return k;
}template<class T>
ostream& operator<<(ostream& out,LinkedStack<T>& rhs)//不加<T>
{out<<"elements nums: "<<rhs.getSize()<<endl;LinkNode<T>* p=rhs.top;out<<"elements is: ";while(p!=NULL){out<<p->data<<" ";p=p->link;}out<<endl;return out;
}template<class T>
LinkedStack<T>::LinkedStack(const LinkedStack<T>& rhs)
{LinkNode<T>* src=rhs.top;LinkNode<T>* dest=NULL;LinkNode<T>* newNode=NULL;while(src!=NULL){newNode=new LinkNode<T>(src->data);if(dest==NULL){dest=newNode;top=dest;}else{dest->link=newNode;dest=newNode;}src=src->link;}
}template<class T>
LinkedStack<T>& LinkedStack<T>::operator=(const LinkedStack<T>& rhs)//copy赋值本质为:析构+copy构造函数
{if(top!=NULL)//先析构,释放资源makeEmpty();LinkNode<T>* src=rhs.top;//copy构造LinkNode<T>* dest=NULL;LinkNode<T>* newNode=NULL;while(src!=NULL){newNode=new LinkNode<T>(src->data);if(dest==NULL){dest=newNode;top=dest;}else{dest->link=newNode;dest=newNode;}src=src->link;}return *this;
}

类的测试代码如下:

int main(int argc, char* argv[])
{LinkedStack<int> s;int a=1,b=2,c=3,d=4,e=5;s.Push(a);s.Push(b);s.Push(c);s.Push(d);s.Push(e);cout<<s;s.Pop(e);cout<<s;cout<<std::boolalpha;//控制显式的bool值的显式cout<<"IsEmpty(): "<<s.IsEmpty()<<endl;cout<<"IsFull(): "<<s.IsFull()<<endl;cout<<std::noboolalpha;s.getTop(e);cout<<"getTop(): "<<e<<endl;s.makeEmpty();cout<<s;s.Push(a);s.Push(b);s.Push(c);cout<<s;LinkedStack<int> s1(s),s2;cout<<s1;s2=s1;cout<<s2;system("pause");return 0;
}

测试结果如下:


elements nums: 5
elements is: 5 4 3 2 1
elements nums: 4
elements is: 4 3 2 1
IsEmpty(): false
IsFull(): false
getTop(): 4
elements nums: 0
elements is:
elements nums: 3
elements is: 3 2 1
elements nums: 3
elements is: 3 2 1
elements nums: 3
elements is: 3 2 1
请按任意键继续. . .

注意事项:

1.在模板类的友元函数的实现与声明时:声明的时间要加额外的参数<T>,在实现的时间时不加的。

2. 实现中采用的是无附加头结点的单链表,所以要注意拷贝时,链表要区分是否是空链表或者是第一次建立链表的情况。

3.链式栈的栈顶在链表的头部,新节点的插入和删除都是在栈顶进行的,是对栈顶元素的操作。

4.链表实现的栈是不可能满的,所以总是返回false

5.采用cout<<std::boolaapha与cout<<std::noboolaapha可显式的控制布尔值的显式方式。







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



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

相关文章

使用Python实现一个优雅的异步定时器

《使用Python实现一个优雅的异步定时器》在Python中实现定时器功能是一个常见需求,尤其是在需要周期性执行任务的场景下,本文给大家介绍了基于asyncio和threading模块,可扩展的异步定... 目录需求背景代码1. 单例事件循环的实现2. 事件循环的运行与关闭3. 定时器核心逻辑4. 启动与停

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python实现word文档内容智能提取以及合成

《Python实现word文档内容智能提取以及合成》这篇文章主要为大家详细介绍了如何使用Python实现从10个左右的docx文档中抽取内容,再调整语言风格后生成新的文档,感兴趣的小伙伴可以了解一下... 目录核心思路技术路径实现步骤阶段一:准备工作阶段二:内容提取 (python 脚本)阶段三:语言风格调

C#实现将Excel表格转换为图片(JPG/ PNG)

《C#实现将Excel表格转换为图片(JPG/PNG)》Excel表格可能会因为不同设备或字体缺失等问题,导致格式错乱或数据显示异常,转换为图片后,能确保数据的排版等保持一致,下面我们看看如何使用C... 目录通过C# 转换Excel工作表到图片通过C# 转换指定单元格区域到图片知识扩展C# 将 Excel

基于Java实现回调监听工具类

《基于Java实现回调监听工具类》这篇文章主要为大家详细介绍了如何基于Java实现一个回调监听工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录监听接口类 Listenable实际用法打印结果首先,会用到 函数式接口 Consumer, 通过这个可以解耦回调方法,下面先写一个

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

Qt中QGroupBox控件的实现

《Qt中QGroupBox控件的实现》QGroupBox是Qt框架中一个非常有用的控件,它主要用于组织和管理一组相关的控件,本文主要介绍了Qt中QGroupBox控件的实现,具有一定的参考价值,感兴趣... 目录引言一、基本属性二、常用方法2.1 构造函数 2.2 设置标题2.3 设置复选框模式2.4 是否

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

springboot整合阿里云百炼DeepSeek实现sse流式打印的操作方法

《springboot整合阿里云百炼DeepSeek实现sse流式打印的操作方法》:本文主要介绍springboot整合阿里云百炼DeepSeek实现sse流式打印,本文给大家介绍的非常详细,对大... 目录1.开通阿里云百炼,获取到key2.新建SpringBoot项目3.工具类4.启动类5.测试类6.测