【数据结构】三、栈和队列：3.链栈（链栈栈的初始化，判空，进栈，出栈，读取栈顶，链栈实例）

文章目录

    • 3.链栈
      • 3.1初始化
      • 3.2判空
      • 3.3获取栈长度
      • 3.4入栈
      • 3.5出栈
      • 3.6销毁链栈
      • 3.7读取栈顶
      • 3.8遍历输出
      • ❗3.9链栈c++实例

3.链栈

链栈是运算受限的单链表，只能在链表头部进行操作的单链表。

  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;   //创建栈顶指针指向链栈的头结点
  • *StackNode，LinkStack的区别：
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* 类型来声明的指针变量。

3.1初始化

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

3.2判空

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

3.3获取栈长度

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

3.4入栈

链栈的入栈相当于单链表的前插法。

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

3.5出栈

//出栈：首先判空
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;
}

3.6销毁链栈

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

3.7读取栈顶

//读取栈顶：取栈顶元素
bool GetTop(LinkStack& stack, SElemType &value){
	if (!StackEmpty(stack)){  	//若栈不为空
		value = stack->data;  		//返回栈顶元素
		return true;
	}
	cout<<"栈为空"<<endl;
	return false; 
}

3.8遍历输出

//遍历输出栈元素
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;
}

❗3.9链栈c++实例

#include<iostream>
using namespace std;

#define MaxSize 100     //链栈的最大长度
typedef int SElemType;  //链栈的数据元素类型假设为int整型

//创建链栈结构

typedef struct StackNode 
{
	SElemType data;   				//结点数据域
	struct StackNode* next;			//结点指针域
}StackNode, *LinkStack;				//struct StackNode的结点形式、链栈形式别名

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


int main()
{
	//创建链栈
	LinkStack stack;
	SElemType value=1;

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

	int number = 0;	//插入元素个数

	cout << "请输入需要插入的元素个数：";
	cin >> number;
	while ((number--) > 0) {
		PushStack(stack, value);//插入所输入元素
        value++;
	}

	cout << "当前栈的元素个数：" << StackLength(stack) << endl;

	GetTop(stack, value);
	cout << "栈顶元素：" << value << endl;
	StackPrint(stack);//遍历打印栈顶元素

	cout << endl;
	PopStack(stack, value);
	cout << "出栈一次,栈顶元素为：" << value << endl;
	StackPrint(stack);

	DestroyStack(stack);
	cout << endl << "栈已被销毁释放" << endl;
	cout << "销毁栈后遍历栈结果：" << " ";
	StackPrint(stack);

	system("pause");
	return 0;
}




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

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


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

//入栈（前插法）
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;
}

//取栈顶元素
bool GetTop(LinkStack& stack, SElemType &value){
	if (!StackEmpty(stack)){  	//若栈不为空
		value = stack->data;  		//返回栈顶元素
		return true;
	}
	cout<<"栈为空"<<endl;
	return false; 
}


//遍历输出栈元素
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 DestroyStack(LinkStack& stack){
	StackNode* temp = new StackNode;	//创建一个指针
	while (stack != nullptr){
		temp = stack;				//使该临时指针与stack指向同一位置
		stack = temp->next;	//更新栈顶指针
		delete temp;				//释放临时指针
	}
	stack = nullptr;
}

检查栈是否为空？ 是
请输入需要插入的元素个数：5
1
2
3
4
5
当前栈的元素个数：5
栈顶元素：5
出栈顺序：5 4 3 2 1
出栈一次,栈顶元素为：5
出栈顺序：4 3 2 1
栈已被销毁释放
销毁栈后打印输出结果： 栈为空！
销毁栈后遍历栈结果： 栈为空！
Press any key to continue . . .

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

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

相关文章

ElasticSearch语句中must,must_not,should 组合关系

ElasticSearch语句中must,must_not,should 组合关系

前言&#xff1a; 在实际应用中&#xff0c;发现当bool中同时使用must和should 没有达到想要的想过&#xff0c;而是只展示了must中的命中数据&#xff0c;所以打算探究一下bool中 三种逻辑关系的组合。 上述查询语句只展示了must的结果&#xff0c;没有should中的结果&#…
阅读更多...
本地Windows主机，使用pycharm通过wsl的ubuntu来创建django项目

本地Windows主机，使用pycharm通过wsl的ubuntu来创建django项目

Windows主机在pycharm中通过wsl的ubuntu来创建django项目 需求&#xff1a;在windows主机中创建python项目再转接到linux服务器中运行&#xff0c;有点麻烦。【特别是存放日志文件或其他文件路径时需要修改为linux中的路径】 1&#xff1a;我的是windows主机 2&#xff1a;有…
阅读更多...
基于java+springboot+vue实现的个人博客系统（文末源码+Lw）200

基于java+springboot+vue实现的个人博客系统（文末源码+Lw）200

摘 要 随着国内市场经济这几十年来的蓬勃发展&#xff0c;突然遇到了从国外传入国内的互联网技术&#xff0c;互联网产业从开始的群众不信任&#xff0c;到现在的离不开&#xff0c;中间经历了很多挫折。本次开发的个人博客系统&#xff0c;有管理员&#xff0c;用户&#xf…
阅读更多...
神经网络参数初始化

神经网络参数初始化

&#x1f4bd;参数初始化是神经网络训练过程中的一个重要步骤。在构建神经网络时&#xff0c;我们需要为权重和偏置等参数赋予初始值。对于偏置&#xff0c;通常可以将其初始化为0或者较小的随机数。然而&#xff0c;对于权重w的初始化&#xff0c;我们通常会采用更加复杂的方法…
阅读更多...
【论文笔记 | 异步联邦】PORT：How Asynchronous can Federated Learning Be?

【论文笔记 | 异步联邦】PORT：How Asynchronous can Federated Learning Be?

1. 论文信息 How Asynchronous can Federated Learning Be?2022 IEEE/ACM 30th International Symposium on Quality of Service (IWQoS). IEEE, 2022&#xff0c;不属于ccf认定 2. introduction 2.1. 背景&#xff1a; 现有的异步FL文献中设计的启发式方法都只反映设计空…
阅读更多...
《2024年绿色发展报告》：算力与电力矛盾愈加突出！

《2024年绿色发展报告》：算力与电力矛盾愈加突出！

2024年4月22日&#xff0c;第55个世界地球日&#xff0c;超聚变发布《2024年绿色发展报告》&#xff0c;向社会展示超聚变面对宏观形势变化、产业趋势变化&#xff0c;推进绿色发展、科技向绿的探索与实践成果。 2023年&#xff0c;算力产业发生了深刻变化。大模型带来AI算力需…
阅读更多...
小程序中如何快速给分类添加商品

小程序中如何快速给分类添加商品

​快速在分类下面上传商品&#xff0c;并且能够设置商品顺序&#xff0c;关系到运营效率的高低。下面就具体介绍如何快速在某个分类下面设置商品。 一、在商品管理处&#xff0c;查询某个分类下面的商品。 进入小程序管理员后台->商品管理&#xff0c;点击分类输入框&…
阅读更多...
从零开始利用MATLAB进行FPGA设计（五）详解双口RAM

从零开始利用MATLAB进行FPGA设计（五）详解双口RAM

创作于谱仪算法设计过程中的数字能谱生成模块设计。 往期回顾&#xff1a; 从零开始利用MATLAB进行FPGA设计&#xff08;四&#xff09;生成优化HDL代码 从零开始利用MATLAB进行FPGA设计&#xff08;三&#xff09;将Simulink模型转化为定点数据类型 目录 1.关于双口RAM …
阅读更多...
大模型咨询培训老师叶梓：利用知识图谱和Llama-Index增强大模型应用

大模型咨询培训老师叶梓：利用知识图谱和Llama-Index增强大模型应用

大模型&#xff08;LLMs&#xff09;在自然语言处理领域取得了显著成就&#xff0c;但它们有时会产生不准确或不一致的信息&#xff0c;这种现象被称为“幻觉”。为了提高LLMs的准确性和可靠性&#xff0c;可以借助外部知识源&#xff0c;如知识图谱。那么我们如何通过Llama-In…
阅读更多...
Web前端开发之CSS_1

Web前端开发之CSS_1

CSS选择器字体属性背景属性文本属性表格属性 1. CSS 1.1 CSS简介 CSS&#xff08;Cascading Style Sheets&#xff09;层叠样式表&#xff0c;又叫级联样式表&#xff0c;简称样式表。CSS文件后缀名为 .css 。CSS用于HTML文档中元素样式的定义。使用CSS可以让网页具有美观一致…
阅读更多...
算法 || 二分查找

算法 || 二分查找

目录 二分查找 在排序数组中查找元素的第一个和最后一个位置 搜索插入位置 一个数组经过划分后具有二段性的都可以用二分查找 二分查找 704. 二分查找 - 力扣&#xff08;LeetCode&#xff09; ​ 暴力解法&#xff1a;直接遍历数组&#xff0c;找到 target 便返回下标&am…
阅读更多...
【blog项目】layui与jquery冲突导致鼠标悬停事件失效、如何调用layui.use()作用域里的方法

【blog项目】layui与jquery冲突导致鼠标悬停事件失效、如何调用layui.use()作用域里的方法

blog项目前台展示——查询数据库中的文章类型并展示时出现的bug 1 正常演示 2 用jquery查询数据库并添加到页面后 3 相关代码 <script src"/static/jquery-2.1.4.js"></script> <script src"/static/layui/layui.js"></script> …
阅读更多...
排序算法-计数排序

排序算法-计数排序

一、计数排序 这种排序算法 是利用数组下标来确定元素的正确位置的。 如果数组中有20个随机整数&#xff0c;取值范围为0~10&#xff0c;要求用最快的速度把这20个整数从小到大进行排序。 很大的情况下&#xff0c;它的性能甚至快过那些时间复杂度为O(nlogn&#xff09;的排序。…
阅读更多...
使用PyCharm开发工具创建工程

使用PyCharm开发工具创建工程

一. 简介 前面文章实现了开发 python程序使用的 开发工具PyCharm&#xff0c;本文来学习使用 PyCharm开发工具创建一个 python工程。 二. 使用PyCharm开发工具创建工程 1. 首先&#xff0c;打开 PyCharm开发工具&#xff0c;打开 "New project" 选项&#xff1a; …
阅读更多...
git如何查询回退之前的提交记录

git如何查询回退之前的提交记录

git如何查询回退之前的提交记录 使用 git reflog 命令&#xff1a; 使用 git reflog 命令&#xff1a; git refloggit reflog 显示的是你的本地引用日志&#xff0c;它包含了所有HEAD指向变更的历史记录&#xff0c;即使那些已经被删除的提交也会出现在这里。当你误操作回退并…
阅读更多...
一款可视化正则表达式工具

一款可视化正则表达式工具

regex-vis是一款在线免费且可视化的正则表达式工具 界面图&#xff1a; 只能输入由26个英文字母组成的字符串 ^[A-Za-z]$ 只能输入数字 ^[0-9]*$测试错误 测试正确 快来感受一下叭 官方网址&#xff1a; Regex VisRegex visualizer & editor, make the regular expr…
阅读更多...
Java根据模板动态生成Pdf(添加页码、文件加密、Spire免费版本10页之后无法显示问题、嵌入图片添加公章、转Base64)

Java根据模板动态生成Pdf(添加页码、文件加密、Spire免费版本10页之后无法显示问题、嵌入图片添加公章、转Base64)

Java根据模板动态生成Pdf&#xff1a;添加页码、文件加密、Spire免费版本10页之后无法显示问题、嵌入图片添加公章、转Base64 引言【Java根据模板动态生成Pdf资源地址】示例一&#xff1a;动态生成带页码的PDF报告示例二&#xff1a;加密PDF以保护敏感信息示例三&#xff1a;应…
阅读更多...
设计模式——终止模式之两阶段终止模式

设计模式——终止模式之两阶段终止模式

文章目录 1. 错误思路2. 两阶段终止模式2.1 利用 isInterrupted2.2 利用停止标记interrupt-打断park Two Phase Termination 在一个线程 T1 中如何“优雅”终止线程 T2&#xff1f;这里的【优雅】指的是给 T2 一个料理后事的机会。 1. 错误思路 使用线程对象的 stop() 方法停…
阅读更多...
容器工作流

容器工作流

背景 目前某平台使用计算容器和解析容器&#xff0c;这两种容器目前通过rabbitmq消息来进行链接&#xff0c;形成容器工作流&#xff0c;使用容器工作流框架可以省去两个容器中间环节的控制&#xff0c;不需要再使用java代码对容器的操作&#xff0c;通过容器工作流框架即可控…
阅读更多...
Docker常见问题排查思路与实战

Docker常见问题排查思路与实战

Docker作为一种流行的容器化技术&#xff0c;已经在众多场景中得到广泛应用。然而&#xff0c;在使用过程中&#xff0c;我们难免会遇到各种问题。本文将介绍一些常见的Docker问题及其排查思路&#xff0c;并通过实战案例帮助大家更好地理解和应对这些挑战。 1. Docker容器启动…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站