(数据结构)栈的实现——再一次保姆级教学

news/2024/2/21 4:01:29

目录

1. 栈

​编辑

 1.2 栈的实现

2. 代码的实现

2.1 初始化栈和销毁栈

2.2栈顶元素的插入

2.3栈顶元素的删除

栈元素删除

2.4栈顶元素的获取和栈元素的个数


1. 栈

1.1 栈的概念和结构

栈(Stack)是一种线性存储结构,它具有如下特点:
(1)栈中的数据元素遵守”先进后出”(First In Last Out)的原则,简称FILO结构。
(2)限定只能在栈顶进行插入删除操作。

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

注意:我们在进行数据插入和删除操作中,都是在栈顶实现的,而另一端叫做栈底。

我们借用一下这个图来说明:

 1.2 栈的实现

我们这里可以通过两种方法实现,顺序表链表。

这里我们会发现链表要尾插或者尾删需要便利一遍链表,效率低;顺序表尾插尾删很快,但是还要解决扩容问题。

所以这里我们就引出了栈这个东西

2. 代码的实现

这里我们需要说明一下,之前我们在实现链表或者顺序表双向链表中都用的是size,为了更好的明确个数。

这里top指的是栈顶元素,如果初始化为 ” -1 “ ,指的是栈顶元素;如果为 “ 0 ” ,指的是栈顶的下一个元素。

这里面我建议是初始化为0

  • top还可以表示元素的个数,可以用来判断栈是否满了
  • 插入元素的时候直接在top的位置插入就行,然后再top++即可

 废话不多先来个头文件

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);

2.1 初始化栈和销毁栈

我们首先要检查一下结构体是否为空,这里我们要注意一下

void STInit(ST* pst)
{assert(pst);pst->a = NULL;//pst->top = -1;   // top 指向栈顶数据pst->top = 0;   // top 指向栈顶数据的下一个位置pst->capacity = 0;
}

这里我们断言结构体不为空在继续,释放我们开辟的空间,将其他数据置为0

void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}

2.2栈顶元素的插入

这里面我们要判断储存空间是否足够,如果没有开辟,我们可以先开辟一些空间出来;如果栈空间满了,直接将栈空间扩大二倍

void STPush(ST* pst, STDataType x)
{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 == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newCapacity;}pst->a[pst->top] = x;pst->top++;
}

2.3栈顶元素的删除

注意:当top为0,代表我们没有元素,不能再减下去,需要一个函数判断一下

判断函数

bool STEmpty(ST* pst)
{assert(pst);/*if (pst->top == 0){return true;}else{return false;}*/return pst->top == 0;
}

栈元素删除

void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst->top--;
}

2.4栈顶元素的获取和栈元素的个数

这里面我们初始化为0,所以我们返回栈顶元素前一个元素即可;如果为空,需要我们断言一下

STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->a[pst->top - 1];
}

元素个数

int STSize(ST* pst)
{assert(pst);return pst->top;
}

以上就是今天栈实现的分享,如果喜欢的话请三联支持一下吧,感谢你的收看,我们下期再见!!!


http://www.ppmy.cn/news/69507.html

相关文章

【网络】Socket编程-TCP篇

文章目录 简单的TCP网络程序服务器:服务端创建套接字socket函数 服务端绑定bind函数bzero函数引入命令行参数 服务端监听listen函数 服务端获取连接accept函数 测试上述的功能telnet命令 服务端处理请求(提供服务)read函数write函数 tcp_server.cc客户端客户端创建套接字引入命…

【数据结构】栈的详解

☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪&…

20 散列表的查找

散列表的查找 简介:散列表(也成哈希表)是一种高效的数据结构,他可以在平均复杂度为O(1)的情况下实现查找、插入和删除操作。 哈希表的基本思想是根据关键字的值来计算其应存储的位置。这个计算过程就是通过哈希函数来实现的。 根…

针对大集群node 对 Kubernetes 集群七大优化大法

一、节点配额和内核参数调整 对于公有云上的 Kubernetes 集群,规模大了之后很容器碰到配额问题,需要提前在云平台上增大配额。这些需要增大的配额包括: 虚拟机个数vCPU 个数内网 IP 地址个数公网 IP 地址个数安全组条数路由表条数持久化存储…

深度学习 -- 逻辑回归 PyTorch实现逻辑回归

前言 线性回归解决的是回归问题,而逻辑回归解决的是分类问题,这两种问题的区别是前者的目标属性是连续的数值类型,而后者的目标属性是离散的标称类型。 可以将逻辑回归视为神经网络的一个神经元,因此学习逻辑回归能帮助理解神经…

Java 中的访问修饰符有什么区别?

Java 中的访问修饰符用于控制类、类的成员变量和方法的访问权限,主要有以下四种: public:公共访问修饰符,可以被任何类访问。public 修饰的类、成员变量和方法可以在任何地方被访问到。 protected:受保护的访问修饰符…

【C++】8.编译:CMake工具入门

😏*★,*:.☆( ̄▽ ̄)/$:*.★* 😏这篇文章主要介绍CMake工具的入门使用。————————————————学其所用,用其所学。——梁启超————————————————— 欢迎来到我的博客,一起学习知识…

【Hello Algorithm】归并排序及其面试题

作者:小萌新 专栏:算法 作者简介:大二学生 希望能和大家一起进步 本篇博客简介:介绍归并排序和几道面试题 归并排序及其面试题 归并排序归并排序是什么归并排序的实际运用归并排序的迭代写法归并排序的时间复杂度 归并排序算法题小…

2023-04-30:用go语言重写ffmpeg的resampling_audio.c示例,它实现了音频重采样的功能。

2023-04-30:用go语言重写ffmpeg的resampling_audio.c示例,它实现了音频重采样的功能。 答案2023-04-30: resampling_audio.c 是 FFmpeg 中的一个源文件,其主要功能是实现音频重采样。 音频重采样是指将一段音频数据从一个采样率…

mysql事务及搜索引擎

mysql事务后半部分 加快查询速度索引会自动排序,(升序) select * from t1;全盘扫描 where可以索引查找show create table 索引是一个排序的列表,包含字段值和相应行数据的物理地址 事务是一种机制,一个…

Spark大数据处理讲课笔记3.5 RDD持久化机制

文章目录 零、本讲学习目标一、RDD持久化(一)引入持久化的必要性(二)案例演示持久化操作1、RDD的依赖关系图2、不采用持久化操作3、采用持久化操作 二、存储级别(一)持久化方法的参数(二&#x…

android log的使用

现在在分析一个android netd的问题,只要一开启热点, for (String ifname : added) {try {Log.d(TAG, "TetheredState, processMessage CMD_TETHER_CONNECTION_CHANGED, add mIfaceName " mIfaceName " ifname " ifname );mNetd.…

etcd的Watch原理

在 Kubernetes 中,各种各样的控制器实现了 Deployment、StatefulSet、Job 等功能强大的 Workload。控制器的核心思想是监听、比较资源实际状态与期望状态是否一致,若不一致则进行协调工作,使其最终一致。 那么当你修改一个 Deployment 的镜像…

蛋糕烘焙店小程序开发 让生活多点甜

蛋糕甜品因为较高的颜值、香甜的口感深受大众喜欢,当我们路过一家蛋糕烘焙店的时候,飘香的味道让我们流连忘返。但是互联网时代,各个行业都在转型,蛋糕烘焙店也需要由传统线下店面向线上线下结合的方式转变,以求摆脱区…

LeetCode 63 不同路径 II

题目: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。现在考虑网格中有障碍物。那么从左…

Golang笔记:使用os.Args和flag包编写命令行界面(CLIs)

文章目录 目的os.ArgsflagFlagSet总结 目的 命令行界面(Command-line Interfaces)是比较常用的一种软件形式。对于大部分开发运维人员来说很多时候CLIs可能比图形界面更加方便。软件开发时也经常会有需要开发命令行界面形式软件的情况,使用G…

Highcharts Core Crack

Highcharts Core Crack 添加了新的“x轴交叉”和“y轴交叉”选项,使创建数学绘图的轴布局变得更容易。 添加了新的“series.legendSymbol”选项。 Highcharts是业界领先的JavaScript图表库。Highcharts被数以万计的开发人员和全球100家最大公司中超过80%的公司使用。…

Leetcode 第 345 场周赛 Problem D 统计完全连通分量的数量

Leetcode 第 345 场周赛 Problem D 统计完全连通分量的数量题目 给你一个整数 n 。现有一个包含 n 个顶点的 无向 图,顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] [ai, bi] 表示顶点 ai 和 bi 之间存在一条 无向 边。返回图中 完全连通分…

大咖齐聚CCIG论坛——文档图像智能分析的产业前沿

目录 1 文档图像智能分析技术2 大咖齐聚CCIG20233 议题介绍3.1 从模式识别到类脑研究3.2 视觉-语言预训练模型演进及应用3.3 篡改文本图像的生成和检测3.4 智能文档处理在工业界的应用与挑战 4 观看入口&议程 1 文档图像智能分析技术 文档图像智能分析是指使用计算机视觉和…

Maven基础篇

Maven基本概念 Maven是什么 maven的本质是一个项目管理工程,将项目开发和管理过程抽象成一个项目对象模型(POM) POM(Project Object Model):项目对象模型 作用 项目构建:提供标准的、跨平台…
最新文章