深入浅出带你玩转栈与队列——【数据结构】

W...Y的主页 😊

代码仓库分享 💕

目录

1.栈

1.1栈的概念及结构

1.2栈的结构特征图 

​编辑 1.3栈的实现

1.3.1栈的初始化

1.3.2进栈

1.3.3出栈

1.3.4销毁内存

1.3.5判断栈是否为空

1.3.5栈底元素的读取

1.3.6栈中大小

1.4栈实现所有接口

2.队列

2.1队列的概念

2.2队列的结构 

 2.3队列的实现

2.3.1队列的接口总览

2.3.2队列的初始化

 2.3.3入队

2.3.4出队

2.3.5获取对头元素

2.3.6获取对尾元素

2.3.7判断是否为空

2.3.8队列销毁

3.拓展内容

 

在前几期的学习中，我们学习了顺序表与链表，今天我们将学习一种新的数据结构——栈与队列。而栈与队列实际上就是链表的一种变形产物，但肯定会有许多结构上的不同。

现在就让我们进入栈和队列，看看它们的特点！！！

1.栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

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

1.2栈的结构特征图 

文字力量有时太过渺小，我们通过图解更清楚的了解栈的特点。

 1.3栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

1.3.1栈的初始化

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

这里我们使用数组作为结构，更好的适用于栈的特征。但是这又与顺序表中的不同，顺序表在刚进入就进行了开辟空间，而我们栈的初始化先全部设为0。

1.3.2进栈

在进栈时，我们会遇到栈内存满的情况，所以我们必须进行判断(top 有效内容与 capacity容量是否相等)，如果相等我们就进行realloc进行扩容即可。然后将需要放入栈的内容存入堆区，有效内容top++即可完成。如果内容开始为0，我们使用三元表达式直接扩容为4。

void STPush(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");
			exit(-1);
		}
		ps->a[ps->top] = x;
		ps->top++;
	}
}

注意：malloc与realloc都可以使用，当给予realloc一个指针时，功能完全相同。

1.3.3出栈

出栈非常简单，只需要将top--，不去访问其内容即可。

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	--ps->top;
}

1.3.4销毁内存

销毁堆上内存也非常简单，只需free掉即可

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

但是我们一定要用assert进行断言，防止传入空指针。

1.3.5判断栈是否为空

栈中是否插入内容，我们可以创建一个函数进行判断一下。返回值为bool类型，我们需要在头文件中加入#include<stdbool.h>才可以使用。

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

1.3.5栈底元素的读取

在读取栈底元素时，我们需要检查传入栈的指针是否正确以及栈中是否为空，两个必须都为真即可进行下面操作。

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

栈底元素就是top-1的内容，我们直接返回即可。

1.3.6栈中大小

当我们一直添加数据，需要了解栈中有多少个有效数据时，我们却束手无策，所以我们还需要一个能测出栈中大小函数。

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

1.4栈实现所有接口

我们需要了解的所有接口，可以放在头文件中：

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType _a[N];
 int _top; // 栈顶
}Stack;
// 支持动态增长的栈
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);

2.队列

2.1队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2.2队列的结构 

 2.3队列的实现

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

2.3.1队列的接口总览

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;

void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);

在这里使用单链表，作为队列结构。队列特点就是先进先出，但是单链表比较适合头插头删，并不适合尾删，所以我们创建另一个结构体记录尾结点和头节点，这样也可以避免使用二级指针增加难度。

2.3.2队列的初始化

初始化我们先把所有内容设置成NULL或0即可

void QueueInit(Que* pq)
{
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

 2.3.3入队

入队其实就是链表中的尾插！！！

void QueuePush(Que* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		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++;
}

我们一定要记得将记录首尾的结构体进行赋值，分情况进行，不要忘记更新哦！！！

2.3.4出队

出队就是链表中的头删

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

 我们一定要注意当删到只有一个内容节点时，要处理尾指针指向NULL。

2.3.5获取对头元素

只需要判断队列存指针正确且不为空，直接返回head指向的data即可。 QueueEmpty函数就是判断队列是否为空的函数，在后面有代码展示！！！

QDataType QueueFront(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return ps->head->data;
}

2.3.6获取对尾元素

尾元素获取与首元素基本相同。

QDataType QueueBack(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return ps->tail->data;
}

2.3.7判断是否为空

bool QueueEmpty(Que* pq)
{
	assert(pq);
	return ps->tail == NULL;
}

2.3.8队列销毁

一定不要忘记创建的存放头尾节点的指针结构体，也要将它们置空

void QueueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = ps->tail = NULL;
	pq->size = 0;
}

3.拓展内容

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

  

栈、队列、顺序表、链表都是相似但不同的数据结构，我们在学习时一定要了解其中的差异，这样才能在以后更好的应用！！！

以上就是本节全部内容，感谢大家耐心观看，你们的三连支持是博主最大创作动力。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Python“牵手”拼多多商品评论数据采集方法，拼多多API申请步骤说明

Python“牵手”拼多多商品评论数据采集方法，拼多多API申请步骤说明

拼多多平台API接口是为开发电商类应用程序而设计的一套完整的、跨浏览器、跨平台的接口规范&#xff0c;拼多多API接口是指通过编程的方式&#xff0c;让开发者能够通过HTTP协议直接访问拼多多平台的数据&#xff0c;包括商品信息、店铺信息、物流信息&#xff0c;评论数据等&a…
阅读更多...
无涯教程-Perl - splice函数

无涯教程-Perl - splice函数

描述 此函数从LENGTH元素的OFFSET元素中删除ARRAY元素,如果指定,则用LIST替换删除的元素。如果省略LENGTH,则从OFFSET开始删除所有内容。 语法 以下是此函数的简单语法- splice ARRAY, OFFSET, LENGTH, LISTsplice ARRAY, OFFSET, LENGTHsplice ARRAY, OFFSET返回值 该函数…
阅读更多...
2024浙大MBA/MEM/MPA四个月冲刺备考策略

2024浙大MBA/MEM/MPA四个月冲刺备考策略

近期收到很多考生的咨询&#xff1a;距离联考就仅剩四个多月的时间&#xff0c;这个管理类联考的难度如何&#xff1f;主要考些什么内容&#xff1f;现在才开始备考还有希望上岸浙大吗&#xff1f;是不是要等到明年在开始备考比较合适&#xff1f;那么今天在这里小立老师就跟大…
阅读更多...
管家婆中了mallox勒索病毒该怎么办？勒索病毒解密数据恢复

管家婆中了mallox勒索病毒该怎么办？勒索病毒解密数据恢复

管家婆是很多中小企业使用的财务软件&#xff0c;它的性价比高、操作简单&#xff0c;适用行业也非常广。这也是它能够赢得众多中小企业主欢迎的原因之一。俗话说的好&#xff0c;木秀于林风必摧之&#xff0c;正是因为管家婆有着非常庞大的使用群体&#xff0c;所以它才成为了…
阅读更多...
Stable Diffusion训练Lora模型

Stable Diffusion训练Lora模型

以下内容参考:https://www.bilibili.com/video/BV1Qk4y1E7nv/?spm_id_from333.337.search-card.all.click&vd_source3969f30b089463e19db0cc5e8fe4583a 1、训练Lora的2个重点步骤 第一步&#xff0c;准备训练要使用的图片&#xff0c;即优质的图片 第二部&#xff0c;为…
阅读更多...
【vue3】对axios进行封装，方便更改路由并且可以改成局域网ip访问（附代码）

【vue3】对axios进行封装，方便更改路由并且可以改成局域网ip访问（附代码）

对axios封装是在main.js里面进行封装&#xff0c;因为main.js是一个vue项目的入口 步骤&#xff1a; 在1处创建一个axios实例为http&#xff0c;baseURL是基础地址&#xff08;根据自己的需求写&#xff09;&#xff0c;写了这个在vue界面调用后端接口时只用在post请求处写路由…
阅读更多...
【深入解析：数据结构栈的魅力与应用】

【深入解析：数据结构栈的魅力与应用】

本章重点 栈的概念及结构 栈的实现方式 数组实现栈接口 栈面试题目 概念选择题 一、栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶&#xff0c;另一端称为栈底。栈中的数…
阅读更多...
Masterstudy主题 - 用于线上教育、在线学习和在线课程的LMS WordPress主题

Masterstudy主题 - 用于线上教育、在线学习和在线课程的LMS WordPress主题

Masterstudy主题是每个人的最佳选择&#xff01;它是一个完整的线上教育WordPress主题&#xff0c;适合所有想要创建在线课程、辅导和语言中心、在线学习平台并在全球范围内传播知识的人。这是一个完美的教育主题&#xff0c;旨在满足学习行业的需求。 网址&#xff1a;Master…
阅读更多...
【数据结构练习】单链表OJ题（一）

【数据结构练习】单链表OJ题（一）

目录 一、移除链表元素思路1&#xff1a;思路2&#xff1a; 二、反转链表三、链表的中间节点四、链表中倒数第k个节点五、回文结构六、合并两个有序链表 一、移除链表元素 题目&#xff1a; 思路1&#xff1a; 在原来的链表上进行修改&#xff0c;节点的数据是val的删除&am…
阅读更多...
axios 各种方式的请求 示例

axios 各种方式的请求 示例

GET请求 示例一&#xff1a; 服务端代码 GetMapping("/f11") public String f11(Integer pageNum, Integer pageSize) {return pageNum " : " pageSize; }前端代码 <template><div class"home"><button click"getFun1…
阅读更多...
时序预测 | MATLAB实现ELM极限学习机时间序列预测（多指标、相关图）

时序预测 | MATLAB实现ELM极限学习机时间序列预测（多指标、相关图）

时序预测 | MATLAB实现ELM极限学习机时间序列预测（多指标、相关图） 目录 时序预测 | MATLAB实现ELM极限学习机时间序列预测（多指标、相关图）效果一览基本介绍程序设计学习总结参考资料效果一览 基本介绍 时序预测 | MATLAB实现ELM极
阅读更多...
linux部署clickhouse(单机)

linux部署clickhouse(单机)

一、下载安装 1.1、下载地址 阿里巴巴开源镜像站-OPSX镜像站-阿里云开发者社区阿里巴巴开源镜像站&#xff0c;免费提供Linux镜像下载服务&#xff0c;拥有Ubuntu、CentOS、Deepin、MongoDB、Apache、Maven、Composer等多种开源软件镜像源&#xff0c;此外还提供域名解析DNS、…
阅读更多...
Android企业项目开发实训室建设方案

Android企业项目开发实训室建设方案

一 、系统概述 Android企业项目开发作为新一代信息技术的重点和促进信息消费的核心产业&#xff0c;已成为我国转变信息服务业的发展新热点&#xff1a;成为信息通信领域发展最快、市场潜力最大的业务领域。互联网尤其是移动互联网&#xff0c;以其巨大的信息交换能力和快速渗透…
阅读更多...
JVM——JDK 监控和故障处理工具总结

JVM——JDK 监控和故障处理工具总结

文章目录 JDK 命令行工具jps:查看所有 Java 进程jstat: 监视虚拟机各种运行状态信息 jinfo: 实时地查看和调整虚拟机各项参数jmap:生成堆转储快照**jhat**: 分析 heapdump 文件**jstack** :生成虚拟机当前时刻的线程快照 JDK 可视化分析工具JConsole:Java 监视与管理控制台连接…
阅读更多...
Flink内核源码解析--Flink中重要的工作组件和机制

Flink内核源码解析--Flink中重要的工作组件和机制

Flink内核源码 1、掌握Flink应用程序抽象2、掌握Flink核心组件整体架构抽象3、掌握Flink Job三种运行模式4、理解Flink RPC网络通信框架Akka详解5、理解TaskManager为例子&#xff0c;分析Flink封装Akka Actor的方法和整个调用流程6、理解Flink高可用服务HighAvailabilityServ…
阅读更多...
【二分查找篇】速刷牛客TOP101 高效刷题指南

【二分查找篇】速刷牛客TOP101 高效刷题指南

文章目录 17、BM17 二分查找-I18、BM18 二维数组中的查找19、BM19 寻找峰值20、BM20 数组中的逆序对21、BM21 旋转数组的最小数字22、BM22 比较版本号23、BM23 二叉树的前序遍历 17、BM17 二分查找-I 思路步骤&#xff1a; step 1&#xff1a;从数组首尾开始&#xff0c;每次取…
阅读更多...
微服务中间件--分布式事务

微服务中间件--分布式事务

分布式事务 a.理论基础1) CAP定理2) BASE理论 b.Seata1) XA模式1.a) 实现XA模式 2) AT模式3) TCC模式3.a) 代码实现 4) Saga模式5) 四种模式对比6) TC的异地多机房容灾架构 a.理论基础 1) CAP定理 分布式系统有三个指标&#xff1a; Consistency&#xff08;一致性&#xff…
阅读更多...
GRPC 链接 NODE 和 GOLANG

GRPC 链接 NODE 和 GOLANG

GRPC 链接 NODE 和 GOLANG GRPC 了解 什么是GRPC gRPC 采用了 Protocol Buffers 作为数据序列化和反序列化的协议&#xff0c;可以更快速地传输数据&#xff0c;并支持多种编程语言的跨平台使用gRPC 提供“统一水平层”来对此类问题进行抽象化。 开发人员在本机平台中编写专…
阅读更多...
使用本地电脑搭建可以远程访问的SFTP服务器

使用本地电脑搭建可以远程访问的SFTP服务器

文章目录 1. 搭建SFTP服务器1.1 下载 freesshd 服务器软件1.3 启动SFTP服务1.4 添加用户1.5 保存所有配置 2. 安装SFTP客户端FileZilla测试2.1 配置一个本地SFTP站点2.2 内网连接测试成功 3. 使用cpolar内网穿透3.1 创建SFTP隧道3.2 查看在线隧道列表 4. 使用SFTP客户端&#x…
阅读更多...
WXML中的条件语句

WXML中的条件语句

wx:if 和 hidden 的使用 1.在js中定义数据 Page({ data:{ type:1,flag: false}, }) 2.在wxml中使用wx:if 和 hidden&#xff0c; block用于包装组件(不会渲染为任何标签) <!-- 条件渲染 --><view wx:if"{{type 1}}">男</view><view wx:elif…
阅读更多...
最新文章

Copyright @ 2022~2023