数据结构:栈和队列(超详细)

目录

​编辑

栈:

栈的概念及结构:

 栈的实现:

队列:

队列的概念及结构:

 队列的实现:

扩展知识:

 以上就是个人学习线性表的个人见解和学习的解析,欢迎各位大佬在评论区探讨!

感谢大佬们的一键三连! 感谢大佬们的一键三连! 感谢大佬们的一键三连!


栈:

栈的概念及结构:

        栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。一般用在1.公平性排队(抽号机);2.BFS(广度优先遍历)。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶。

 栈的实现:

        栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。链的尾插需要调动更多的数据过程中有更多的消耗

// 支持动态增长的栈
typedef int STDataType ;
typedef struct Stack
{
STDataType * _a ;
int _top ; // 栈顶
int _capacity ; // 容量
} Stack ;
// 初始化栈
void StackInit ( Stack * ps );
// 入栈
void StackPush ( Stack * ps , STDataType data );
// 出栈
void StackPop ( Stack * ps );
// 获取栈顶元素
STDataType StackTop ( Stack * ps );
// 获取栈中有效元素个数
int StackSize ( Stack * ps );
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回 0
int StackEmpty ( Stack * ps );
// 销毁栈
void StackDestroy ( Stack * ps );

 //初始化栈


//初始化
void SLInit(SL* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}

//入栈

//入栈
void SLPush(SL* ps, STDataType x)
{assert(ps);//栈顶=容量说明需要扩容if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}ps->a[ps->top] = x;//后缀++方便下一次入栈和打印栈顶ps->top++;
}

//出栈

//出栈
void SLPop(SL* ps)
{assert(ps);//为空情况“0”assert(ps->top > 0);//--ps->top;
}

//获得栈顶元素

//获得栈顶元素
STDataType SLTTop(SL* ps)
{assert(ps);//为空情况“0”assert(ps->top > 0);int n = (ps->top) - 1;return ps->a[n];
}

 //获取栈中有效元素个数

//获取栈中有效元素个数
int SLSize(SL* ps)
{assert(ps);return ps->top;
}

//销毁栈

//销毁栈
void SLDestroy(SL* ps)
{assert(ps);//开辟数组优势:一次全部释放free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool SLEmpty(SL* ps)
{assert(ps);//为“0”说明为NULLif (ps->top == 0){return true;}return false;
}

队列:

队列的概念及结构:

         队列: 只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有 先进先出 FIFO(First In First Out) 。
入队列:进行插入操作的一端称为队尾; 
出队列:进行删除操作的一端称为队头。

 队列的实现:

        队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数 组头上出数据,效率会比较低

// 链式结构:表示队列
typedef struct QListNode
{
struct QListNode * _pNext ;
QDataType _data ;
} QNode ;
// 队列的结构
typedef struct Queue
{
QNode * _front ;
QNode * _rear ;
} Queue ;
// 初始化队列
void QueueInit ( Queue * q );
// 队尾入队列
void QueuePush ( Queue * q , QDataType data );
// 队头出队列
void QueuePop ( Queue * q );
// 获取队列头部元素
QDataType QueueFront ( Queue * q );
// 获取队列队尾元素
QDataType QueueBack ( Queue * q );
// 获取队列中有效元素个数
int QueueSize ( Queue * q );
// 检测队列是否为空,如果为空返回非零结果,如果非空返回 0
int QueueEmpty ( Queue * q );
// 销毁队列
void QueueDestroy ( Queue * q );

//初始化

//初始化
void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}

//入列

//入列
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;//第一次或N+1次if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

//出列

//出列
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){//就剩下一个free(pq->head);pq->head = pq->tail = NULL;}else{//剩下两个及以上Que * del = pq->head;pq->head = pq->head->next;free(del);}pq->size--;
}

// 获取队列头部元素 

// 获取队列头部元素 
Qdatatype QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

// 获取队列队尾元素 

// 获取队列队尾元素 
Qdatatype QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

// 获取队列中有效元素个数 

// 获取队列中有效元素个数 
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}

// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 

// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}

//销毁

//销毁
void QueueDestroy(Que* pq)
{assert(pq);while (pq->head){Que* del = pq->head->next;free(pq->head);pq->head = del;pq->size--;}pq->head = pq->tail = NULL;
}

扩展知识:

        队列适合使用链表实现,使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题,因此大佬们设计出了循环队列,循环队列就是为了解决顺序结构实现队列假溢出问题的

        循环队列:实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现,也可以使用循环链表实现。

 

        同时指向一个位置为空rear(尾)的下一个位置为front(头)时说明已经填满此处是多开辟了一个空间来做判断是否为满 !!!

 以上就是个人学习线性表的个人见解和学习的解析,欢迎各位大佬在评论区探讨!

感谢大佬们的一键三连! 感谢大佬们的一键三连! 感谢大佬们的一键三连!

                                              

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/93078.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++入门篇9---list

list是带头双向循环链表 一、list的相关接口及其功能 1. 构造函数 函数声明功能说明list(size_type n,const value_type& valvalue_type())构造的list中包含n个值为val的元素list()构造空的listlist(const list& x)拷贝构造list(InputIterator first, InputIterator…

Python爬虫——scrapy_当当网图书管道封装

创建爬虫项目 srcapy startproject scrapy_dangdang进入到spider文件里创建爬虫文件(这里爬取的是青春文学,仙侠玄幻分类) srcapy genspider dang http://category.dangdang.com/cp01.01.07.00.00.00.html获取图片、名字和价格 # 所有的se…

快速通过华为HCIP认证

你可以按照以下步骤进行准备和学习: 华为认证课程和资料--提取码:1234https://pan.baidu.com/s/1YJhD8QbocHhZ30MvrKm8hg 了解认证要求:查看华为官方网站上的HCIP认证要求和考试大纲,了解考试的内容、考试形式和考试要求。 学习相关知识&am…

c++ std::shared_ptr(内存布局)

https://cplusplus.com/reference/memory/shared_ptr/

AIGC绘画:kaggle部署stable diffusion项目绘画

文章目录 kaggle介绍项目部署edit my copy链接显示 结果展示 kaggle介绍 Kaggle成立于2010年,是一个进行数据发掘和预测竞赛的在线平台。从公司的角度来讲,可以提供一些数据,进而提出一个实际需要解决的问题;从参赛者的角度来讲&…

泛微E-Office任意文件上传漏洞复现

0x01 产品简介 泛微E-Office是一款标准化的协同 OA 办公软件,泛微协同办公产品系列成员之一,实行通用化产品设计,充分贴合企业管理需求,本着简洁易用、高效智能的原则,为企业快速打造移动化、无纸化、数字化的办公平台。 0x02 漏…

【Linux】Reactor模式

Reactor模式 Reactor模式的定义 Reactor反应器模式,也叫做分发者模式或通知者模式,是一种将就绪事件派发给对应服务处理程序的事件设计模式。 Reactor模式的角色构成 Reactor主要由以下五个角色构成: reactor模式的角色 角色解释Handle(句…

TIA博途_通过EXCEL快速给PLC程序段添加注释信息的方法示例

通过EXCEL快速给PLC程序段添加注释信息的方法示例 如下图所示,以OB1为例,正常情况下,我们可以在博途中直接输入各个程序段的注释信息, 但是如果程序段较多的话,逐个输入的话效率不高,此时可以参考下面这种通过EXCEL进行快速添加的方法。 如下图所示,选中某个OB或FC、FB块…

线性代数再回顾

最近,在深度学习线性代数,之前大一的时候学过线性代数,但那纯属于是应试用的,考试一考完,啥都忘了,也说出不出个所以然,所以,在B站的MIT的线性代数以及3blue1brown线性代数的本质中去…

Vim学习(二)—— 编译C程序

打开终端,这里以MobaXterm为例, 邮件创建新的空文件并命名, 然后cd到对应路径下,用 vim hello.cvim打开创建的文件,进入编辑模式,编辑完程序后按Esc退出编辑模式,输入 :wq保存并退出&#xf…

uniapp微信小程序消息订阅快速上手

一、微信公众平台小程序开通消息订阅并设置模板 这边的模板id和详细内容后续前后端需要使用 二、uniapp前端 需要是一个button触发 js: wx.getSetting({success(res){console.log(res)if(res.authSetting[scope.subscribeMessage]){// 业务逻辑}else{uni.request…

Linux下如何修改CPU 电源工作模式

最近处理一起历史遗留问题,感觉很爽。 现象: 背景:设备采用ARM,即rk3568处理器,采用Linux系统;主要用于视觉后端处理 现象:当软件运行一段时间,大概1个小时(也不是很固定…

对话 4EVERLAND:Web3 是云计算的新基建吗?

在传统云计算的发展过程中,数据存储与计算的中心化问题,对用户来说一直存在着潜在的安全与隐私风险——例如单点故障可能会导致网络瘫痪和数据泄露等危险。同时,随着越来越多 Web3 项目应用的落地,对于数据云计算的性能要求也越来…

Kotlin runBlocking launch多个协程读写mutableListOf时序

Kotlin runBlocking launch多个协程读写mutableListOf时序 import kotlinx.coroutines.delay import kotlinx.coroutines.launch import kotlinx.coroutines.runBlockingfun main(args: Array<String>) {var lists mutableListOf<String>()runBlocking {launch {r…

《零基础7天入门Arduino物联网-05》电路基础知识下

配套视频课程&#xff1a;《零基础学Arduino物联网&#xff0c;入门到进阶》 配套课件资料获取&#xff1a;微联实验室 配套学习套件购买&#xff1a;淘宝搜索店铺【微联实验室】 电阻、电容、电感和二极管 电阻 电阻用于电路中&#xff0c;其主要功能在于控制电流的流动和阻…

R语言实现非等比例风险生存资料分析(1)

#非等比例风险的生存资料分析 ###1 生成模拟数据### library(flexsurv) set.seed(123) # 生成样本数量 n <- 100 # 生成时间数据 time <- sample(1:1000,n,replaceF) # 调整shape和scale参数以控制生存曲线形状 # 生成事件数据&#xff08;假设按比例风险模型&#xff0…

GitHub 如何部署写好的H5静态页面

感谢粉皮zu的私信&#xff0c;又有素材写笔记了。(●’◡’●) 刚好记录一下我示例代码的GitHub部署配置&#xff0c;以便于后期追加仓库。 效果 环境 gitwin 步骤 第一步 新建仓库 第二步 拉取代码 将仓库clone到本地 git clone 地址第三步 部署文件 新建.github\workflo…

设计模式之原型模式Prototype的C++实现

1、原型模式提出 在软件功能设计中&#xff0c;经常面临着“某些结构复杂的对象”的创建工作&#xff0c;且创建的对象想拥有其他对象在某一刻的状态&#xff0c;则可以使用原型模型。原型模型是通过拷贝构造函数来创建对象&#xff0c;并且该对象拥有其他对象在某一刻的状态。…

知识体系总结(九)设计原则、设计模式、分布式、高性能、高可用

文章目录 架构设计为什么要进行技术框架的设计 六大设计原则一、单一职责原则二、开闭原则三、依赖倒置原则四、接口分离原则五、迪米特法则&#xff08;又称最小知道原则&#xff09;六、里氏替换原则案例诠释 常见设计模式构造型单例模式工厂模式简单工厂工厂方法 生成器模式…

【深入理解Linux内核锁】三、原子操作

我的圈子: 高级工程师聚集地 我是董哥,高级嵌入式软件开发工程师,从事嵌入式Linux驱动开发和系统开发,曾就职于世界500强企业! 创作理念:专注分享高质量嵌入式文章,让大家读有所得! 文章目录 1、原子操作思想2、整型变量原子操作2.1 API接口2.2 API实现2.2.1 原子变量结…