什么是栈,如何实现?

news/2024/10/31 5:29:11/

欢迎来到 Claffic 的博客 💞💞💞 

“但有一枝堪比玉,何须九畹始征兰?”

前言:

栈是一种特殊的线性表,就像开盖的桶一样,从底部开始放数据,从顶部开始取数据,那么栈具体是如何实现的呢?这篇博客为你解答:


目录

💩Part1:何为栈

1.栈的概念

2.栈的结构 

🪲Part2: 栈的实现

1.前期准备

1.1创建项目

1.2栈的结构

1.3栈的初始化

2.相关功能实现

2.1入栈

2.2检测栈是否为空 

2.3出栈

2.4获取栈顶元素

2.5获取栈中有效元素的个数

2.6销毁栈 


Part1:何为栈

1.栈的概念

栈是一种特殊的线性表,只允许从特定的一端插入或删除元素,栈中数据的元素遵循后进先出原则(Last In First Out)

进行数据插入和删除的一端称为栈顶,另一端称栈底。 

就像个桶子一样,总是先从顶部放入或取出元素。

2.栈的结构 

说完了栈的概念,大家的脑海里也许就会有栈的基本样子了,这里画图解释: 

 我是图示

Part2: 栈的实现

1.前期准备

1.1创建项目

老样子,三个项:

SList.h:头文件,声明所有函数;

SList.c:源文件,实现各函数;

test.c:  源文件,主函数所在项,可调用各函数。

1.2栈的结构

在创建结构体之前,我们不妨要考虑一个问题:
用数组还是链表来实现栈?

数组:存储空间在物理上连续,随机访问时间复杂度O(1)

链表:存储空间在逻辑上连续,但物理上不一定连续,随机访问时间复杂度O(N).

就栈的特点来说,数组更接近。还是数组香哇。

所以我们 用数组来实现栈

创建一个结构体,其中的元素包含: 

数组首元素的地址;

栈顶;

容量。

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; // 栈顶int capacity; // 容量
}Stack;

1.3栈的初始化

既然创建了栈,就要进行初始化

无非就是对结构体中的元素进行初始化:

数组容量,先定义一个初始大小:4个元素大小,并且是动态的。

栈顶的话,可以是0,也可以是-1:

0时,top 的位置就是栈顶元素的下一个位置;

-1时,top 的位置就是栈顶元素的位置。

在这里我们取 top = 0

// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;
}

2.相关功能实现

2.1入栈

所谓入栈,就相当于尾部插入新的数据。

要注意插入数据前需检查是否满容,判断方法也很简单,就看 栈顶与容量 是否相等就可以。

// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->capacity == ps->top){STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = data;ps->top++;
}

2.2检测栈是否为空 

这里把检测栈是否为空单独封装成一个函数,是为了出栈做铺垫;

在栈为空的情况下是不能出栈的,所以出栈前要检测栈是否为空;

这里我们约定 如果为空返回非0结果,如果为不为空返回0

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;//表达式,真为非0,假为0
}

2.3出栈

出栈就相当于删除数据,但又不完全等于删除数据

只是改变了栈顶 ,栈顶之外的元素占有的空间不需要释放。

// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));//注意逻辑反,为空就报错ps->top--;
}

2.4获取栈顶元素

因为是栈,总要在栈顶取元素的

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);return ps->a[ps->top-1];//注意元素个数与下标差1
}

2.5获取栈中有效元素的个数

其实就是栈顶啦,栈顶的数值代表了栈中有效元素的个数;

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}

2.6销毁栈 

用完了栈,要记得销毁哦。

其实就是该释放的释放,容量归0,栈顶置为-1,表示没有元素。

// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = -1;
}

代码已上传至 我的gitee

拿走不谢~ 


总结:

栈也是线性表,具有后进先出的特点,在有这总需求的情况下可以应用,你学会了吗?

码文不易 

如果你觉得这篇文章还不错并且对你有帮助,不妨支持一波哦  💗💗💗


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

相关文章

java基础面试题(一)

java概述1.何为编程?让计算机为解决某个问题而使用程序设计语言编写程序代码,并得到结果的过程。2.什么是java?java是面向对象的编程语言,具有功能强大、简单易用的特征。3.jdk、jre、jvmjdk:java的开发工具(包含jre&a…

基于Spring Boot的酒店管理系统

文章目录 项目介绍主要功能截图:登录首页房间类型酒店预约部分代码展示设计总结项目获取方式🍅 作者主页:Java韩立 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅 项目介绍 基于Spring Boot的酒店管理系统…

C语言变量和数据类型的使用

文章目录前言一、将变量输出打印到控制台1.整形变量的输出2.浮点型变量的输出1.flaot的输出2.doble的输出3.float和double输出的区别4.%f,%10.2f......二、数据类型的大小总结前言 上一篇文章我们学习了C语言变量和数据类型的基本概念那么今天我们就具体的来看看如何在代码中使…

插件化架构设计(2):插件化从设计到实践该考量的问题汇总

根据《插件式可扩展架构设计心得》精读扩展版 怎么实现插件化模式 插件模式本质是一种设计思想,并没有一个一成不变或者是万金油的实现。但我们经过长期的代码实践,其实已经可以总结出一套方法论来指导插件体系的实现,并且其中的一些实现细…

Transformer在计算机视觉中的应用-VIT、TNT模型

上期介绍了Transformer的结构、特点和作用等方面的知识,回头看下来这一模型并不难,依旧是传统机器翻译模型中常见的seq2seq网络,里面加入了注意力机制,QKV矩阵的运算使得计算并行。 当然,最大的重点不是矩阵运算&…

汽车4S店业务管理软件

一、产品简介  它主要提供给汽车4S商店,用于管理各种业务,如汽车销售、售后服务、配件、精品和保险。整个系统以客户为中心,以财务为基础,覆盖4S商店的每一个业务环节,不仅可以提高服务效率和客户满意度,…

【ChatGPT】论文阅读神器 SciSpace 注册与测试

【ChatGPT】论文阅读神器 SciSpace 注册与测试1. 【SciSpace】网址与用户注册1.1 官网地址:[【SciSpace官网】https://typeset.io](https://typeset.io)1.2 官网注册2. 【SciSpace】实战解说2.1 导入论文2.2 论文分析2.3 中文分析2.4 论文分析进阶2.5 公式表格分析3…

音视频开发_获取媒体文件的详细信息

一、前言 做音视频开发过程中,经常需要获取媒体文件的详细信息。 比如:获取视频文件的总时间、帧率、尺寸、码率等等信息。 获取音频文件的的总时间、帧率、码率,声道等信息。 这篇文章贴出2个我封装好的函数,直接调用就能获取媒体信息返回,copy过去就能使用,非常方便。…