数据结构线性表——栈
前言:哈喽小伙伴们,今天我们将一起进入数据结构线性表的第四篇章——栈的讲解,栈还是比较简单的哦,跟紧博主的思路,不要掉队哦。
目录
一.什么是栈
二.如何实现栈
三.栈的实现
栈的初始化
四.栈的操作
1.数据入栈
2.数据出栈
3.返回栈顶数据
4.判断空栈
5.销毁栈
6.测试栈
五.完整代码展示
1.Stack.h
2.Stack.c
3.test.c
六.总结
一.什么是栈
栈,其实是一种特殊的线性表,他只允许在线性表固定的一端进行插入和删除元素的操作。
进行插入和删除的一端称为栈顶,另一端则称为栈底。
栈中的元素遵循后进先出的原则。
其中有两个对栈中元素进行操作的专业名词:
- 压栈:栈的插入操作,也可以叫入栈或进栈,入数据在栈顶。
- 出栈:栈的删除操作叫做出栈,出数据也在栈顶。

二.如何实现栈
经过我们前边的学习,我们已经掌握了数据结构实现的两种方式,数组和链表。
那么对于栈,我们是用数组,还是用链表呢???不妨来分析一下:
关于栈的操作,主要是要方便栈顶的操作。
如果是数组栈:

数组可以直接通过下标来实现访问,方便快捷。
如果是单链表栈:

如果追求高效,就需要让单链表的头作为栈顶,因为单链表的尾部操作比较复杂。
如果是双链表栈,那么无论头尾都可。但是双链表的设计更加麻烦,空间占用也更大。
综合全局因素考虑,用数组实现栈是最合适的。
三.栈的实现
栈的初始化
//初始化
void StackInit(ST* pst)
{assert(pst);pst->data = NULL;pst->capacity = 0;pst->top = -1;
}
栈的初始化和顺序表一样,但是不同于顺序表的是,栈需要一个top,表示栈顶的当前位置,方便对栈顶数据的操作。
值得注意的是,栈是以数组为基础的,而数组的下标是从0开始的,所以我们如果想让top指向当前栈顶的位置,就要初始化为-1,这样每输入一个数据,top++,就可以完全等同于数组下标啦。
四.栈的操作
1.数据入栈
数据入栈之前,我们还是要提前判断一下栈当前空间是否已满,满了则扩容:
//数据入栈
void StackPush(ST* pst, STDataType x)
{assert(pst);if (pst->top + 1 == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->data, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("StackBush->realloc");exit(-1);}pst->data = tmp;pst->capacity = newcapacity;}pst->data[pst->top + 1] = x;pst->top++;
}
这些操作我们都已经很熟悉了,唯一值得注意的就是对top当前值的判断及后续操作。
2.数据出栈
//数据出栈
void StackPop(ST* pst)
{assert(pst);assert(pst->top >= 0);pst->top--;
}
出栈就很简单了,要注意的就是要断言一下是否为空栈。
3.返回栈顶数据
//返回栈顶数据
STDataType StackTop(ST* pst)
{assert(pst);assert(pst->top >= 0);return pst->data[pst->top];
}
同样需要断言一下是否为空栈。
4.判断空栈
//判断空栈
bool StackEmpty(ST* pst)
{assert(pst);if (pst->top >= 0){return true;}else{return false;}
}
这里我们造一个函数来判断栈是否为空,并返回bool型数据,用于我们后续遍历栈的操作。
5.销毁栈
//销毁栈
void StackDestroy(ST* pst)
{assert(pst);free(pst->data);pst->data = NULL;pst->capacity = 0;pst->top = -1;
}
销毁也是不变的操作,将所有数据复原。
6.测试栈
是的,栈总共就上边的5种基础操作方式,因为栈仅允许在栈顶操作数据,所以没有任意位置的入栈,出栈这些操作。
下面我们就来测试:
int main()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);while (StackEmpty(&st)){STDataType top = StackTop(&st);printf("%d ", top);StackPop(&st);}StackDestroy(&st);return 0;
}
能够看出,我们直接将所有的操作整合在一起。
想要遍历栈的数据,就需要返回一个栈顶数据,就让它出栈,再进行循环出栈,直到栈为空,也就是while循环的判断条件。
结果如下:

五.完整代码展示
1.Stack.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDataType;typedef struct Stack
{STDataType* data;int top;int capacity;
}ST;
//初始化
void StackInit(ST* pst);
//入栈
void StackPush(ST* pst, STDataType x);
//出栈
void StackPop(ST* pst);
//栈顶数据
STDataType StackTop(ST* pst);
//判断空栈
bool StackEmpty(ST* pst);
//销毁栈
void StackDestroy(ST* pst);
2.Stack.c
#include "Stack.h"//初始化
void StackInit(ST* pst)
{assert(pst);pst->data = NULL;pst->capacity = 0;pst->top = -1;
}
//入栈
void StackPush(ST* pst, STDataType x)
{assert(pst);if (pst->top + 1 == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->data, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("StackBush->realloc");exit(-1);}pst->data = tmp;pst->capacity = newcapacity;}pst->data[pst->top + 1] = x;pst->top++;
}
//出栈
void StackPop(ST* pst)
{assert(pst);assert(pst->top >= 0);pst->top--;
}
//栈顶数据
STDataType StackTop(ST* pst)
{assert(pst);assert(pst->top >= 0);return pst->data[pst->top];
}
//判断空栈
bool StackEmpty(ST* pst)
{assert(pst);if (pst->top >= 0){return true;}else{return false;}
}
//销毁栈
void StackDestroy(ST* pst)
{assert(pst);free(pst->data);pst->data = NULL;pst->capacity = 0;pst->top = -1;
}
3.test.c
#include "Stack.h"
int main()
{ST st;StackInit(&st);StackPush(&st, 1);StacKPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);while (StackEmpty(&st)){STDataType top = StackTop(&st);printf("%d ", top);StackPop(&st);}StackDestroy(&st);return 0;
}
六.总结
栈就是在顺序表的基础上进行一些整改,如果顺序表小伙伴们已经掌握,那么栈就是小趴菜!!!
最后喜欢博主文章的小伙伴不要忘记一键三连哦!!!
我们下期再见啦!!!
相关文章:
数据结构线性表——栈
前言:哈喽小伙伴们,今天我们将一起进入数据结构线性表的第四篇章——栈的讲解,栈还是比较简单的哦,跟紧博主的思路,不要掉队哦。 目录 一.什么是栈 二.如何实现栈 三.栈的实现 栈的初始化 四.栈的操作 1.数据入栈…...
自定义 springboot 启动器 starter 与自动装配原理
Maven 依赖 classpath 类路径管理 Maven 项目中的类路径添加来源分为三类 自定义 springboot starter starter 启动器定义的规则自定义 starter 示例 自动装配 文章链接...
16 _ 二分查找(下):如何快速定位IP对应的省份地址?
通过IP地址来查找IP归属地的功能,不知道你有没有用过?没用过也没关系,你现在可以打开百度,在搜索框里随便输一个IP地址,就会看到它的归属地。 这个功能并不复杂,它是通过维护一个很大的IP地址库来实现的。地址库中包括IP地址范围和归属地的对应关系。 当我们想要查询202…...
vb.net圣经带快捷键,用原装的数据库
Imports System.Data.SqlServerCe Imports System.Text.RegularExpressions Imports System.Data.OleDbPublic Class Form1Dim jiuyue As String() {"创", "出", "利", "民", "申", "书", "士", "…...
Unity中Shader的雾效
文章目录 前言一、Unity中的雾效在哪开启二、Unity中不同种类雾的区别1、线性雾2、指数雾1(推荐用这个,兼具效果和性能)3、指数雾2(效果更真实,性能消耗多) 三、在我们自己的Shader中实现判断,是…...
企业微信开发教程一:添加企微应用流程图解以及常见问题图文说明
最近在前辈的基础上新添加了一个企微应用,过程中遇到了一些卡点,这里一一通过图片标注与注释的方式记录一下,希望能给后来人提供一些清晰明了的帮助,话不多说,大家直接看图吧。 (文中包括一些本项目独有的配…...
【LeetCode】67. 二进制求和
67. 二进制求和 难度:简单 题目 给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。 示例 1: 输入:a "11", b "1" 输出:"100"示例 2: 输入:a "…...
【LeetCode刷题笔记】二叉树(一)
102. 二叉树的层序遍历 解题思路: 1. BFS广度优先遍历 ,使用队列,按层访问 解题思路: 2. 前序遍历 , 递归 ,在递归方法参数中,将 层索引...
NativeScript开发ios应用,怎么生成测试程序?
在 NativeScript 中,要部署 iOS 应用程序,你需要遵循以下一般步骤: 1、确保开发环境: 确保你的开发环境中已经安装了 Xcode,并且你有一个有效的 Apple 开发者账号。 2、构建 iOS 应用: 在你的 NativeScri…...
Js面试题:说一下js的模块化?
作用: 一个模块就是实现某个特定功能的文件,在文件中定义的变量、函数、类都是私有的,对其他文件不可见。 为了解决引入多个js文件时,出现 命名冲突、污染作用域 等问题 AMD: 浏览器端模块解决方案 AMD即是“异步模块定…...
媒体转码软件Media Encoder 2024 mac中文版功能介绍
Media Encoder 2024 mac是一款媒体转码软件,它可以将视频从一种格式转码为另一种格式,支持H.265、HDR10等多种编码格式,同时优化了视频质量,提高了编码速度。此外,Media Encoder 2024还支持收录、创建代理和输出各种格…...
整治PPOCRLabel中cv2文件读取问题(更新中)
PPOCRLabel 使用PPOCRLabel对ocr预标注结果进行纠正由于PaddleOCR代码库十分混乱,路径经常乱调pip和代码库的代码(pip库和源码冲突),经常报错,因此paddleocr和ppocrlabel都是使用pip包;PPOCRLabel中使用了cv2进行图片数据的读取,…...
网络运维Day09-补充
文章目录 rsync增量同步scp与rsync的区别rsync常用选项 rsync本地实验rsync远程同步实验练习上传练习下载 总结 rsync增量同步 rsync是增量同步的一种工具,可以实现本地目录之间数据同步,也可以实现远程跨主机之间数据同步 scp与rsync的区别 scp属于全…...
【C++】【Opencv】minMaxLoc()函数详解和示例
minMaxLoc()函数 是 OpenCV 库中的一个函数,用于找到一个多维数组中的最小值和最大值,以及它们的位置。这个函数对于处理图像和数组非常有用。本文通过参数和示例详解,帮助大家理解和使用该函数。 参数详解 函数原型…...
用Go实现网络流量解析和行为检测引擎
1.前言 最近有个在学校读书的迷弟问我:大德德, 有没有这么一款软件, 能够批量读取多个抓包文件,并把我想要的数据呈现出来, 比如:源IP、目的IP、源mac地址、目的mac地址等等。我说:“这样的软件你要认真找真能找出不少开源软件, 但毕竟没有你自己的灵魂在里面,要不…...
Mysql数据备份 — mysqldump
一 备份类型 - 逻辑备份(mysqldump): - 优点: - 恢复简单,可以使用管道将他们输入到mysql。 - 与存储引擎无关,因为是从MySQL服务器中提取数据而生成的,所以消除了底层数据…...
vue使用Echarts5实现词云图
先上官网 词云图有些特殊,它属于Echarts 的扩展,需要额外安装Echarts-wordcloud包。 Echarts 官网 Echarts-wordcloud 词云图官网 先安装 npm install echarts npm install echarts-wordcloud再引入 echarts选一个引入就行;4或5版本都可以 …...
带有密码的Excel只读模式,如何取消?
Excel文件打开之后发现是只读模式,想要退出只读模式,但是只读模式是带有密码的,该如何取消带有密码的excel只读文件呢? 带有密码的只读模式,是设置了excel文件的修改权限,取消修改权限,我们需要…...
Linux下基本操作命令
一、基础命令 1. pwd 命令 pwd命令用于显示当前所在的工作目录的全路径名称。该命令无需任何参数,只需在终端窗口中输入 pwd 命令即可使用。 2. cd 命令 cd命令用于更改当前工作目录。该命令需要一个参数:目标目录名称。例如,若要进入 Do…...
JVS低代码表单自定义按钮的使用说明和操作示例
在普通的表单设计中,虽然自带的【提交】、【重置】、【取消】按钮可以满足基本操作需求,但在面对更多复杂的业务场景时,这些按钮的显示控制就显得有些力不从心。为了更好地满足用户在表单操作过程中的个性化需求,JVS低代码推出了表…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
