第六章:C语言数据结构与算法初阶之栈
系列文章目录
文章目录
- 系列文章目录
- 前言
- 一、栈
- 二、栈的实现
- 三、接口函数的实现
- 1、初始化
- 2、销毁栈
- 3、压栈与出栈
- 4、判空
- 5、元素个数
- 6、返回栈顶元素
- 四、栈中元素的访问
- 总结
前言
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。
一、栈
栈的结构如上图所示:像一个桶,元素是在竖直放入的。
栈只允许在固定的一端进行插入和删除元素操作,进行数据插入和删除操作的一端称为栈顶,另一端称为栈底,即元素遵循后进先出的原则,但注意这个是相对于栈内的元素。
二、栈的实现
我们可以用数组或链表的结构来实现栈,但栈这种数据结构是不存在随即插入这种方式的,因为它只能尾插。
我们以链表的方式来模拟的时候,我们需要不断地找尾,这个过程的时间复杂度是O(N)。所以我们是用数组可以更好的来实现栈的结构。
typedef struct Stack
{STDataType* a;int capacity;int top;
}ST;
三、接口函数的实现
1、初始化
void StackInit(ST* ps)
{assert(ps);ps->capacity = 4;ps->a = (STDataType*)malloc(sizeof(STDataType)*(ps->capacity));assert(ps->a);ps->top = 0;//栈顶元素的下一位置下标 top = 0/ 栈顶元素 top = -1
}
默认开辟四个元素大小空间,将top设为0,capacity设置为4。
2、销毁栈
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;}
3、压栈与出栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//扩容if (ps->top == ps->capacity){ps->a = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);ps->capacity *= 2;assert(ps->a);}ps->a[ps->top] = x;ps->top++;
}
void StackPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}
压栈是尾部插入元素,所以要注意可能要扩容。
当一个栈为空的时候,恰好就是top为0的时候。
4、判空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
当一个栈为空的时候,恰好就是top为0的时候,因此,我们可以通过top来判断栈是否为空。
5、元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
6、返回栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}
四、栈中元素的访问
栈是无法像顺序表和链表那样不断地遍历元素的。因为,想要遍历元素必须取出栈顶元素,也就是说,我们必须删除栈顶的元素才能访问到下一个元素。因此,栈只能遍历一次,遍历一次之后就代表着栈已经空了。
总结
栈的特点就是后进先出。
任何问题都有解决的办法,无法可想的事是没有的。——爱迪生
相关文章:

第六章:C语言数据结构与算法初阶之栈
系列文章目录 文章目录系列文章目录前言一、栈二、栈的实现三、接口函数的实现1、初始化2、销毁栈3、压栈与出栈4、判空5、元素个数6、返回栈顶元素四、栈中元素的访问总结前言 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 一、…...
Android学习之WebView
什么是WebView WebView是Android中UI组件的一种,WebView基于webkit内核,不过由于兼容性的原因在Android5.0后改为了Chromium内核。 WebView可以用来展示网页,常用于我们不想打开浏览器但又想浏览网页的情况。 WebView的使用 WebVeiw的常用…...
3/11 考试总结
时间安排 7:30–7:50 读题,T1 是个利用随机性的题目,T2 dp,T3 不知道是啥。 7:50–8:30 T1,对于随机有个结论时最值突变不超过 log ,于是可以处理出所有 log 个区间然后统计答案,但这暴力做是个 3log 铁定过不去。 8:30–8:50 T2…...

Leetcode 141.环形链表 142环形链表II
141环形链表 文章目录快慢指针快慢指针 代码思路: slow 和fast 指向 head slow走一步,fast走两步 没有环: fast每次走2步 ,如果 fast 最终遇到NULL(链表中的元素是 偶数)或者fast->next(链表中的元素是 奇数)遇到NULL…...

hibernate学习(五)
hibernate学习(五) hibernate的一对多关联映射: 一、数据库表与表之间关系 一对多建表原则: 多对多的建表原则: 一对一建表原则: (1)唯一外键对应: (…...

STM32CubeIDE 快速开发入门指南
描述 STM32CubeIDE是一体式多操作系统开发工具,是STM32Cube软件生态系统的一部分。 STM32CubeIDE是一种高级C/C开发平台,具有STM32微控制器和微处理器的外设配置、代码生成、代码编译和调试功能。它基于Eclipse/CDT™框架和用于开发的GCC工具链…...
华为OD机试 - 火星文计算(C 语言解题)【独家】
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 使用说明本期题目:火星文计…...

超超超超保姆式详解——字符函数和字符串函数(学不会打我)上
目录 长度不受限制的字符串函数 strlen部分 strlen函数的易错小知识 strlen函数的实现 strcpy部分 strcat部分 自己实现strcat strstr函数部分 简单例子: 分析 strcmp部分 长度受限制的字符串函数 strncpy 简单例子 strncat strncmp 简单例子 &…...
Data mesh 笔记
有用的网站 https://www.datamesh-architecture.com/ https://www.agilelab.it/data-mesh-in-action https://learn.microsoft.com/en-us/azure/cloud-adoption-framework/scenarios/cloud-scale-analytics/well-architected-framework https://www.datamesh-architecture.com…...
(八十三)大白话透彻研究通过explain命令得到的SQL执行计划(2)
今天我们就一步一步的来讲解不同的SQL语句的执行计划长什么样子,先来看第一条SQL语句,特别的简单,就是: explain select * from t1 就这么一个简单的SQL语句,那么假设他这个里面有大概几千条数据,此时执行计…...

案例18-面向对象之开门小例子
目录 一:背景介绍 二:思路&方案 1.面向过程 2.面向对象 3.面向对象(反射) 三:过程 1.面向过程:原本何老师的作用交给我了米老师来完成。 2.面向对象:把开门的方法完全交个何老师,米老师不需要有…...

【碎片化知识总结】三月第一周
目录 前言 1、开发中常用的 IDEA 编辑器,如何做到不用每次都重新配置? 2、如何使用 Python 获取视频文件信息? 3、使用 Java 的 try-with-resources 优化代码 4、使用 shell 脚本批量修改服务器某一目录下的文件后缀名称 5、MySQL优化&…...
从零开始的JSON库(1):启程
1. JSON 是什么 JSON(JavaScript Object Notation)是一个用于数据交换的文本格式,现时的标准为ECMA-404 。 虽然 JSON 源自于 JavaScript 语言,但它只是一种数据格式,可用于任何编程语言。现时具有类似功能的格式有X…...

【Java】数组
目录 1.数组的定义与初始化 2.遍历数组 3.认识null 4.引用变量 5.返回多个值 6.数组拷贝 7.数组逆序 8.数组填充 9.小练习 //将整形数组转化为字符串 //二分查找优化 //冒泡排序优化 10.二维数组 //遍历二维数组 //不规则的二维数组 1.数组的定义与初始化 int…...

【C++】非类型的模板参数,特化
目录 1.类型模板参数和非类型模板参数 2.特化 3. 模板的分离编译 4.模板的优缺点 1.类型模板参数和非类型模板参数 之前写模板传的都是类型——类型模板参数 现在想定义两个静态数组,数组长度不同,就可以用模板参数传数值而不是传类型 非类型模板…...

核方法(kernel Method)
核方法 核方法定义 一种能够将在原始数据空间中的非线性数据映射到高维线性可分的方法。 核方法的用处 1、低维数据非线性,当其映射到高维空间(feature space)时,可以用线性方法对数据进行处理。 2、线性学习器相对于非线性学…...

消息队列MQ用来做什么的,市场上主流的四大MQ如何选择?RabbitMQ带你HelloWorld!
文章目录MQ用来做什么的MQ会有什么样的麻烦MQ消息队列模式分类MQ消息队列常用协议市场主流四大MQRabbitMQ项目开发RabbitMQ中的组成部分MQ用来做什么的 省流 :系统解耦、异步调用、流量削峰 系统解耦 首先举例下面这个场景,现有ABCDE五个系统ÿ…...

2023年中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛(同步赛) A — E
2023年中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛(同步赛) 文章目录A -- A Xor B Problem题目分析codeB -- 吃苹果题目分析codeC -- n皇后问题题目分析codeD -- 分苹果题目分析codeE -- 完型填空题目分析codeA – A…...

一文分析Linux v4l2框架
说明: Kernel版本:4.14 ARM64处理器,Contex-A53,双核 使用工具:Source Insight 3.5, Visio 1. 概述 V4L2(Video for Linux 2):Linux内核中关于视频设备驱动的框架,对上向应用层提供…...

MFC常用控件使用(文本框、编辑框、下拉框、列表控件、树控件)
简介 本文章主要介绍下MFC常用控件的使用,包括静态文本框(Static Text)、编辑框(Edit Control)、下拉框(Combo Box)、列表控件(List Control)、树控件(Tree Control)的使用。 创建项目 我们选择 文件->新建->新建项目,选择MFC程序 选择基于对话…...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...

MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...

三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...