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

第六章: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&#xf…...

hibernate学习(五)

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

STM32CubeIDE 快速开发入门指南

描述 STM32CubeIDE是一体式多操作系统开发工具,是STM32Cube软件生态系统的一部分。 STM32CubeIDE是一种高级C/C开发平台,具有STM32微控制器和微处理器的外设配置、代码生成、代码编译和调试功能。它基于Eclipse/CDT™框架和用于开发的GCC工具链&#xf…...

华为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五个系统&#xff…...

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程序 选择基于对话…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求&#xff…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...