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

【数据结构】栈及其实现

目录

1.栈的概念及结构

2.栈的实现

2.1栈结构定义

2.2初始化及销毁

2.3插入数据

2.4删除数据

2.5访问栈顶数据

2.6判断是否为空栈

2.7计算栈的大小

3.8访问栈中所有数据


1.栈的概念及结构

栈:栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除操作

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

栈中的数据元素遵守后进先出LIFO(Last  In First Out)的原则

压栈:栈的插入操作叫做进栈/压栈/入栈,插入数据在栈顶

出栈:栈的删除操作叫做出栈,删除数据也在栈顶

如下图为一个栈的结构:

上图中入栈顺序为:123456789

出栈顺序为:987654321

区分数据结构中的栈和内存中的栈:

内存区域划分:堆区,栈区,静态区,常量区......

一般操作系统中的栈指的是内存中的栈,数据结构中的栈是可以插入删除数据的栈

2.栈的实现

栈的实现一般可以使用数组或者链表实现,使用数组在尾插数据时的代价比较小,所以一般使用数组实现栈

2.1栈结构定义

栈结构的定义分为静态开辟和动态开辟两种

静态开辟时栈的空间大小是固定的,所以一般情况我们使用动态开辟

动态开辟的栈结构包括三个成员变量:数组指针,可以访问栈顶的top,栈的当前容量

📖Note:

我们创建的栈结构是数组形式的,所以可以通过下标访问,top即为时刻指向栈顶的下标

top也可以看作为栈中实际元素的个数

typedef int  STDataType;
//静态开辟
#define N 100
struct Stack
{STDataType a[N];int top;
};//动态内存开辟
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

2.2初始化及销毁

初始化时对三个成员变量都要进行初始化

数组指针初始化为NULL

top = 0,同时指向栈底和栈顶,top可以看作为栈中实际元素的个数栈顶是动态变化的,每次插入数据或删除数据栈顶都会发生变化,而栈底是相对固定不变的

初始化时栈的容量为0,需要使用栈时再动态开辟空间

销毁时同样对三个结构成员分别置空或置0

//初始化
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}
//销毁
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

2.3插入数据

插入数据首先要扩容,第一次插入我们开辟4个空间(根据需求),其他情况扩容为原来的二倍

📖Note:

以下代码中realloc的第二个参数应该是newcapacity * sizeof(STDataType)而不newcapacity

使用realloc函数扩容,第二个参数的单位是字节,是我们开辟空间的总字节数

扩容失败直接退出函数即可

扩容成功才可以插入数据

数组形式的栈中数据访问通过下标访问,栈结构的特殊性使其只能在栈顶进行数据的插入和删除,而top正是时刻指向栈顶的下标,所以使数据的插入和删除更加方便

//插入数据
void StackPush(ST* ps, STDataType x)
{assert(ps);//扩容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;STDataType* tmp = realloc(ps->a, newcapacity * sizeof(STDataType));//扩容失败if (tmp == NULL){perror("realloc fail");exit(-1);}//扩容成功ps->a = tmp;ps->capacity = newcapacity;}//插入数据ps->a[ps->top] = x;ps->top++;
}

下图是将12345一次压栈后栈中的结构 

2.4删除数据

数据的删除就更加方便,只要栈非空,指向栈顶的top直接向栈底方向移动一块空间即可

//删除数据
void StackPop(ST* ps)
{assert(ps);//栈不为空才能删除assert(!StackEmpty(ps));--ps->top;
}

2.5访问栈顶数据

访问栈顶数据的前提也是栈非空

注意数组的下标与元素的对应关系,数组的下标从0开时,所以第n个元素对应下标n-1

//访问栈顶数据
STDataType StackTop(ST* ps)
{assert(ps);//栈不为空才能访问assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}

2.6判断是否为空栈

当栈中实际元素的个数为0时,栈即为空栈

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

2.7计算栈的大小

栈的大小即为栈中实际元素的个数,所以返回ps->top即可

//计算栈的大小
int StackSize(ST* ps) 
{assert(ps);return ps->top;
}

3.8访问栈中所有数据

栈中数据的访问只能从栈顶,当栈非空时,每次访问栈顶元素即可,访问栈顶的下一个元素需要栈顶元素先出栈,直至栈为空停止访问

//访问栈中数据
void StackPopAll(ST* ps)
{while (!StackEmpty(ps)){printf("%d ", StackTop(ps));StackPop(ps);}printf("\n");
}

 

相关文章:

【数据结构】栈及其实现

目录 1.栈的概念及结构 2.栈的实现 2.1栈结构定义 2.2初始化及销毁 2.3插入数据 2.4删除数据 2.5访问栈顶数据 2.6判断是否为空栈 2.7计算栈的大小 3.8访问栈中所有数据 1.栈的概念及结构 栈:栈是一种特殊的线性表,其只允许在固定的一端进行插…...

Linux命令200例:mount将文件系统挂载到指定目录下(常用)

🏆作者简介,黑夜开发者,全栈领域新星创作者✌。CSDN专家博主,阿里云社区专家博主,2023年6月csdn上海赛道top4。 🏆数年电商行业从业经验,历任核心研发工程师,项目技术负责人。 &…...

互联网摸鱼日报(2023-08-11)

互联网摸鱼日报(2023-08-11) 36氪新闻 年景不稳,市场人活成创始人 石油巨头开始疯抢锂矿,美国也开始讲“锂”了? 公司监控员工键盘 49 天,18 年老员工被解雇:因为“打字不够”? 这不是危言耸听&#xf…...

第十五章、【Linux】例行性工作调度

15.1 什么是例行性工作调度 在不考虑硬件与服务器的链接状态下,Linux可以帮助提醒许多任务。Linux调度就是通过crontab与at这两个东西。 15.1.1 Linux工作调度的种类:at,cron 从上面的说明当中,我们可以很清楚的发现两种工作调度的方式&am…...

基于Promise.resolve实现Koa请求队列中间件

本文作者为360奇舞团前端工程师 前言 最近在做一个 AIGC 项目,后端基于 Koa2 实现。其中有一个需求就是调用兄弟业务线服务端 AIGC 能力生成图片。但由于目前兄弟业务线的 AIGC 项目也是处于测试阶段,能够提供的服务器资源有限,当并发请求资源…...

【结构型设计模式】C#设计模式之桥接模式

题目:设计一个桥接模式来实现图形和颜色之间的解耦。 解析: 桥接模式是一种结构型设计模式,它将抽象部分与实现部分分离,使它们可以独立变化。在这个例子中,抽象部分是图形(如圆形、正方形)&am…...

【12】Git工具 协同工作平台使用教程 Gitee使用指南 腾讯工蜂使用指南【Gitee】【腾讯工蜂】【Git】

tips:少量的git安装和使用教程,更多讲快速使用上手Gitee和工蜂平台 一、准备工作 1、下载git Git - Downloads (git-scm.com) 找到对应操作系统,对应版本,对应的位数 下载后根据需求自己安装,然后用git --version验…...

zookeeper增加IP白名单-安全设置

简介: zookeeper未授权访问漏洞,处理这个漏洞最简单,常用的应该就是给zookeeper添加用户名、密码验证,如果项目比较急,且代码不支持zookeeper的用户名、密码验证,那采用ip白名单过滤,无疑是最快…...

Mac 调试 ios safar

1. 打开Mac的 Safari 浏览器的“开发”菜单 运行 Safari 浏览器,然后依次选取“Safari 浏览器”>“偏好设置”,点按“高级”面板,然后勾选“在菜单栏中显示开发菜单”。 2. 开启IPhone的Safari调试模式 启用 Web 检查 功能,打…...

Linu网络服务NFS

linux网络服务NFS 一.NFS简介二.NFS原理三.NFS优势四.配置文件五.NFS共享存储服务的操作步骤 一.NFS简介 NFS(网络文件服务) NFS是一种基于tcp/ip传输的网络文件系统协议,最初由sun公司开放通过使用NFS协议,客户机可以像访问本地…...

24届近5年同济大学自动化考研院校分析

今天给大家带来的是同济大学控制考研分析 满满干货~还不快快点赞收藏 一、同济大学 学校简介 同济大学历史悠久、声誉卓著,是中国最早的国立大学之一,是教育部直属并与上海市共建的全国重点大学。经过115年的发展,同济大学已经…...

多源BFS

多源 超级源点和汇点最短距离[超级汇点]昂贵的聘礼 多源BFS矩阵距离 超级源点和汇点 超级源点跟超级汇点是模拟出来的虚拟点&#xff0c;多用于图中&#xff1a; <1>同时有多个汇点和一个源点&#xff0c;建立超级汇点 1、2、3、6分别到达4或者5或者7的最短路径&#xf…...

自制电子农历

水文大师上线。今天一水电子农历牌。 首先讲讲电子配件&#xff0c;一来是电子小屏幕的选择&#xff0c;遇到文字比较多的&#xff0c;尤其是汉字&#xff0c;不要选传统那款128x64 oled&#xff0c;绝对放不下(找到最牛的超小免费字体至少要在8pixel以上才能看清楚)。我选了i…...

解决nvm安装后,node生效但npm无效

问题描述 nvm安装后&#xff0c;node生效但npm无效 清除缓存 C:\Users\cc\AppData\Roaming cc是我的用户名改成你自己的就行删除 npm和npm-cache...

Chrome DevTools 与 WebSocket 数据查看失焦的问题

Chrome DevTools 在与 WebSocket 连接交互时可能会出现失焦的问题&#xff0c;这似乎是一个已知的 bug。当 DevTools 选中 WebSocket 消息时&#xff0c;如果有新的消息到达&#xff0c;DevTools 将会自动失焦&#xff0c;导致无法查看完整的消息内容。 虽然这个问题很令人困扰…...

Javascript 正则

基本语法 定义 JavaScript种正则表达式有两种定义方式 构造函数 var regnew RegExp(<%[^%>]%>,g);字面量 var reg/<%[^%>]%>/g;g&#xff1a; global&#xff0c;全文搜索&#xff0c;默认搜索到第一个结果接停止i&#xff1a;ingore case&#xff0c;忽略…...

C语言可变数组 嵌套的可变数组,翻过了山跨过了河 又掉进了坑

可变数组 ​专栏内容&#xff1a; postgresql内核源码分析 手写数据库toadb 并发编程 个人主页&#xff1a;我的主页 座右铭&#xff1a;天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物. 概述 数组中元素是顺序存放&#xff0c;这一特性让我们…...

FFmpeg安装和使用

sudo apt install ffmpeg sudo apt-get install libavfilter-devcmakelist模板 CMakeLists.txt cmake_minimum_required(VERSION 3.16) project(ffmpeg_demo)# 设置ffmpeg依赖库及头文件所在目录&#xff0c;并存进指定变量 set(ffmpeg_libs_DIR /usr/lib/x86_64-linux-gnu) …...

HTTP代理编程:Python实用技巧与代码实例

今天我要与大家分享一些关于HTTP代理编程的实用技巧和Python代码实例。作为一名HTTP代理产品供应商&#xff0c;希望通过这篇文章&#xff0c;帮助你们掌握一些高效且实用的编程技巧&#xff0c;提高开发和使用HTTP代理产品的能力。 一、使用Python的requests库发送HTTP请求&a…...

java调用第三方接口工具类 (HttpClientUtils.java)

1. 依赖 <!--httpclient--> <dependency><groupId>commons-httpclient</groupId><artifactId>commons-httpclient</artifactId><version>3.1</version> </dependency><!-- 阿里JSON解析器 --> <dependency>…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...