(C++)栈的链式存储结构(出栈、入栈、判空、遍历、销毁)(数据结构与算法)

链栈是运算受限的单链表、只能在链表头部进行操作
1.链表的头指针就是栈顶,链头为栈顶,链尾为栈底
2.栈的链式存储不需要附设头节点
3.基本不存在栈满的情况,不需要判断栈满,但要判空
4.空栈相当于头指针指向空
5.插入和删除仅在栈顶处执行
6.因为是动态分配空间,所以需要释放

#define MaxSize 100     //链栈的最大长度
typedef int SElemType;  //链栈的数据元素类型假设为int整型
//创建链栈结构
typedef struct StackNode 
{
	SElemType data;   				//结点数据域
	struct StackNode* next;			//结点指针域
}StackNode, *LinkStack;				//struct StackNode的结点形式、链栈形式别名

LinkStack stack;   //创建栈顶指针指向链栈的头结点

注意事项:

LinkStack temp1 = new StackNode;
这里 LinkStack 是一个指针类型别名,实际上是 StackNode* 的别名。
所以 temp1 是一个指针变量,指向 StackNode 类型的结点。

StackNode* temp2 = new StackNode;
这里直接声明了一个 StackNode* 类型的指针变量 temp2,指向 StackNode 类型的结点。

这两种声明方式是等价的。两者都创建了一个动态分配的 StackNode 类型的结点,并将它的地址赋给相应的指针变量。两者都可以通过 temp1->data 或 temp2->data 来访问结点的数据成员,以及 temp1->next 或 temp2->next 来访问结点的下一个结点的指针成员。

因此,在功能上,temp1 和 temp2 没有区别。不同的只是它们的声明方式,temp1 是通过别名 LinkStack 来声明的指针变量,而 temp2 是直接以 StackNode* 类型来声明的指针变量。

链栈存储结构及其实现如下:

#include<iostream>
using namespace std;

#define MaxSize 100     //链栈的最大长度
typedef int SElemType;  //链栈的数据元素类型假设为int整型
//创建链栈结构
typedef struct StackNode 
{
	SElemType data;   				//结点数据域
	struct StackNode* next;			//结点指针域
}StackNode, *LinkStack;				//struct StackNode的结点形式、链栈形式别名

LinkStack stack;   //创建栈顶指针指向链栈的头结点

bool InitStack(LinkStack& stack);					//初始化链栈
bool StackEmpty(LinkStack& stack);					//链栈判空
bool PushStack(LinkStack& stack, SElemType value);	//入栈
bool PopStack(LinkStack& stack, SElemType& value);	//出栈
SElemType GetTop(LinkStack& stack);					//获取栈顶元素
bool StackPrint(LinkStack& stack);					//遍历元素
void DestoryStack(LinkStack& stack);				//销毁链栈,释放内存
int StackLength(LinkStack& stack);					//计算链栈长度/元素个数

//链栈的初始化
bool InitStack(LinkStack& stack)
{
	//构造一个空栈、栈顶指针置为空
	stack = NULL;
	return true; 
}

//判断链栈是否为空
bool StackEmpty(LinkStack& stack)
{
	if (stack == NULL)
	{
		return true; 
	}
	return false;
}

//链栈的入栈
bool PushStack(LinkStack& stack, SElemType value)   //不用判栈满
{
	StackNode* temp = new StackNode; 		//生成新结点temp
	temp->data = value; 					//将新节点数据域置为value
	temp->next = stack; 					//将新结点插入栈顶
	stack = temp; 							//更新栈顶指针
	return true;
}

//链栈的出栈:首先判空
bool PopStack(LinkStack& stack, SElemType &value)
{
	if (StackEmpty(stack))
	{
		return false; 
	}
	value = stack->data;  		//将栈顶数据域元素赋值给value
	StackNode* temp = stack;	//创建一个temp指针,并将其指向 stack 指针所指向的内存地址,以便找到出栈位置并释放。
	stack = stack->next; 		//令栈顶指针指向下一位结点,即更新栈顶指针
	delete temp;   				//释放temp所指向的空间,即出栈元素所占的内存空间,而temp本身会在函数结束后自动销毁。
	return true;  
}

//取栈顶元素
SElemType GetTop(LinkStack& stack)
{
	if (!StackEmpty(stack))  //若栈不为空
	{
		return stack->data;  //返回栈顶元素
	}
	return false; 
}
//获取栈顶长度
/*因为链表的最后一个节点的next指针是nullptr(或者说是NULL),代表链表的终止,
所以可以将链表的遍历条件设置为当前节点指针不等于nullptr,这样在遍历过程中,
当指针指向最后一个节点时,其next指针就会指向nullptr,循环条件就不再成立,
遍历结束,可以避免继续遍历下一个不合法的节点。*/
int StackLength(LinkStack& stack)
{
	int length = 0;
	StackNode* temp = stack;//创建临时指针temp与stack指向同一位置
	while (temp != nullptr)
	{
		length++;  //链栈长度即为栈中元素个数,循环一次,长度++
		temp = temp->next; //temp指针下移一位
	}
	return length; //返回链栈长度
}

//遍历栈元素
bool StackPrint(LinkStack& stack)
{
	if (stack != nullptr)
	{
		StackNode* temp = stack;//创建一个指针与stack指向同一位置
		cout << "出栈顺序:";
		while (temp != nullptr)
		{
			cout << temp->data << " ";
			temp = temp->next;  //temp向下移动一位
		}
		return true;  //遍历完毕
	}
	cout << "栈为空!" << endl;
	return false;
}

//销毁链栈,释放内存
void DestoryStack(LinkStack& stack)
{
	StackNode* temp = new StackNode;//创建一个指针
	while (stack != nullptr)
	{
		temp = stack;//使该临时指针与stack指向同一位置
		stack = temp->next;//更新栈顶指针
		delete temp;//释放临时指针
	}
	stack = nullptr;
	return;
}

//测试代码
int main()
{
	//创建链栈
	LinkStack stack;
	SElemType value;

	InitStack(stack);
	cout << "检查栈是否为空?" << (StackEmpty(stack) ? "\t是" : "\t否") << endl;

	int number = 0;//插入元素个数
	int num = 0; //插入元素值
	cout << "请输入需要插入的元素个数:";
	cin >> number;
	while ((number--) > 0) //计数
	{
		cin >> num;//输入数据
		PushStack(stack, num);//插入所输入元素
	}
	cout << "当前栈的元素个数:" << StackLength(stack) << endl; 
	cout << "获取栈顶元素:" << GetTop(stack) << endl;
	StackPrint(stack); //遍历打印栈顶元素

	cout << endl;
	PopStack(stack, value); //出栈
	cout << "出栈一次后栈顶元素为:" << GetTop(stack) << endl;
	StackPrint(stack);//遍历打印链栈元素

	DestoryStack(stack);
	cout << endl << "栈已被销毁释放" << endl;

	cout << "销毁栈后打印输出结果:" <<" ";
	StackPrint(stack);
	cout << "销毁栈后遍历栈结果:" << " ";
	StackPrint(stack);

	system("pause");
	return 0;
}

结果:
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/153572.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ncbi-datasets-cli-高效便捷下载NCBI数据

文章目录 简介安装datasets download下载基因组/基因序列按照GCA list文件编号下载下载大基因组genome完整参数gene参数 datasets summary下载元数据dataformat将json转换成表格格式通过json文件解析其他字段问题 简介 NCBI Datasets 可以轻松从 NCBI 数据库中收集数据。使用命…

牛客 —— 链表中倒数第k个结点(C语言,快慢指针,配图)

目录 1. 思路1&#xff1a;倒数第K个节点&#xff0c;就是整数第N-K1的节点 2. 思路2&#xff1a;快慢指针 1. 思路1&#xff1a;倒数第K个节点&#xff0c;就是整数第N-K1的节点 链表中&#xff0c;一共有N个节点&#xff0c;如果我们想要得出倒数第K个节点&#xff0c;我们…

windows server 华夏ERP部署手册

软件包准备&#xff1a; .安装MySql 找到mysql程序双击进行安装,进入这个页面 选择Server only点击Next 进入到下图,点击execute&#xff0c;等待完成&#xff0c;点击下一步 点击install安装插件 安装完插件点击下一步 等待程序加载完成,点击下一步 继续下一步 进行下一步 进行…

不加家长好友,如何私密发成绩?

身为老师的你&#xff0c;是否经常收到家长们的询问&#xff0c;要求你告知他们孩子的成绩&#xff1f;而你却因为规定&#xff0c;不能直接将成绩公布&#xff1f;那么&#xff0c;如何解决这个问题呢&#xff1f; 成绩查询系统。是专门为学生和家长提供成绩查询服务的系统。可…

智慧农业新篇章:拓世法宝AI智能直播一体机助力乡村振兴与农业可持续发展

随着乡村振兴战略的深入推进&#xff0c;农业发展日益成为国家关注的焦点。在这一大背景下&#xff0c;助农项目的兴起成为支持乡村振兴的一项重要举措。 乡村振兴战略的实施&#xff0c;得益于《关于推动文化产业赋能乡村振兴的意见》、《关于全面推进乡村振兴加快农业农村现…

vscode Prettier配置

常用配置项&#xff1a; .prettierrc.json 是 Prettier 格式化工具的配置文件 {"printWidth": 200, // 指定行的最大长度"tabWidth": 2, // 指定缩进的空格数"useTabs": false, // 是否使用制表符进行缩进&#xff0c;默认为 false"singl…

Behave介绍和快速示例

Behave是一个用于行为驱动开发 (Behavior-Driven Development, BDD) 的 Python 库。使用 Behave&#xff0c;可以编写自然语言格式的使用场景来描述软件的行为&#xff0c;然后用 Python 实现这些场景下的步骤&#xff0c;形成可直接运行的测试。 Behave的目标是帮助用户、开发…

RT-DETR算法优化改进:自研独家创新BSAM注意力 ,基于CBAM升级 | 注意力机制大作战

💡💡💡本文全网首发独家改进:提出新颖的注意力BSAM(BiLevel Spatial Attention Module),创新度极佳,适合科研创新,效果秒杀CBAM,Channel Attention+Spartial Attention升级为新颖的 BiLevel Attention+Spartial Attention 1)作为注意力BSAM使用; 推荐指数:…

B/S麻醉临床信息系统(手麻系统)源码

手术麻醉系统是一套以数字形式与医院信息系统&#xff08;如HIS、EMR、LIS、PACS等&#xff09;和医疗设备等软、硬件集成并获取围手术期相关信息的计算机系统&#xff0c;其核心是对围手术期患者信息自动采集、储存、分析并呈现。该系统通过整合围手术期中病人信息、人员信息、…

DBeaver还原mysql数据库

DBeaver还原mysql数据库 DBEaver还原mysql数据库新建一个要还原的数据库选择工具》恢复数据库 DBEaver还原mysql数据库 新建一个要还原的数据库 选中数据库,右键新建一个数据库&#xff0c;字符集和排序规则默认的即可 选择工具》恢复数据库 选中刚刚创建好的数据库&#x…

springboot326校园体育场馆(设施)使用管理网站

交流学习&#xff1a; 更多项目&#xff1a; 全网最全的Java成品项目列表 https://docs.qq.com/doc/DUXdsVlhIdVlsemdX 演示 项目功能演示&#xff1a; ————————————————

Garmin佳明发布quatix 7 Pro航海商务智能腕表,于陆地之外乘风破浪

全新航海商务智能腕表&#xff0c;专为水上活动爱好者设计 搭载1.3英寸AMOLED屏幕&#xff0c;内置LED手电筒&#xff0c;长达16天电池续航 【2023年11月16日】今日&#xff0c;专业运动智能可穿戴设备及创新航海设备品牌佳明&#xff08;纽交所代码&#xff1a;GRMN&#xff…

Linux/麒麟系统上部署Vue+SpringBoot前后端分离项目

目录 1. 前端准备工作 1.1 在项目根目录创建两份环境配置文件 1.2 环境配置 2. 后端准备工作 2.1 在项目resources目录创建两份环境配置文件 2.2 环境配置 3. 前后端打包 3.1 前端打包 3.2 后端打包 4、服务器前后端配置及部署 4.1 下载、安装、启动Nginx 4.2 前端项目部署…

学而优则“创”西电学子助力openGauss教学“破圈”,一举斩获金奖

在你的大学生涯&#xff0c;是否有过发现某本教材作者就是本校老师的经历&#xff1f;是否曾经为在课堂上见到作者本人而感到些许骄傲&#xff1f;实际上&#xff0c;这样的巧合在很多专业领域常有发生&#xff0c;因为一线教师往往既是知识的传道者&#xff0c;也是知识的生产…

Kafka 集群如何实现数据同步?

哈喽大家好&#xff0c;我是咸鱼 最近这段时间比较忙&#xff0c;将近一周没更新文章&#xff0c;再不更新我那为数不多的粉丝量就要库库往下掉了 T﹏T 刚好最近在学 Kafka&#xff0c;于是决定写篇跟 Kafka 相关的文章&#xff08;文中有不对的地方欢迎大家指出&#xff09;…

简单高效的定制移动固态硬盘,稳定易用的办公小助手

我在平时的工作中&#xff0c;常常需要处理各种大文件和数据&#xff0c;如果硬盘速度跟不上&#xff0c;那工作效率就会大幅降低。今年固态硬盘的价格大幅下降&#xff0c;有很多国产品牌加入其中&#xff0c;很容易找到一款性价比高的固态硬盘&#xff0c;搭配硬盘盒使用&…

EV代码签名证书

为了增强软件的安全性和可信度&#xff0c;EV代码签名证书&#xff08;Extended Validation Code Signing Certificate&#xff09;成为了一种具有最高级别保障的关键工具。 EV代码签名证书是一种由受信任的证书颁发机构&#xff08;CA&#xff09;或证书供应商提供的高级别代…

免费最强下载工具IDM,没有之一

IDM(Internet Download Manager)下载工具是我见过的最强下载工具&#xff0c;没有之一。主要以下特点&#xff1a; 下载程度超快实时检测下载行为下载任何文件探测视频下载地址&#xff0c;几分钟下载高清视频可多进程下载&#xff0c;可多线程下载 IDM官网地址&#xff1a;下…

性能测试知多少---系统架构分析

之前有对性能需求进行过分析&#xff0c;那篇主要从项目业务、背景等角度如何抽丝剥茧的将项目的需求抽离出来。在我们进行需求的时候也需要对被测项目的架构有一定的认识&#xff0c;如果不了解被测系统的架构&#xff0c;那么在后期的性能分析与调优阶段将无从下手。 简单系…