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

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

相关文章

Spring Security 单点登录与自动登录机制的实现原理

《SpringSecurity单点登录与自动登录机制的实现原理》本文探讨SpringSecurity实现单点登录(SSO)与自动登录机制,涵盖JWT跨系统认证、RememberMe持久化Token... 目录一、核心概念解析1.1 单点登录(SSO)1.2 自动登录(Remember Me)二、代码分析三、

PyCharm中配置PyQt的实现步骤

《PyCharm中配置PyQt的实现步骤》PyCharm是JetBrains推出的一款强大的PythonIDE,结合PyQt可以进行pythion高效开发桌面GUI应用程序,本文就来介绍一下PyCha... 目录1. 安装China编程PyQt1.PyQt 核心组件2. 基础 PyQt 应用程序结构3. 使用 Q

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF(BinaryLoggingFormat)作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析:从文件遍历到数据导出1. 环境准备与依赖库

linux下shell脚本启动jar包实现过程

《linux下shell脚本启动jar包实现过程》确保APP_NAME和LOG_FILE位于目录内,首次启动前需手动创建log文件夹,否则报错,此为个人经验,供参考,欢迎支持脚本之家... 目录linux下shell脚本启动jar包样例1样例2总结linux下shell脚本启动jar包样例1#!/bin

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发,所以面试百分百会问到

Go语言并发之通知退出机制的实现

《Go语言并发之通知退出机制的实现》本文主要介绍了Go语言并发之通知退出机制的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、通知退出机制1.1 进程/main函数退出1.2 通过channel退出1.3 通过cont

Python实现PDF按页分割的技术指南

《Python实现PDF按页分割的技术指南》PDF文件处理是日常工作中的常见需求,特别是当我们需要将大型PDF文档拆分为多个部分时,下面我们就来看看如何使用Python创建一个灵活的PDF分割工具吧... 目录需求分析技术方案工具选择安装依赖完整代码实现使用说明基本用法示例命令输出示例技术亮点实际应用场景扩

java如何实现高并发场景下三级缓存的数据一致性

《java如何实现高并发场景下三级缓存的数据一致性》这篇文章主要为大家详细介绍了java如何实现高并发场景下三级缓存的数据一致性,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 下面代码是一个使用Java和Redisson实现的三级缓存服务,主要功能包括:1.缓存结构:本地缓存:使

如何在Java Spring实现异步执行(详细篇)

《如何在JavaSpring实现异步执行(详细篇)》Spring框架通过@Async、Executor等实现异步执行,提升系统性能与响应速度,支持自定义线程池管理并发,本文给大家介绍如何在Sprin... 目录前言1. 使用 @Async 实现异步执行1.1 启用异步执行支持1.2 创建异步方法1.3 调用

Spring Boot配置和使用两个数据源的实现步骤

《SpringBoot配置和使用两个数据源的实现步骤》本文详解SpringBoot配置双数据源方法,包含配置文件设置、Bean创建、事务管理器配置及@Qualifier注解使用,强调主数据源标记、代... 目录Spring Boot配置和使用两个数据源技术背景实现步骤1. 配置数据源信息2. 创建数据源Be