当前位置: 首页 > news >正文

数据结构 --- 栈

栈 --- stack

  • 前言
  • 一、栈结构
  • 二、相关方法
    • 1.初始化
    • 2.入栈
    • 3.出栈
    • 4.判空
    • 5.获取栈顶元素
    • 6.获取栈大小
    • 7.销毁

前言

栈是一个特殊的线性表,遵循一个先进后出的特性,即操作数据(入栈,出栈)只能从栈顶操作,栈底是一个封口的结构。既然是线性表从逻辑结构上是线性的,物理结构上取决于底层实现的结构,若是顺序栈(底层为数组),则是线性的,若是链栈,则是非线性的,本次实现的栈为顺序栈,对比链栈空间更小:
在这里插入图片描述
对比上述两种栈的实现结构,进行入栈出栈操作时,两种结构的时间复杂度都为O(1),但是在进行入栈操作时,假设type是int类型,那么数组结构就只增加4个字节,而链表结构会增加8个或者12个字节,对比而得顺序栈更好,当然也不是一定不能使用链表实现。
同时本次实现栈使用C语言实现

一、栈结构

经由前文使用数组定义栈结构,有三个属性,一个指向栈的指针arr,一个标记栈顶位置和栈实际大小的top(其实也就是顺序表的size)是有效数据的下一个位置,以及一个空间容量capacity。

//定义栈结构
typedef int STDataType;   // 方便更改栈存储数据的类型
typedef struct Stack
{STDataType* arr; //指向栈的指针int top;         //栈顶位置和栈实际大小int capacity;    //空间容量
}ST;

二、相关方法

1.初始化

初始化是将栈初始化成一个空栈,即栈底层数组置为NULL,将top和capacity等于0。

//初始化
void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}

2.入栈

入栈操作四步,首先判断传递过来的参数栈是否不为空,不为空才能进行入栈操作,第二步,判断是否需要扩容,当top == capacity时进行扩容操作(两种情况,一为空栈,二为栈满),使用realloc进行扩容操作,第三步,更新数据,当扩容完成后,需要将扩容后的数组和空间大小更新回arr和capacity,最后再在top栈顶位置插入数据,top再加加;
当空间充足时直接进行最后的插入操作。

//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);   //ps不能传空//首先判断栈空间是否需要增容 --- 没有空间或者空间已满if (ps->top == ps->capacity){// 增容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* temp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (temp == NULL){perror("realloc");exit(1);}ps->arr = temp;ps->capacity = newcapacity;}//空间充足 --- top位置入栈,入栈完成top+1ps->arr[ps->top++] = x;
}

3.出栈

出栈首先需要断言传递过来的参数栈不为空,并且栈内需存在元素方可进行出栈操作,其次直接减减top栈顶位置即可。

//出栈 --- 要改变top位置 
void StackPop(ST* ps)
{//assert(ps && ps->top);assert(ps && !StackEmpty(ps));   //ps不能传空,top==0不能再出栈--ps->top;
}

4.判空

当栈为空时,返回true,不为空时返回false。

//判定栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);   //ps不能传空return ps->top == 0;
}

5.获取栈顶元素

获取栈顶元素即获取top位置的元素,并且只是读取元素而不是出栈,故top大小不会改变。

//获取栈顶元素 --- top位置不用改变
STDataType StackTop(ST* ps)
{assert(ps);   //ps不能传空return ps->arr[ps->top-1];
}

6.获取栈大小

//获取栈中有效数据个数
int StackGetSize(ST* ps)
{assert(ps);   //ps不能传空return ps->top;
}

7.销毁

销毁栈空间即将数组置为空,top和capacity等于0,也就是恢复至空栈状态,当然数组若已为NULL了,则无需置空。

//销毁
void StackDestroy(ST* ps)
{assert(ps);if (ps->arr != NULL){free(ps->arr);ps->arr = NULL;}ps->top = ps->capacity = 0;
}
http://www.lryc.cn/news/582443.html

相关文章:

  • django-ckeditor配置html5video实现视频上传与播放
  • word中的单位详解
  • 算法化资本——智能投顾技术重构金融生态的深度解析
  • 使用阿里云/腾讯云安装完成mysql使用不了
  • 分库分表之实战-sharding-JDBC广播表
  • JavaScript基础篇——第二章 类型转换与常见错误解析
  • 《UE5_C++多人TPS完整教程》学习笔记42 ——《P43 瞄准(Aiming)》
  • 250708-Svelte项目从Debian迁移到无法联网的RHEL全流程指南
  • 计算机网络:(八)网络层(中)IP层转发分组的过程与网际控制报文协议 ICMP
  • [论文阅读] 软件工程 | 自适应CPS中的人机协作与伦理
  • 自动驾驶感知系统
  • 分水岭算法:图像分割的浸水原理
  • 【王树森推荐系统】召回12:曝光过滤 Bloom Filter
  • 大数据在UI前端的应用创新:基于社交网络的用户影响力分析
  • 深度学习——神经网络1
  • 基于物联网的智能交通灯控制系统设计
  • three案例 Three.js波纹效果演示
  • 【操作系统】进程(二)内存管理、通信
  • MySQL Galera Cluster部署
  • 如何利用AI大模型对已有创意进行评估,打造杀手级的广告创意
  • 算法学习笔记:11.冒泡排序——从原理到实战,涵盖 LeetCode 与考研 408 例题
  • 【计算机网络】王道考研笔记整理(1)计算机网络体系结构
  • 高效学习之一篇搞定分布式管理系统Git !
  • 【字节跳动】数据挖掘面试题0013:怎么做男女二分类问题, 从抖音 app 提供的内容中。
  • 视频号账号矩阵运营中定制开发开源 AI 智能名片 S2B2C 商城小程序的赋能研究
  • main(int argc,char **agrv)的含义
  • 第0章:开篇词 - 嘿,别怕,AI应用开发没那么神!
  • Nat.C|RiNALMo:通用 RNA 语言模型新突破,3600 万序列预训练,跨家族结构预测、剪接识别与功能注释全能泛化
  • 【Note】《Kafka: The Definitive Guide》 第8章: Cross-Cluster Data Mirroring
  • 安卓10.0系统修改定制化____如何修改ROM 实现开机自动开启开发者选项与隐藏开发者选项