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

数据结构线性表——栈

前言:哈喽小伙伴们,今天我们将一起进入数据结构线性表的第四篇章——栈的讲解,栈还是比较简单的哦,跟紧博主的思路,不要掉队哦。


目录

一.什么是栈

二.如何实现栈

三.栈的实现

栈的初始化

四.栈的操作

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;
}

六.总结

栈就是在顺序表的基础上进行一些整改,如果顺序表小伙伴们已经掌握,那么栈就是小趴菜!!!

最后喜欢博主文章的小伙伴不要忘记一键三连哦!!!

我们下期再见啦!!!

相关文章:

数据结构线性表——栈

前言&#xff1a;哈喽小伙伴们&#xff0c;今天我们将一起进入数据结构线性表的第四篇章——栈的讲解&#xff0c;栈还是比较简单的哦&#xff0c;跟紧博主的思路&#xff0c;不要掉队哦。 目录 一.什么是栈 二.如何实现栈 三.栈的实现 栈的初始化 四.栈的操作 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&#xff08;推荐用这个&#xff0c;兼具效果和性能&#xff09;3、指数雾2&#xff08;效果更真实&#xff0c;性能消耗多&#xff09; 三、在我们自己的Shader中实现判断&#xff0c;是…...

企业微信开发教程一:添加企微应用流程图解以及常见问题图文说明

最近在前辈的基础上新添加了一个企微应用&#xff0c;过程中遇到了一些卡点&#xff0c;这里一一通过图片标注与注释的方式记录一下&#xff0c;希望能给后来人提供一些清晰明了的帮助&#xff0c;话不多说&#xff0c;大家直接看图吧。 &#xff08;文中包括一些本项目独有的配…...

【LeetCode】67. 二进制求和

67. 二进制求和 难度&#xff1a;简单 题目 给你两个二进制字符串 a 和 b &#xff0c;以二进制字符串的形式返回它们的和。 示例 1&#xff1a; 输入:a "11", b "1" 输出&#xff1a;"100"示例 2&#xff1a; 输入&#xff1a;a "…...

【LeetCode刷题笔记】二叉树(一)

102. 二叉树的层序遍历 解题思路: 1. BFS广度优先遍历 ,使用队列,按层访问 解题思路: 2. 前序遍历 , 递归 ,在递归方法参数中,将 层索引...

NativeScript开发ios应用,怎么生成测试程序?

在 NativeScript 中&#xff0c;要部署 iOS 应用程序&#xff0c;你需要遵循以下一般步骤&#xff1a; 1、确保开发环境&#xff1a; 确保你的开发环境中已经安装了 Xcode&#xff0c;并且你有一个有效的 Apple 开发者账号。 2、构建 iOS 应用&#xff1a; 在你的 NativeScri…...

Js面试题:说一下js的模块化?

作用&#xff1a; 一个模块就是实现某个特定功能的文件&#xff0c;在文件中定义的变量、函数、类都是私有的&#xff0c;对其他文件不可见。 为了解决引入多个js文件时&#xff0c;出现 命名冲突、污染作用域 等问题 AMD&#xff1a; 浏览器端模块解决方案 AMD即是“异步模块定…...

媒体转码软件Media Encoder 2024 mac中文版功能介绍

Media Encoder 2024 mac是一款媒体转码软件&#xff0c;它可以将视频从一种格式转码为另一种格式&#xff0c;支持H.265、HDR10等多种编码格式&#xff0c;同时优化了视频质量&#xff0c;提高了编码速度。此外&#xff0c;Media Encoder 2024还支持收录、创建代理和输出各种格…...

整治PPOCRLabel中cv2文件读取问题(更新中)

PPOCRLabel 使用PPOCRLabel对ocr预标注结果进行纠正由于PaddleOCR代码库十分混乱,路径经常乱调pip和代码库的代码&#xff08;pip库和源码冲突&#xff09;,经常报错&#xff0c;因此paddleocr和ppocrlabel都是使用pip包;PPOCRLabel中使用了cv2进行图片数据的读取&#xff0c;…...

网络运维Day09-补充

文章目录 rsync增量同步scp与rsync的区别rsync常用选项 rsync本地实验rsync远程同步实验练习上传练习下载 总结 rsync增量同步 rsync是增量同步的一种工具&#xff0c;可以实现本地目录之间数据同步&#xff0c;也可以实现远程跨主机之间数据同步 scp与rsync的区别 scp属于全…...

【C++】【Opencv】minMaxLoc()函数详解和示例

minMaxLoc&#xff08;&#xff09;函数 是 OpenCV 库中的一个函数&#xff0c;用于找到一个多维数组中的最小值和最大值&#xff0c;以及它们的位置。这个函数对于处理图像和数组非常有用。本文通过参数和示例详解&#xff0c;帮助大家理解和使用该函数。 参数详解 函数原型…...

用Go实现网络流量解析和行为检测引擎

1.前言 最近有个在学校读书的迷弟问我:大德德, 有没有这么一款软件, 能够批量读取多个抓包文件,并把我想要的数据呈现出来, 比如:源IP、目的IP、源mac地址、目的mac地址等等。我说&#xff1a;“这样的软件你要认真找真能找出不少开源软件, 但毕竟没有你自己的灵魂在里面,要不…...

Mysql数据备份 — mysqldump

一 备份类型 - 逻辑备份&#xff08;mysqldump&#xff09;&#xff1a; - 优点&#xff1a; - 恢复简单&#xff0c;可以使用管道将他们输入到mysql。 - 与存储引擎无关&#xff0c;因为是从MySQL服务器中提取数据而生成的&#xff0c;所以消除了底层数据…...

vue使用Echarts5实现词云图

先上官网 词云图有些特殊&#xff0c;它属于Echarts 的扩展&#xff0c;需要额外安装Echarts-wordcloud包。 Echarts 官网 Echarts-wordcloud 词云图官网 先安装 npm install echarts npm install echarts-wordcloud再引入 echarts选一个引入就行&#xff1b;4或5版本都可以 …...

带有密码的Excel只读模式,如何取消?

Excel文件打开之后发现是只读模式&#xff0c;想要退出只读模式&#xff0c;但是只读模式是带有密码的&#xff0c;该如何取消带有密码的excel只读文件呢&#xff1f; 带有密码的只读模式&#xff0c;是设置了excel文件的修改权限&#xff0c;取消修改权限&#xff0c;我们需要…...

Linux下基本操作命令

一、基础命令 1. pwd 命令 pwd命令用于显示当前所在的工作目录的全路径名称。该命令无需任何参数&#xff0c;只需在终端窗口中输入 pwd 命令即可使用。 2. cd 命令 cd命令用于更改当前工作目录。该命令需要一个参数&#xff1a;目标目录名称。例如&#xff0c;若要进入 Do…...

JVS低代码表单自定义按钮的使用说明和操作示例

在普通的表单设计中&#xff0c;虽然自带的【提交】、【重置】、【取消】按钮可以满足基本操作需求&#xff0c;但在面对更多复杂的业务场景时&#xff0c;这些按钮的显示控制就显得有些力不从心。为了更好地满足用户在表单操作过程中的个性化需求&#xff0c;JVS低代码推出了表…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...