【C语言数据结构——————栈和队列4000字详解】
欢迎阅读新一期的c语言数据结构模块————栈和队列
✒️个人主页:-_Joker_-
🏷️专栏:C语言
📜代码仓库:c_code
🌹🌹欢迎大佬们的阅读和三连关注,顺着评论回访🌹🌹
文章目录
- 栈
- 一、栈的概念
- 1.什么是栈
- 2.栈的基本操作
- 二、栈的实现
- 1.定义栈的结构
- 2.栈的初始化
- 3.栈的判空
- 4.入栈
- 5.出栈
- 6.获取栈顶元素
- 7.栈的销毁
- 一、栈的概念
- 队列
- 一、队列的概念
- 1.什么是队列
- 2.队列的基本操作
- 二、队列的实现
- 1.定义队列的结构
- 2.队列初始化
- 3.队列判空
- 4.入队
- 5.出队
- 6.获取队首元素
- 7.队列的销毁
- 一、队列的概念
栈
一、栈的概念
1.什么是栈
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
栈顶(Top): 线性表允许进行插入删除的那一端。
栈底(Bottom): 固定的,不允许进行插入和删除的另一端。
空栈: 不含任何元素的空表。
因为其后进先出(Last In First Out)的特性,栈又称为的线性表,简称LIFO结构
2.栈的基本操作
栈的基本操作通常都有以下几种:
- InitStack(&Stack):初始化一个空栈S。
- StackEmpty(&Stack):判断一个栈是否为空,若栈为空则返回true,否则返回false。
- StackPush(&Stack, x):进栈(栈的插入操作),若栈S未满,则将x加入使之成为新栈顶。
- StackPop(&Stack):出栈(栈的删除操作),若栈S非空,则返回一个提示.
- GetTop(&Stack):读栈顶元素。
- DestroyStack(&Stack):栈销毁,并释放S占用的存储空间(“&”表示引用调用)。
二、栈的实现
1.定义栈的结构
栈又分为顺序栈和链式栈,这里我们以顺序栈为例
首先想要实现一个栈,我们需要了解如何创建一个栈的结构,这里我们可以用结构体来定义,有两种方式:
①
#define N 10//定义栈的大小
struct Stack
{int a[N];int top;//栈顶
};
②
typedef int STDataType;
typedef struct Stack
{STDataType* a;//定义一个栈int top;//栈顶int capacity;//栈的大小
}ST;
第一种结构是用一个宏定义常量定义的栈的大小,这种用静态开辟的空间存在一些瑕疵,如果栈的空间大小太小需要成倍的扩容,很容易造成空间的浪费,所以我们优先采用方法②。
这种方法的好处在于我们可以动态开辟空间,如果空间不够就多开一个空间,这样就可以避免空间的浪费。
2.栈的初始化
void InitStack(ST* ps)
{assert(ps);//断言ps->a = NULL;//将指针置为空ps->capacity = 0;//初始化大小ps->top = 0;
}
3.栈的判空
bool StackEmpty(ST* ps)
{assert(ps);//断言return ps->top == 0;//栈顶为0则为空
}
4.入栈
入栈的具体流程如图
入栈首先判断空间大小,若已满则需要扩容,然后从栈底向上逐个插入
入栈操作如下
void StackPush(ST* ps, STDataType x)
{assert(ps);//断言if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);//扩容 if (tmp == NULL)//判断空间是否开辟成功{perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;//插入元素ps->top++;//栈顶移动
}
5.出栈
出栈操作如图
出栈首先判断是否为空,若为空则返回一个提示,若不为空则只需要直接将栈顶向下移动即可达到出栈的效果。
出栈操作如下;
void StackPop(ST* ps)
{assert(ps);//断言assert(ps->top > 0);//判断空--ps->top;//栈顶移动
}
6.获取栈顶元素
这里需要注意top的位置,如果top的指向是栈顶元素的话则只需要return a[ps->top]即可,由于我这里的top是指向栈顶元素的下一个位置,所以需要top-1才可以获取到栈顶元素.
STDataType StackTop(ST* ps)
{assert(ps);assert(ps->top > 0);//判断为空return ps->a[ps->top - 1];//返回栈顶元素
}
7.栈的销毁
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);//释放栈的空间ps->a = NULL;//将指针置空,防止野指针产生ps->top = ps->capacity = 0;
}
队列
一.队列的概念
1.什么是队列
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
队首(front): 线性表允许进行插入删除的那一端。
队尾(rear): 固定的,不允许进行插入和删除的另一端。
空队列: 不含任何元素的空表。
因为其先进先出(First In First Out)的特性,队列又称为的线性表,简称FIFO结构
2.队列的基本操作
- QueueInit(&Q):初始化队列,构造一个空队列Q。
- QueueEmpty(Q):判队列空,若队列Q为空返回true,否则返回false。
- QueuePush(&Q, x):入队,若队列Q未满,将x加入,使之成为新的队尾。
- QueuePop(&Q):出队,若队列Q非空,删除队头元素。
- QueueFront(&Q):读队头元素。
- QueueDestroy(&Q): 队列销毁。
二.队列的实现
队列同样拥有两种实现方式(顺序结构和链式结构),但是用顺序结构实现队列在出列的情况比较复杂,所以这里我们以链式结构来实现队列
1.定义队列的结构
和栈类似,队列的结构可以这样定义
typedef int QDataType;
typedef struct QueueNode//队列节点
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue//队列结构
{QNode* head;//队首QNode* tail;//队尾int size;
}Que;
2.队列初始化
void QueueInit(Que* pq)
{assert(pq);//断言pq->head = pq->tail = NULL;//头尾指针置空pq->size = 0;//大小初始化
}
3.队列判空
bool QueueEmpty(Que* pq)
{assert(pq);//断言return pq->head == NULL;//头指针为空则为空
}
4.入队
入队操作如图
入队新开一个节点,将元素插入新的节点,然后判断尾指针是否指向空,若为空则将头尾指针指向新的节点,若不为空则将新的节点作为队尾。
入队实现:
void QueuePush(Que* pq, QDataType x)
{assert(pq);//断言QNode* newnode = (QNode*)malloc(sizeof(QNode));//开一个新节点if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;//新节点赋值newnode->next = NULL;if (pq->tail == NULL)//空队列{pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}
5.出队
出队操作和入队操作类似,出队首先判空,若队列为空则返回一个提示,若不为空需要将队首节点指向下一个节点并释放第一个节点。若队首的下一个元素为空,说明改队列只有一个节点,所以需要将头尾指针置空防止野指针的产生。
出队操作如下
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));//判空if (pq->head->next == NULL)//判断队首下一个节点是否为空{free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;//新开一个节点并将头指针下一个节点给新节点free(pq->head);//释放队首pq->head = next;//将新开的节点赋给新队首}pq->size--;//队列大小-1
}
6.读取队首元素
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));//判空return pq->head->data;//取队首元素
}
7.队列销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;//创建一个节点存储队首while (cur)//{QNode* next = cur->next;//创建一个中间节点free(cur);//从队首一个一个删除cur = next;}pq->head = pq->tail = NULL;//删完所有节点将指针置空pq->size = 0;//初始化大小
}
以上就是栈和队列的基本概念和基础操作实现,如果文章存在错误请在评论区留言,最后别忘了三连支持一下,顺着评论回访🌹🌹
相关文章:
【C语言数据结构——————栈和队列4000字详解】
欢迎阅读新一期的c语言数据结构模块————栈和队列 ✒️个人主页:-_Joker_- 🏷️专栏:C语言 📜代码仓库:c_code 🌹🌹欢迎大佬们的阅读和三连关注,顺着评论回访🌹&#…...
电子地图 | VINS-FUSION | 小觅相机D系列
目录 一、相关介绍 二、VINS-FUSION环境安装及使用 (一)Ubuntu18.04安装配置 1、Ubuntu下载安装 2、设置虚拟内存(可选) (二)VINS-FUSION环境配置 1、ros安装 2、ceres-solver安装 3、vins-fusion…...
C++goto语句
在本文中,您将了解goto语句,它是如何工作的,以及为什么应该避免它。在C 编程中,goto语句用于通过将控制权转移到程序的其他部分来更改程序执行的正常顺序。 goto语句的语法 goto label; ... .. ... ... .. ... ... .. ... label…...
Spring学习笔记11 GoF代理模式
Spring学习笔记10 JdbcTemplate_biubiubiu0706的博客-CSDN博客 新建个maven模块 static-proxy 演示静态代理 订单接口 测试 需求:统计每个业务方法的耗时 package com.example.proxy.service;/*** author hrui* date 2023/9/25 8:42*/ public class OrderServiceImpl implem…...
代码随想录二刷 Day23
669. 修剪二叉搜索树 找到小数字的右子树与大数字左子树必须要重新检查一遍然后让root的左右直接指向return的左右节点; class Solution { public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root NULL) return NULL;if (root->val < low…...
Ubuntu `apt` 报错 “Errors were encountered while processing: base-passwd“ 的解决方法
Ubuntu apt 更新时出现报错: Setting up base-passwd (3.5.52build1) ... Changing home-directory of irc from /var/run/ircd to /run/ircd 1 changes have been made, rewriting files Writing passwd-file to /etc/passwd Error making backupfile /etc/passwd…...
XXL-JOB分布式任务调度
XXL-JOB分布式任务调度 在实际项目中,为了降低耦合,通常会把定时任务的逻辑单独抽离出来,构建成一个新的工程。也有可能需要定时任务实现高可用,组建成集群,提高容错率。 那么问题也就来了。既然定时任务是多个…...
加拿大人工智能数据搜索平台【Secoda】完成1400万美元A轮融资
来源:猛兽财经 作者:猛兽财经 猛兽财经获悉,总部位于加拿大多伦多的人工智能数据搜索平台【Secoda】今日宣布已完成1400万美元A轮融资。 本轮融资由Craft Ventures领投,参与投资的投资机构有Abstract Ventures、现有投资者YCombi…...
less与sass
1.变量: Less: my-color: #ff0000;.container {background-color: my-color; } Sass:$my-color: #ff0000;.container {background-color: $my-color; } 在这点上,Less和Sass的变量概念基本相同,都是以声明的方式存储值,然后在…...
已解决: Go Error: no Go files in /path/to/directory问题
🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🦄 博客首页: 🐅🐾猫头虎的博客🎐《面试题大全专栏》 🦕 文章图文并茂🦖…...
2022年6月和7月的工作经历
6月 3D打标软件 3D打标软件,要求在Open3d上加几个2D文字。大致有如下几个方案: 依葫芦画瓢,但O3DVisualizer派生于gui::Window,我的程序派生于Visualizer。工作量不小。 利用OpenGL输出文字,Baidu的两种方法一个编…...
【图像处理】SIFT角点特征提取原理
一、说明 提起在OpenCV中的特征点提取,可以列出Harris,可以使用SIFT算法或SURF算法来检测图像中的角特征点。本篇围绕sift的特征点提取,只是管中窥豹,而更多的特征点算法有: Harris & Stephens / Shi–Tomasi 角点…...
flutter开发实战-应用更新apk下载、安装apk、启动应用实现
flutter开发实战-应用更新apk下载、安装apk、启动应用实现 在开发过程中,经常遇到需要更新下载新版本的apk文件,之后进行应用更新apk下载、安装apk、启动应用。我们在flutter工程中实现下载apk,判断当前版本与需要更新安装的版本进行比对判断…...
DispatcherServlet初始化之Spring容器创建1.0
一、前言 在SpringMVC框架中,DispatcherServlet扮演着非常重要的角色,它负责接收所有的HTTP请求并将其分发给相应的处理器。在DispatcherServlet的初始化过程中,会创建一个Spring容器来管理应用程序中的Bean。 二、步骤 1、加载配置文件&a…...
CSS的基础
CSS美化HTML,布局网页 CSS最大的价值:由HTML专注去做结构呈现,样式给CSS,结构(HTML)与样式(CSS)相分离 CSS主要由选择器以及一条或多条声明 在<head></head>中实现CSS在<body…...
mathtype如何嵌入到word中?详细mathtype安装步骤教程
mathtype是一款功能特别强大的数学方式编辑软件,为用户提供各种强大的数学公式符号帮助用户进行计算,并且速度很快。有小伙伴知道mathtype如何嵌入到word中吗,这里小编就给大家详细介绍一下mathtype嵌入到word中的方法,有需要的小…...
云安全之访问控制的常见攻击及防御
访问控制攻击概述 访问控制漏洞即应用程序允许攻击者执行或者访问某种攻击者不具备相应权限的功能或资源。 常见的访问控制可以分为垂直访问控制、水平访问控制及多阶段访问控制 (上下文相关访问控制),与其相应的访问控制漏洞为也垂直越权漏洞(普通用户可以访问或…...
Java编程技巧:跨域
目录 1、跨域概念2、后端CORS(跨域资源共享)配置原理3、既然请求跨域了,那么请求到底发出去没有?4、通过后端CORS(跨域资源共享)配置解决跨域问题代码4.1、SpringBoot(FilterRegistrationBean&a…...
react create-react-app 配置less
环境信息: create-react-app:v5 react:18.2.0 node:18.16.0 如果你不必须使用 less 建议直接使用scss。 因为less配置会遇到很多问题。 配置less过程: 如果你只需要 sass的话,就可以直接使用sass。因为默认配置了scss。 npm、yarn、cnpm、…...
树的表示——孩子兄弟表示法
从图中可以看出,树的每个结点,都有不确定的指向他们的孩子的节点,如果我们定义这样一个结构体来便是数的结构的话: struct TreeNode { int val; struct TreeNodep1; struct TreeNodep1; … }; 是不能够表示一棵树的,因…...
Windows11安装MySQL8.1
安装过程中遇到任何问题均可以参考(这个博客只是单纯升级个版本和简化流程) Windows安装MySQL8教程-CSDN博客 到官网下载mysql8数据库软件 MySQL :: Download MySQL Community Server 下载完后,解压到你需要安装的文件夹 其中的配置文件内容了如下 [mysqld]# 设置3306端口po…...
Linux编程——经典链表list_head
1. 关于list_head struct list_head是Linux内核定义的双向链表,包含一个指向前驱节点和后继节点的指针的结构体。其定义如下: struct list_head {struct list_head *next, *prev; //双向链表,指向节点的指针 };1.1 链表的定义和初始化 有两…...
基于51单片机NEC协议红外遥控发送接收仿真设计( proteus仿真+程序+原理图+报告+讲解视频)
基于51单片机NEC协议红外遥控发送接收仿真设计 讲解视频1.主要功能:2.仿真3. 程序代码4. 原理图5. 设计报告6. 设计资料内容清单&&下载链接 基于51单片机NEC协议红外遥控发送接收仿真设计 51单片机红外发送接收仿真设计( proteus仿真程序原理图报告讲解视频…...
Jmeter分布式压力测试
目录 1、场景 2、原理 3、注意事项 4、slave配置 5、master配置 6、脚本执行 1、场景 在做性能测试时,单台机器进行压测可能达不到预期结果。主要原因是单台机器压到一定程度会出现瓶颈。也有可能单机网卡跟不上造成结果偏差较大。 例如4C8G的window server机…...
Rust :mod.rs和lib.rs中use的作用
一、mod.rs和lib.rs mod.rs往往是把同一目录下的n个rs文件综合在一起的有效方式; lib.rs是一个库或子库层次综合在一起的有效方式; 下面举个实例来说明。生成一个rusttoc本地库(由cargo new rusttoc --lib所生成),目录…...
ISP图像信号处理——平场校正介绍以及C++实现
参考文章1:http://t.csdn.cn/h8TBy 参考文章2:http://t.csdn.cn/6nmsT 参考网址3:opencv平场定标 - CSDN文库 平场校正一般先用FPN(Fixed Pattern Noise)固定图像噪声校正,即暗场校正;再用PRNU(Photo Response Non Uniformity)…...
【深入了解Java String类】
目录 String类 常用方法 字符串的不可变性 String的内存分析 StringBuilder类 解释可变和不可变字符串 常用方法 面试题:String,StringBuilder,StringBuffer之间的区别和联系 String类的OJ练习 String类 【1】直接使用,…...
基于SpringBoot的知识管理系统
目录 前言 一、技术栈 二、系统功能介绍 用户管理 文章分类 资料分类 文章信息 论坛交流 资料下载 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 随着信息互联网信息的飞速发展,无纸化作业变成了一种趋势,针对这个问题开发一个…...
Pytorch基础:Tensor的reshape方法
在Pytorch中,reshape是Tensor的一个重要方法,它与Numpy中的reshape类似,用于返回一个改变了形状但数据和数据顺序和原来一致的新Tensor对象。注意:此时返回的数据对象并不一定是新的,这取决于应用此方法的Tensor是否是…...
wordpress背景图如何设置/搜索引擎优化技术都有哪些
具体的安装步骤网上已经很多,我只说碰到的几个问题。 虚拟机环境下安装。 虚拟机版本: virtual box 4.2 guest os: oracle linux 6.3 DB version: 11.2.0.3.0 安装RDBMS的时候之前,要检查OS的很多包是否安装。 在orac…...
如何给公司做网站推广宣传/seo网站优化培训
(1) 10gen,它既是一个云平台,又是一个可下载的开放源代码包,可用于创建您自己的私有云。10gen 是类似于 App Engine 的一个软件栈,它提供与 App Engine 类似的功能 — 但有一些不同之处。通过 10gen&#x…...
网站注册界面设计/和生活app下载安装最新版
面向对象 面向对象程序语言的特点: 1.抽象, 2.封装, 3.继承, 4.多态 类,对象和成员的使用方法及区别: 声明一个类: class 人类 {public:void 获得身高()&#…...
福建省住房和城乡建设部网站/域名免费注册
文章概述: 一、逻辑卷存储概念 二、逻辑卷管理器 三、管理物理卷 四、管理卷组 AIX的存储管理和逻辑卷管理(Logical Volume Management,LVM) 一、逻辑卷存储概念 五个基本的逻辑卷存储概念:物理卷(PV&am…...
html企业网站源码/营销推广渠道有哪些
智天下系统开发(广州公司)找广州【贺经理:188微1924电2925同号】智天下ERP管理系统,OA系统,智天下商城系统开发,智天下小程序开发,智天下公众号开发,智天下源码开发,智天下PHP源码搭建ÿ…...
哈尔滨专业建设网站设计/网站关键词怎么添加
(一):Scrapy爬虫框架的安装 当然如果你想用Anaconda 方式来安装也行,只是个人觉得杀鸡用牛刀,哈哈,随意吧! 创建爬虫项目 在电脑上新建一个Scrapy项目,在命令行中切换到要存储的位置. D:\work\my_python\python_scrapy…...