【数据结构】栈的实现

🚩纸上得来终觉浅, 绝知此事要躬行。
🌟主页:June-Frost
🚀专栏:数据结构

🔥该文章主要了解实现栈的相关操作。

目录:

  • 🌍 栈的概念
  • 🌎栈的实现
    • ✉️ 初始化栈 和 销毁栈
    • ✉️ 入栈
    • ✉️ 出栈
    • ✉️ 获取栈顶元素
    • ✉️ 获取栈中有效元素个数
    • ✉️ 判空
    • ✉️ 接口测试
  • ❤️ 结语

🌍 栈的概念

 栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素——压栈和出栈都是在栈顶。

🌎栈的实现

 栈的实现一般可以使用数组或者链表实现,如果使用数组,以尾部为栈顶,压栈和出栈的时间消耗都为O(1),唯一的缺陷就是需要扩容。如果考虑单链表,若以尾节点为栈顶,那么时间复杂度为O(N),如果以头节点为栈顶,时间复杂度就是O(1)。相较于链表,数组结构的缓存利用率较高,相对而言更优一些。这里采用数组结构实现。
  结构体:

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity; // 记录容量int top;//栈顶
}ST;

✉️ 初始化栈 和 销毁栈

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

 这里将top初始化为0,意味着top标记的是栈顶元素的下一个元素。top如果初始化为-1,那么标记的就是栈顶元素,初始化的不同,后续相关操作的实现方式也是不同的。

✉️ 入栈

void STPush(ST* ps, STDataType x)
{assert(ps);//扩容if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4: ps->capacity * 2;//如果 ps->a 为NULL,realloc的功能和malloc一样 STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top] = x;ps->top++;
}

✉️ 出栈

void STPop(ST* ps)
{assert(ps->top > 0 && ps);ps->top--;
}

✉️ 获取栈顶元素

STDataType STTop(ST* ps)
{assert(ps->top > 0 && ps);return ps->arr[ps->top-1];
}

✉️ 获取栈中有效元素个数

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

✉️ 判空

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

✉️ 接口测试

 这样的逻辑就可以实现栈的特性。

void test()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);STPush(&st, 6);STPush(&st, 7);STPush(&st, 8);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}STDestroy(&st);
}

❤️ 结语

 文章到这里就结束了,如果对你有帮助,你的点赞将会是我的最大动力,如果大家有什么问题或者不同的见解,欢迎大家的留言~

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

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

相关文章

Linux-centos系统安装MySql5.7

1.配置yum仓库 1.1配置yum仓库 rpm --import https://repo.mysql.com/RPM-GPG-KEY-mysql-2022 1.2 安装Mysql yum库 rpm -Uvh http://repo.mysql.com//mysql57-community-release-el7-7.noarch.rpm 2.使用yum安装Msql 说明:下载大约5分钟左右 yum -y install mysq…

【赠书活动】Excel透视表的简单应用

👉博__主👈:米码收割机 👉技__能👈:C/Python语言 👉公众号👈:测试开发自动化【获取源码商业合作】 👉荣__誉👈:阿里云博客专家博主、5…

如何优雅构建自定义 Spring Boot 验证器,让你的代码更加丝滑!

作为一名开发人员,你应该知道确保应用程序中流动的数据的准确性和完整性是多么重要。Spring Boot提供了强大的验证功能,但有时我们需要额外的验证,创建适合特定需求的自定义验证器。 接下来,我们来介绍下如何完整的创建一个自定义…

日期相关工具类

日期相关工具类 【一】介绍【1】SimpleDateFormat 为什么是线程不安全【2】解决 SimpleDateFormat 线程不安全的方法 【二】LocalDate API【三】LocalTime API【四】LocalDateTime API【五】转换关系【1】LocalDateTime 与 LocalDate 之间的转换【2】LocalDateTime 与 Date 之间…

账户和组管理

1. 账户和工作组的分类 1.1. 用户分为三类: 超级账户——账户名为root,它具有一切权限,只有进行系统维护(例如:建立用户等)或其他必要情形下才 用超级用户登录,以避免系统出现安全问题。 系统账户——是Linux系统正常…

软件工程与计算总结(四)项目管理基础

目录 一.项目和项目管理 二.团队组织与管理 三.软件质量保障 四.软件配置管理 五.项目实践 一.项目和项目管理 1.软件开发远不是纯粹的编程,随着软件规模的增长,软件开发活动也变得越来越复杂~ 2.软件项目就是要将所有的软件开发活动组织起来&#…

简单聊一聊公平锁和非公平锁,parallel并行流

目录 一、降低锁的粒度,将synchronized关键字不放在方法上了,改为synchronized代码块。二、先区分一下公平锁和非公平锁1、公平锁2、非公平锁3、公平锁的优缺点:4、非公平锁的优缺点: 三、是否对症下药四、IntStream.rangeClosed是…

【问题解决】报错:unable to execute ‘swig‘: No such file or directory

在编译uboot代码时, make -f rockpi4.mk u-boot -j4 报了以下错误。 HOSTCC scripts/dtc/dtc.oSHIPPED scripts/dtc/pylibfdt/libfdt.iENVT include/generated/environment.hPYMOD rebuildHOSTCC scripts/dtc/flattree.oUPD include/generated/version_…

【手绘 | 日漫风】从临摹开始控笔,线条,再到人体

博主:_LJaXi 专栏: Unity | 横版游戏开发 手绘入门 控笔 排线起稿方式九宫格起稿五官起稿专业起稿 握笔姿势三角握持姿势拇指指握姿势 勾线建议注意对于人体 控笔 排线 在绘画过程中,可以使用铅笔控制笔触的方向、压力和角度,以获…

力扣 -- 446. 等差数列划分 II - 子序列

解题步骤&#xff1a; 参考代码&#xff1a; class Solution { public:int numberOfArithmeticSlices(vector<int>& nums) {int nnums.size();//把元素和它对应的所有下标绑定存放到哈希表中unordered_map<double,vector<int>> hash;for(int i0;i<n;…

picodet onnx转其它芯片支持格式时遇到

文章目录 报错信息解决方法两模型精度对比 报错信息 报错信息为&#xff1a; Upsample(resize) Resize_0 not support attribute coordinate_transformation_mode:half_pixel. 解决方法 整个模型转换过程是&#xff1a;paddle 动态模型转成静态&#xff0c;再用paddle2onnx…

网站安全维护:守护您的数字领土

在这个数字时代&#xff0c;网站已成为企业和个人展示自己的重要平台。然而&#xff0c;随着互联网的高速发展&#xff0c;网站安全问题也日益严峻。黑客和入侵软件等威胁不断涌现&#xff0c;因此&#xff0c;保护网站免受这些威胁的影响变得至关重要。本文将探讨网站安全维护…

字符串常量池位于JVM哪里

Java6 和6之前&#xff0c;常量池是存放在方法区&#xff08;永久代&#xff09;中的。Java7&#xff0c;将常量池是存放到了堆中。Java8 之后&#xff0c;取消了整个永久代区域&#xff0c;取而代之的是元空间。运行时常量池和静态常量池存放在元空间中&#xff0c;而字符串常…

【软件测试】功能测试/接口测试/自动化测试/性能测试/验收测试

软件测试的主要流程 一、测试主要的四个阶段 1.测试计划设计阶段&#xff1a;产品立项之后&#xff0c;进行需求分析&#xff0c;需求评审&#xff0c;业务需求评级&#xff0c;绘制业务流程图。确定测试负责人&#xff0c;开始制定测试计划&#xff1b; 2.测试准备阶段&…

【STM32单片机】多功能电子密码锁设计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用STM32F103C8T6单片机控制器&#xff0c;使用按键、IIC OLED模块、DS18B20温度传感器、SG90舵机、红外遥控、矩阵按键、EEPROM等。 主要功能&#xff1a; 系统运行后&#xff0c;OLED显示RTC日期…

【C++面向对象侯捷下】21. 关于New, Delete

文章目录 底层 是 调用 malloc函数 class 可以 重载这些 函数&#xff08;可以重载 构造&#xff0c;析构函数&#xff1f;&#xff09;

CCF CSP认证 历年题目自练Day24

题目一 试题编号&#xff1a; 202009-1 试题名称&#xff1a; 称检测点查询 时间限制&#xff1a; 1.0s 内存限制&#xff1a; 256.0MB 问题描述&#xff1a; 题目背景 2020 年 6 月 8 日&#xff0c;国务院联防联控机制发布《关于加快推进新冠病毒核酸检测的实施意见》&…

速通Redis基础(一):掌握Redis的字符串类型和命令

目录 字符串&#xff08;String&#xff09; 常见命令 SET GET MSET&MGET SETNX INCR INCRBY DECR DECRBY INCRBYFLOAT APPEND GETRANGE SETRANGE STRLEN Redis字符串类型命令总结 Redis&#xff08;Remote Dictionary Server&#xff09;是一个高性能的…

【14】c++设计模式——>工厂模式

简单工厂模式的弊端 简单工厂模式虽然简单&#xff0c;但是违反了设计模式中的开放封闭原则&#xff0c;即工厂类在数据增加时需要被修改&#xff0c;而我们在设计时对于已经设计好的类需要避免修改的操作&#xff0c;而选用扩展的方式。 工厂模式设计 简单工厂模式只有一个…

河北吉力宝:国内顶尖资源荣誉共筑全景融合新商业生态

随着科技的不断发展和社会的进步&#xff0c;新兴企业纷纷崭露头角&#xff0c;展现出令人瞩目的商业潜力。随着科技的不断演进和社会的持续进步&#xff0c;新兴企业正崭露头角&#xff0c;显露出巨大的商机。在这个时代&#xff0c;合作和资源整合变得至关重要。河北吉力宝智…