数据结构——栈

  • 1. 栈的概念和结构
  • 2. 栈的实现
    • 2.1 原型声明
    • 2.2 初始化和销毁
    • 2.3 入栈 出栈
    • 2.4 取栈顶数据
    • 2.5 判空
    • 2.6 获取数据个数
  • 3. 总结

  

🔥 博客主页: 偷心编程
🎥 系列专栏: 《Java学习》 《C语言学习》 《数据结构C语言版》
❤️ 感谢大家点赞👍收藏评论✍️
在这里插入图片描述
在这里插入图片描述

  

1. 栈的概念和结构

  栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守 后进先出LIFO(Last In First Out)的原则

  压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
  出栈:栈的删除操作叫做出栈。出数据也在栈顶。

在这里插入图片描述
  我们在前面学习了“顺序表、单链表、双向链表”,在它们的结构原型下,我们都可以实现栈,但是相对来说,用顺序表实现栈会更好,因为顺序表可以很快的找到最后一个元素,进行“进栈”和“出栈”。

2. 栈的实现

2.1 原型声明

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;      //其实top就是顺序表里的size,刚好size就是栈顶的下一个元素int capacity;
}ST;

  注意这里的top(栈顶),有两种处理方法。1. 等同于size,也就是栈中最后一个有效元素的一下个位置,严格意义上来说是栈顶的下一个元素;2. 就是栈顶,最后一个有效元素

  对top的处理方法不同,我们在栈的初始化的时候也就不同,前者top要初始化为0;后者要初始化为-1

  但是为了更好的契合顺序表,所以我们采用第一个处理方案(top=size

2.2 初始化和销毁

// 初始化和销毁
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = pst->top = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}

2.3 入栈 出栈

// 入栈 
void STPush(ST* pst, STDataType x)
{assert(pst);//若是空间满了,扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a,newcapacity * sizeof(STDataType));if (!tmp){perror("malloc:");exit(1);}pst->a = tmp;pst->capacity = newcapacity;}//处理一般情况pst->a[pst->top++] = x;
}
//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top != 0);pst->top--;
}

2.4 取栈顶数据

// 取栈顶数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst->top != 0);return pst->a[pst->top - 1];
}

2.5 判空

// 判空
bool STEmpty(ST* pst)
{return pst->top == 0;
}

2.6 获取数据个数

// 获取数据个数
int STSize(ST* pst)
{return pst->top;
}

3. 总结

  我们主要是学习好栈的结构特点——“后进先出”,我们可以用多种不同的方法来实现,但是用顺序表实现最简单。

  我们为什么要定义这些接口呢,这是人们根据具体问题需要定义的,我们以后做的题目多了,自然会理解其用意。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

谷歌浏览器中编辑并重发请求

文章目录 1、直接重发请求2、修改传参后重发请求3、可能的报错 有时候,需要调整请求参数后,重新发送请求,查看响应,从浏览器搬到Postman太繁琐,可直接在浏览器进行编辑并重发 1、直接重发请求 F12 > Network >…

day19作业

注册登录 #include "log.h" void reg() {char name[20],pwd[20];printf("请输入账号:");fgets(name,sizeof(name),stdin);printf("请输入密码:");fgets(pwd,sizeof(pwd),stdin);//name[strlen(name)-1]\0;printf("账…

[LitCTF 2023]ez_XOR

文件无壳 拖入ida 查看主函数伪c代码 继续跟进xor函数 函数遍历输入的字符串 Str,对每个字符执行异或操作,并将字符与 3 * a2 异或 所以题目的加密过程是将字符串E}J]OrQF[V8zV:hzpV}fVF[t与3异或 写出脚本 def XOR_encrypt(input_str, a2):encrypted_…

[数据结构从小白到大牛]第五篇:3分钟带你吃透双链表并用C语言模拟实现

目录 1->前言 2->链表的概念和结构 2.1链表概念 2.2->带头双向循环链表结构 3->模拟实现带头双向循环链表 3.1定义链表结点 struct ListNode 3.2创建链表结点 CreateLTNode 函数 3.3链表初始化函数 ListInit函数 3.4链表打印函数 ListPrint函数 3.5链表…

心觉:如果做不到“道生一”,能做到“一生道”也不得了

Hi,我是心觉,带你用潜意识化解各种焦虑、内耗,建立无敌自信;教你财富精准显化的实操方法;关注我,伴你一路成长! 每日一省写作222/1000天 想学的东西太多,想练的能力太多,想重塑的负…

基于BP神经网络的手写体数字图像识别

基于BP神经网络的手写体数字图像识别 摘要 在信息化飞速发展的时代,光学字符识别是一个重要的信息录入与信息转化的手段,其中手写体数字的识别有着广泛地应用,如:邮政编码、统计报表、银行票据等等,因其广泛地应用范围…

SpringBoot项目中获取resources下静态文件时遇到的坑

文章目录 问题解决方法1. 上传到服务器指定的文件夹下2. 使用ClassPathResource读取 问题 在项目中需要使用到静态图片,将静态图片放在resources文件夹下。 本地使用this.getClass().getResource()读取静态图片一切正常,成功读取到静态图片。但是将项目…

树莓派AI视觉小车——2.小车蜂鸣器控制实验

如下图所示,蜂鸣器为板载元器件,所以不需要外接其他设备。 将机器人打开电源开机,运行程序代码即可。 import RPi.GPIO as GPIO import timeBuzzer 11CL [0, 131, 147, 165, 175, 196, 211, 248] # Frequency of Low C notes CM [0, 262…

【C++刷题注意事项】bfs?单源bfs?多源bfs?bfs解决拓扑排序?

一、bfs是个什么? 简单而言bfs就是个广度优先遍历,其根本就是我把与跟我当前点相邻的题目中所要求的点都统计出来并进行处理,再去遍历下一个满足的点的邻接的点的信息即可,最大的优势就是只需要不停的入队和出队即可。 那么我们就…

三、Java并发 Java 线程池 ( Thread Pool )

一、前言 本文我们将讲解 Java 中的线程池 ( Thread Pool ),从 Java 标准库中的线程池的不同实现开始,到 Google 开发的 Guava 库的前世今生 注:本章节涉及到很多前几个章节中阐述的知识点。我们希望你是按照顺序阅读下来的,不然…

string模拟实现迭代器

个人主页:Jason_from_China-CSDN博客 所属栏目:C系统性学习_Jason_from_China的博客-CSDN博客 所属栏目:C知识点的补充_Jason_from_China的博客-CSDN博客 string模拟实现迭代器 迭代器的实现 主要实现的两种迭代器 这里我们实现迭代器我们主要…

推荐一款C盘清理工具:360清理Pro

360清理Pro是一款专门用于解决电脑C盘空间不足问题的清理工具。它旨在简化C盘清理过程,让用户能够轻松释放磁盘空间,提高电脑性能。与其它版本不同,这个独立版的360清理Pro无需依赖360安全卫士,是一个独立运行的工具。 软件特点 …

《scientific discovery in the age og artificial intelligence》文献阅读翻译

人工智能时代的科学发现 人工智能(AI)正日益被整合到科学发现中,以增强和加速研究,帮助科学家生成假设、设计实验、收集和解释大数据集,并获得使用传统科学方法可能无法获得的见解。在此,我们探讨了过去十…

字节青训-小D的 abc 变换问题

问题描述 小D拿到了一个仅由 "abc" 三种字母组成的字符串。她每次操作会对所有字符同时进行以下变换: 将 a 变成 bc将 b 变成 ca将 c 变成 ab 小D将重复该操作 k 次。你的任务是输出经过 k 次变换后,得到的最终字符串。 例如:对于初…

Air780E基于LuatOS编程开发

Air780E基于LuatOS编程开发 Air780E开发板下载固件版本开发板刷机开发调试 Air780E开发板 合宙通信推出的 LTE Cat.1 bis通信模块,采用移芯EC618平台,支持4G全网通, 包括的模组有: Air780E – 4G Cat.1Air780EG – Air780EAir510U,支持GNSS/GPS卫星定位…

Chrome与火狐哪个浏览器的移动版本更流畅

在当今的数字化时代,移动设备已经成为我们生活中不可或缺的一部分。而浏览器作为我们访问互联网的重要工具,其性能和用户体验直接影响到我们的使用感受。本文将对比Chrome和火狐(Firefox)两款主流浏览器的移动版本,探讨…

深度学习-pytorch安装与基本使用

一. 基本介绍 Pytorch概念 PyTorch是一个开源机器学习和深度学习框架。PyTorch 允许您使用 Python 代码操作和处理数据并编写深度学习算法,能够在强大的GPU加速基础上实现张量和动态神经网络。 PyTorch是一个基于 Python 的科学计算包,使用 Tensor 作为…

HCIP-HarmonyOS Application Developer V1.0 笔记(五)

弹窗功能 prompt模块来调用系统弹窗API进行弹窗制作。 当前支持3种弹窗API,分别为: 文本弹窗,prompt.showToast;对话框,prompt.showDialog;操作菜单,prompt.showActionMenu。 要使用弹窗功能&…

[极客大挑战 2019]EasySQL 1

[极客大挑战 2019]EasySQL 1 观察题目,发现为登录界面,判断这道题的考点是SQL注入。 知识点 万能密码 知识点原理 当用户尝试登录时 网站后台会进行SQL查询,比如 【select * from table_name where username‘xxxx’ and password‘xxxx…

42.第二阶段x86游戏实战2-lua寻找状态指针

免责声明:内容仅供学习参考,请合法利用知识,禁止进行违法犯罪活动! 本次游戏没法给 内容参考于:微尘网络安全 本人写的内容纯属胡编乱造,全都是合成造假,仅仅只是为了娱乐,请不要…