【数据结构】—— 栈

  • 一、栈的基本概念
    • 1、栈的定义
    • 2、栈的常见基本操作
  • 二、栈的顺序存储
    • 1、栈的顺序存储结构
    • 2、顺序栈存储实现
      • (1)初始化
      • (2)判空
      • (3)进栈
      • (4)出栈
      • (5)取栈顶元素
      • (6)获取元素个数
      • (7)销毁
  • 三、栈的链式存储
    • 1、栈的链式存储结构
    • 2、链式栈存储实现
      • (1)初始化
      • (2)判空
      • (3)进栈
      • (4)出栈
      • (5)取栈顶元素
      • (6) 获取元素个数
      • (7)销毁
  • 四、性能分析

一、栈的基本概念

1、栈的定义

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

  • 进栈:栈的插入操作叫左进栈/压栈/入栈,入数据在栈顶
  • 出栈:栈的删除操作叫做出栈。出数据也在栈顶
  • 栈顶(Top):线性表允许进行插入删除的那一端。
  • 栈底(Bottom):固定的,不允许进行插入和删除的另一端。
  • 空栈:不含任何元素的空表。

在这里插入图片描述

2、栈的常见基本操作

void STInit(ST* ps);//初始化一个空栈S。
void STDestroy(ST* ps);//栈销毁,释放其占用的存储空间//从栈顶操作
void STPush(ST* ps, STDateType x);//进栈(栈的插入操作),若栈未满,插入使x成为新栈顶
void STPop(ST* ps);//出栈(栈的删除操作),若栈非空,弹出栈顶元素
STDateType STTop(ST* ps);//返回栈顶元素
int STSize(ST* ps);//返回栈中有效元素个数(top记录有效个数)bool STEmpty(ST* ps);//判断栈是否为空(top是否指向0)

栈主要有两种存储方式来实现:一是顺序存储结构(数组),二是链式存储结构(链表)

二、栈的顺序存储

栈的顺序存储结构通常由数组和一个记录栈顶元素的下一个位置的变量(下一个入栈的数据插入的位置)组成,但是当数组空间大小不够时还需要扩容,所以还要存储栈的空间大小的变量。
可以参考我写的另一篇博客理解——顺序表
在这里插入图片描述

1、栈的顺序存储结构

采用顺序(数组)存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶元素的位置,一个整形(capacity)用于扩容,实现动态栈。

typedef int STDateType;//STDateType的类型根据实际情况而定
typedef struct Stack
{STDateType* a;int top;//指向栈顶下一个位置的指针->方便进栈/出栈/判空等操作int capacity;//空间大小->用于动态扩容
}ST;

2、顺序栈存储实现

(1)初始化

用一级指针接收栈的地址,将栈的存储空间(即a这个动态分配内存的数组)置为NULL,表示当前没有分配任何内存,将top和capacity置为0来表示栈的起始状态(无元素插入和无内存分配)。

void STInit(ST* ps)
{assert(ps);//断言,确保传入的指针 ps 不为空,以避免对无效指针的操作ps->a = NULL;ps->top = 0;//指向栈顶元素下一个位置ps->capacity = 0;
}

(2)判空

判断头指针的下一个位置是否指向0即可,如果指向0说明栈为空(无元素插入),否则说什么栈不为空(已有元素插入)

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;//为真返回1,说明栈为空,否则返回0,说明栈不为空
}

(3)进栈

  • 判断是否需要扩容:如果栈中有效元素(top指向的位置)和栈空间大小相同(ps->top == ps->capacity),则需要扩容,否则无需扩容。
    扩容:使用三目运算符,如果capactiy是0则置空间大小为4,否则空间大小翻倍。随后使用realloc动态内存分配出新空间给临时数组tmp,最后更新a数组和空间。
  • 将x元素放入a数组,有效元素加1。
void STPush(ST* ps, STDateType x)
{assert(ps);//满了,扩容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDateType* tmp = (STDateType*)realloc(ps->a, newcapacity * sizeof(STDateType));//STDateType* tmp = ps;if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity = newcapacity;}//top始终指向栈顶元素//动态内存分配:包含 N 个 STDateType 类型元素的内存块,可以像数组一样使用。ps->a[ps->top] = x;ps->top++;
}

注意:当ps->a为NULL,realloc和malloc作用相同。

  • realloc(ptr, size):用于调整 ptr 指向的内存块的大小为 size。如果 ptr 是非空的,它会尝试在原有内存块上重新分配内存。如果 ptr 为空,realloc() 就相当于 malloc(size),即分配一个新的内存块。
  • malloc(size):用于分配一个大小为 size 的内存块,并返回指向这块内存的指针。

(4)出栈

  • 判断栈是否为空:如果为空无法出栈
  • top指针-1
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));//调用前面的判空操作ps->top--;
}

(5)取栈顶元素

  • 判断栈是否为空:如果为空无法取栈顶元素
  • 返回栈顶元素 (top-1 即为栈顶元素的位置)
STDateType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

(6)获取元素个数

top的下标即为栈中有效元素的个数,直接返回即可

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

(7)销毁

释放栈占用的存储空间,置栈顶指针top和栈的空间大小置为0即可。

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

三、栈的链式存储

链式存储的栈称为链栈,通常采用单链表实现。由于栈是链式存储,每次插入时需要申请一个新节点,因此我们定义一个结构体存放指向头节点的指针和记录有效元素个数的整形size。再定义一个结构体存放节点的数据和指向下一个节点的指针
链表具体实现过程可以参考这篇博客——单链表
在这里插入图片描述

1、栈的链式存储结构

定义两个结构体

  • StackNode :存放节点的数据STDataType data; + 存放当前节点的下一个节点struct StackNode* next;
  • ST:保存栈顶元素StackNode* top;+ 记录有效数据个数int size;
typedef int STDataType;//STDateType的类型根据实际情况而定
typedef struct StackNode {STDataType data;//当前节点的数据struct StackNode* next;//当前节点的下一个节点的指针
}StackNode;
typedef struct Stack {StackNode* top;//栈顶int size;//有效数据的个数
}ST;

2、链式栈存储实现

(1)初始化

用一级指针接收ST结构体的地址,对ST结构体中保存的头结点悬空(NULL),有效元素个数初始化为0即可

void STInit(ST* ps)
{assert(ps);//ps!=NULLps->top = NULL;ps->size = 0;
}

(2)判空

用一级指针接收ST结构体的地址,判断ST结构体中保存的头节点是否为NULL即可

bool StackEmpty(ST* ps)
{assert(ps);//ps!=NULLreturn ps->top == NULL;
}

(3)进栈

判断栈是否为空,如果为空直接将数据给头节点即可,否则需要修改指针连接并更新头节点

void StackPush(ST* ps, STDataType x)
{assert(ps);//申请一个新节点StackNode* newnode = (StackNode*)malloc(sizeof(StackNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;if (StackEmpty(ps)){//如果栈为空,将新节点newnode赋给栈顶ps->top = newnode;ps->top->next = NULL;}else{//如果栈不为空,更新栈顶指针并修改指针连接newnode->next = ps->top;ps->top = newnode;}//有效数据+1ps->size++;
}

(4)出栈

  • 判空:出栈需要栈中有元素,因此第一步断言判空assert(!StackEmpty(ps));
  • 处理头节点的元素:如果栈中只有一个头节点,那么直接销毁栈顶free(ps->top); ps->top = NULL;否则修改头节点指针指向,定义del存放要被删的头节点,更新头节点为下一个节点ps->top = ps->top->next,释放del指向的空间(要被删除节点的空间)并置空free(del); del = NULL;
  • 元素个数减1ps->size--;
void StackPop(ST* ps)
{assert(ps);//ps!=NULLassert(!StackEmpty(ps));//栈不能为空if (ps->size == 1 || ps->top->next == NULL){//如果栈中只有一个数据,直接销毁栈顶即可free(ps->top);ps->top = NULL;}else{//如果栈的数据个数大于1,先改变栈顶指针指向,再销毁栈顶空间即可StackNode* del = ps->top;ps->top = ps->top->next;free(del);//释放空间del = NULL;//指向空}//每次出栈有效数据减一ps->size--;
}

(5)取栈顶元素

断言非空后返回top指向的元素数据

STDataType StackTop(ST* ps)
{assert(ps);//ps!=NULLassert(!StackEmpty(ps));//栈不能为空return ps->top->data;
}

(6) 获取元素个数

直接返回ST结构体中的size即可

int STSize(ST* ps)
{assert(ps);//ps!=NULLreturn ps->size;
}

(7)销毁

链式栈的销毁和顺序栈的销毁不一样,链式栈的销毁需要遍历节点一一删除(和单链表的删除操作一样)

void STDestory(ST* ps)
{assert(ps);//ps!=NULLassert(!StackEmpty(ps));//栈不能为空while (!StackEmpty(ps)){StackPop(ps);}
}

四、性能分析

时间复杂度:顺序栈和链式栈在插入、删除和访问栈顶元素等操作上的时间复杂度都是O(1)。这意味着它们在这些基本操作上的性能是相似的。
空间复杂度

顺序栈
顺序栈的空间复杂度是O(n),其中n是栈中元素的数量。这是因为顺序栈使用数组来存储元素,而数组的大小确定。尽管数组中可能有一部分空间未被使用(特别是当栈未满时),但整个数组的空间都被分配给了顺序栈。如果栈的容量不足,还需要进行扩容操作,这可能会进一步增加空间复杂度。

链式栈
链式栈的空间复杂度也是O(n),但这里的n指的是栈中实际元素的数量,而不是预先分配的空间大小。链式栈通过动态地创建和删除节点来管理内存,因此它不会浪费未使用的空间。然而,每个节点除了存储数据外,还需要额外的空间来存储指向下一个节点的指针,这增加了每个节点的空间开销。但从整体上看,链式栈的空间复杂度仍然是线性的,因为它只与栈中元素的数量有关。

总结:如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用 CSS 打印样式为 Web 页面设置专业的打印机效果

对于有打印需求的网页,特别是文章的详情页,需要设置专门的打印样式来适配页面。CSS 打印样式允许你为网页设置专门用于打印的样式。文本就是专门介绍如何使用 CSS 打印样式为 Web 页面设置专业的打印机效果。 media print 通过使用 media print 媒体查…

算法打卡 Day19(二叉树)-平衡二叉树 + 二叉树的所有路径 + 左叶子之和 + 完全二叉树的节点个数

Leetcode 101-平衡二叉树 文章目录 Leetcode 101-平衡二叉树题目描述解题思路 Leetcode 257-二叉树的所有路径题目描述解题思路 Leetcode 404-左叶子之和题目描述解题思路 Leetcode 222-完全二叉树的节点个数题目描述解题思路 题目描述 https://leetcode.cn/problems/balanced…

Chainlit快速实现AI对话应用将聊天数据的持久化到postgres关系数据库中

概述 默认情况下,Chainlit 应用不会保留其生成的聊天和元素。即网页一刷新,所有的聊天记录,页面上的所有聊天记录都会消失。但是,存储和利用这些数据的能力可能是您的项目或组织的重要组成部分。 之前写过一篇文章《Chainlit快速…

实现高亮的全文分页检索

文章目录 🌞 Sun Frame:SpringBoot 的轻量级开发框架(个人开源项目推荐)🌟 亮点功能📦 spring cloud模块概览常用工具 🔗 更多信息1.sun-club-infra 模块SubjectEsServiceImpl.java1.querySubje…

大数据-74 Kafka 高级特性 稳定性 - 控制器、可靠性 副本复制、失效副本、副本滞后 多图一篇详解

点一下关注吧!!!非常感谢!!持续更新!!! 目前已经更新到了: Hadoop(已更完)HDFS(已更完)MapReduce(已更完&am…

【Linux】Linux环境基础开发工具使用之软件包管理(yum)与 Linux编辑器(vim)

目录 一、Linux 软件包管理器 yum1.1 什么是软件包1.2 关于 rzsz1.3 查看软件包1.4 如何安装软件1.5 如何卸载软件1.6 如何更新软件包1.7 yum源更新 二、 Linux编辑器-vim使用2.1 vim的基本概念2.2 vim的基本操作2.3 vim命令模式命令集2.3.1 从命令模式切换为插入模式2.3.2 从插…

03创建型设计模式——抽象工厂模式

一、抽象工厂模式简介 抽象工厂模式是所有形态的工厂模式中最为抽象和具有一般性的。抽象工厂模式可以向客户端提供一个接口,使得客户端在不必指定产品的具体类型的情况下,能够创建多个产品族的产品对象。例如现实生活中,水果的种类繁多&…

Vue3+Ts项目中经常遇到导入组件,vscode报无法找到模块xxx,xxx隐式拥有 “any“ 类型解决办法~

1、报错截图: 2、解决办法:在确保路径正确的情况下,你会在 src 目录下找到一个名为 env.d.ts 的文件(或者类似的名称)。在这个文件中,你可以声明 .vue 文件的模块类型。例如:(这告诉 TypeScript…

系统内存管理:虚拟内存、内存分段与分页、页表缓存TLB以及Linux内存管理

虚拟内存 虚拟内存是一种操作系统提供的机制,用于将每个进程分配的独立的虚拟地址空间映射到实际的物理内存地址空间上。通过使用虚拟内存,操作系统可以有效地解决多个应用程序直接操作物理内存可能引发的冲突问题。 在使用虚拟内存的情况下&#xff0…

IDEA打开持久层的代码很卡,关掉mybatis-plus的插件

不知道大家有没有遇到过打开 mapper 层的页面,然后要切换另外 java 文件的时候很卡,我遇到过卡了好几分钟的,那种继承了 mybatis-plus 的 mapper java文件或者 xml 文件都会,我后来把 mybatis 的插件关掉了,就不会了

LVS的12种调度算法详解

1.lvs调度算法类型 1.1静态方法 仅根据算法本身进行调度,不考虑RS的负载情况 1.2动态方法 主要根据每RS当前的负载状态及调度算法进行调度Overheadvalue较小的RS将被调度 1.1lvs静态调度算法 1.1.1RR(轮询算法): roundrobin 轮…

Haproxy状态页

HAProxy 的状态页是一个非常有用的监控和诊断工具,它提供了关于 HAProxy 服务器运行状态的详细信息,通过web界面,显示当前HAProxy的运行状态。 状态页通常包含以下关键信息: 前端(Frontend)和后端&#x…

从TiDB迁移到OceanBase的实践分享

本文来自OceanBase热心用户的分享 近期,我们计划将业务数据库从TiDB迁移到OceanBase,但面临的一个主要挑战是如何更平滑的完成这一迁移过程。经过研究,了解到OceanBase提供的OMS数据迁移工具能够支持从TiDB到OceanBase的迁移,并且…

js构造函数的prototype赋值总结

我们知道通过构造函数的prototype,可以生成让所有实例对象访问的通用属性和方法,下面通过代码来解释这个过程 function Person(name){this.name name; }Person.prototype.sex man我们定义了一个构造函数Person,然后给它的prototype添加了一个sex的属性,下面我们来看看Person…

OSPF进阶

一、LSA详解 Type:LSA的类型(1、2、3、4、5、7类) link-state-ID:链路状态表示符 ADV router:产生该LSA的路由器 age:老化时间 Metric:开销值,一般都为ADV router到达该路由的开…

人工智能,代跑通,预测模型,模型优化

人工智能,代跑通,预测模型,模型优化,增加模块,文章复现,python代做,预测,微调,融合,深度学习,机器学习程序代写,环境调试,…

STM32-门电路-储存器-寄存器-STM32f1-MCU-GPIO-总线-keil5-点led-寄存器编程

1、门电路 门电路组成简单加法器: 二进制对电路的影响: 0和1代表无和有; 以下图例,演示与门:左1右1输出1; 电平标准:使用不同的电压表示数字0和1; 高电平:1&#xff1…

攻防世界-web-ctf-upload

题目场景 查看源码 毫无有效的数据 官方WriteUp 本题需要利用文件上传漏洞点,通过绕过服务器的安全防护,达到getshell的目的 本题的主要考点为利用fastcgi的.user.ini特性进行任意命令执行 这里需要绕过的点如下 检查文件内容是否有php字符串 检查…

haproxy七层代理

目录 一、haproxy简介 二、haproxy实验 1.环境部署 2.haproxy的基本部署方法及负载均衡的实现 2.1安装软件 2.2haproxy的基本配置 3.haproxy的全局配置参数及日志分离 3.1多线程设定 3.2自定义日志 4.haproxy-proxies中的常用配置参数 4.1设置backup --- sorryserver…

卷积神经网络(李宏毅老师系列)

自学参考: 一文搞懂卷积神经网络(CNN)的原理 视频课 课件资料 笔记 一、引入 cnn设计灵感来自于生物学中的视觉系统,旨在模拟人类视觉处理的方式。常用场景:image classification 基本步骤: 把所有图片都先…