栈和队列的实现以及OJ题讲解

💓博主个人主页:不是笨小孩👀
⏩专栏分类:数据结构与算法👀 刷题专栏👀 C语言👀
🚚代码仓库:笨小孩的代码库👀
⏩社区:不是笨小孩👀
🌹欢迎大家三连关注,一起学习,一起进步!!💓

在这里插入图片描述

栈以及OJ

  • 栈的概念以及结构
    • 栈的概念
    • 栈的结构
  • 栈的实现
    • 栈的接口
    • 各个接口的实现
  • 队列的概念和结构
    • 队列的结构
  • 队列的实现
    • 队列的接口
    • 接口的实现
  • 有效的括号

栈的概念以及结构

栈的概念

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

栈的结构

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

在这里插入图片描述

在这里插入图片描述
知道了栈的概念以及结构,接下来我们来实现一下栈。

栈的实现

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

在这里插入图片描述
结构:

typedef int STDateType;typedef struct Stack
{STDateType* arr;int top;int capacity;
}Stack;

栈的接口

// 初始化栈
void StackInit(Stack* ps);// 入栈
void StackPush(Stack* ps, STDateType x);// 出栈
void StackPop(Stack* ps);// 获取栈顶元素
STDateType StackTop(Stack* ps);// 获取栈中有效元素个数
int StackSize(Stack* ps);// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool StackEmpty(Stack* ps);// 销毁栈
void StackDestroy(Stack* ps);

各个接口的实现

有了顺序表的基础,栈与其相比就太简单了。大家直接看代码就知道了:

// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}// 入栈
void StackPush(Stack* ps, STDateType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDateType* pa = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType));if (ps == NULL){perror("realloc fail");exit(-1);}ps->arr = pa;ps->capacity = newcapacity;}ps->arr[ps->top] = x;ps->top++;
}// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps ->top > 0);ps->top--;
}// 获取栈顶元素
STDateType StackTop(Stack* ps)
{assert(ps);return ps->arr[ps->top - 1];
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}// 检测栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0 ? true : false;
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}

队列的概念和结构

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

在这里插入图片描述

队列的结构

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

typedef int QDataType;typedef struct QNode
{QDataType date;struct QNode* next;
}QNode;typedef struct Queue
{QNode* head;//记录尾,方便入队QNode* tail;//记录队列里有效数据的个数int size;
}Queue;

队列的实现

队列的接口

//初始化队列
void QueueInit(Queue* pq);//入队列
void QueuePush(Queue* pq, QDataType x);//出队列
void QueuePop(Queue* pq);//获取队头的元素
QDataType QueueFront(Queue* pq);//获取队头尾的元素
QDataType QueueBack(Queue* pq);//获取队列中有效数据的个数
int QueueSize(Queue* pq);//判断队列是否为空
bool QueueEmpty(Queue* pq);//销毁队列
void QueuDestroy(Queue* pq);

接口的实现

//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->date = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head);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--;
}//获取队头的元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->date;
}//获取队头尾的元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->date;
}//获取队列中有效数据的个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}//销毁队列
void QueuDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}
}

有效的括号

在这里插入图片描述

这个题放在这里讲,它一定是需要用到栈的,但是由于我们的C语言没有栈,所以我们写这个题时需要手写一个栈,我们这里说一下思路,括号匹配,我们可以将左括号入栈,然后碰到右括号然后保存栈顶的元素,然后出栈,然后看是否匹配,匹配的情况我们不关心,但是只要不匹配我们就返回false,但是每次是右括号是我们都要判断是不是空栈,如果是空栈,就一定不匹配,这是我们要返回false,等字符串遍历完一遍后,如果不是空栈,就一定不匹配,返回false,但是如果字符串遍历完了,是空栈,就一定匹配,返回true,注意在返回之前一定要销毁栈。

代码:

typedef char STDateType;typedef struct Stack
{STDateType* arr;int top;int capacity;
}Stack;
// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}// 入栈
void StackPush(Stack* ps, STDateType x)
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDateType* pa = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType));if (ps == NULL){perror("realloc fail");exit(-1);}ps->arr = pa;ps->capacity = newcapacity;}ps->arr[ps->top] = x;ps->top++;
}// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps ->top > 0);ps->top--;
}// 获取栈顶元素
STDateType StackTop(Stack* ps)
{assert(ps);return ps->arr[ps->top - 1];
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->top;
}// 检测栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0 ? true : false;
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = 0;ps->top = 0;
}bool isValid(char * s)
{Stack st;StackInit(&st);char top = 0;while(*s){if(*s=='('||*s=='{'||*s=='['){StackPush(&st,*s);}else{//数量不匹配if(StackEmpty(&st)){StackDestroy(&st);return false;}else{top = StackTop(&st);StackPop(&st);//判断是否匹配if((top=='['&&*s!=']')||top=='('&&*s!=')'||top=='{'&&*s!='}'){StackDestroy(&st);return false;}}}*s++;}//判断数量是否匹配if(!StackEmpty(&st)){StackDestroy(&st);return false;}StackDestroy(&st);return true;
}

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

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

相关文章

【阵列信号处理】空间匹配滤波器、锥形/非锥形最佳波束成形器、样本矩阵反演 (SMI) 研究(Matlab代码实现)

💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…

回归预测 | MATLAB实现POA-CNN-LSTM鹈鹕算法优化卷积长短期记忆神经网络多输入单输出回归预测

回归预测 | MATLAB实现POA-CNN-LSTM鹈鹕算法优化卷积长短期记忆神经网络多输入单输出回归预测 目录 回归预测 | MATLAB实现POA-CNN-LSTM鹈鹕算法优化卷积长短期记忆神经网络多输入单输出回归预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 MATLAB实现POA-CNN…

Michael.W基于Foundry精读Openzeppelin第20期——EnumerableMap.sol

0. 版本 [openzeppelin]:v4.8.3,[forge-std]:v1.5.6 0.1 EnumerableMap.sol Github: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v4.8.3/contracts/utils/structs/EnumerableMap.sol EnumerableMap库提供了Bytes32ToB…

快速远程桌面控制公司电脑远程办公

文章目录 第一步第二步第三步 远程办公的概念很早就被提出来,但似乎并没有多少项目普及落实到实际应用层面,至少在前几年,远程办公距离我们仍然很遥远。但2019年末突如其来的疫情,着实打了大家一个措手不及。尽管国内最初的大面积…

新魔百和M301H_关于CW代工_JL(南传)代工_zn及sm代工区分及鸿蒙架构全网通卡刷包刷机教程

新魔百盒M301H_关于CW代工_JL(南传)代工_zn及sm代工区分及鸿蒙架构全网通卡刷包刷机教程 下载固件之前我们先区分下代工: 如盒子背面型号标签上带有ZN则视为兆能代工,如有CW或BYT则视为创维代工; 如有JL或南传则视为九联代工,ys…

机器学习---概述(一)

文章目录 1.人工智能、机器学习、深度学习2.机器学习的工作流程2.1 获取数据集2.2 数据基本处理2.3 特征工程2.3.1 特征提取2.3.2 特征预处理2.3.3 特征降维 2.4 机器学习2.5 模型评估 3.机器学习的算法分类3.1 监督学习3.1.1 回归问题3.1.2 分类问题 3.2 无监督学习3.3 半监督…

网络安全防火墙体验实验

网络拓扑 实验操作: 1、cloud配置 2、防火墙配置 [USG6000V1]int GigabitEthernet 0/0/0 [USG6000V1-GigabitEthernet0/0/0]ip add 192.168.200.100 24 打开防火墙的所有服务 [USG6000V1-GigabitEthernet0/0/0]service-manage all permit 3、进入图形化界面配置…

阿里云容器服务助力极氪荣获 FinOps 先锋实践者

作者:海迩 可信云评估是中国信息通信研究院下属的云计算服务和软件的专业评估体系,自 2013 年起历经十年发展,可信云服务评估体系已日臻成熟,成为政府支撑、行业规范、用户选型的重要参考。 2022 年 5 月国务院国资委制定印发《…

【周末闲谈】“深度学习”,人工智能也要学习?

个人主页:【😊个人主页】 系列专栏:【❤️周末闲谈】 系列目录 ✨第一周 二进制VS三进制 ✨第二周 文心一言,模仿还是超越? ✨第二周 畅想AR 文章目录 系列目录前言机器学习深度学习深度学习的三在种方法深度学习讲解…

Godot 4 源码分析 - Path2D与PathFollow2D

学习演示项目dodge_the_creeps,发现里面多了一个Path2D与PathFollow2D 研究GDScript代码发现,它主要用于随机生成Mob var mob_spawn_location get_node(^"MobPath/MobSpawnLocation")mob_spawn_location.progress randi()# Set the mobs dir…

RIP Bram Moolenaar

Grateful for your work on Vim and for the impact Vim has had on the world. Thank you for everything, Bram.

Kubespray-offline v2.21.0-1 下载 Kubespray v2.22.1 离线部署 kubernetes v1.25.6

文章目录 1. 目标2. 预备条件3. vcenter 创建虚拟机4. 系统初始化4.1 配置网卡4.2 配置主机名4.3 内核参数 5. 打快照6. 安装 git7. 配置科学8. 安装 docker9. 下载介质9.1 下载安装 docker 介质9.2 下载 kubespray-offline-ansible 介质9.3 下载 kubernetes 介质 10. 搬运介质…

浅析大数据时代下的视频技术发展趋势以及AI加持下视频场景应用

视频技术的发展可以追溯到19世纪初期的早期实验。到20世纪初期,电视技术的发明和普及促进了视频技术的进一步发展。 1)数字化:数字化技术的发明和发展使得视频技术更加先进。数字电视信号具有更高的清晰度和更大的带宽,可以更快地…

8.15锁的优化

1.锁升级(锁膨胀) 无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁 偏向锁:不是真的加锁,而是做了一个标记,如果有别的线程来竞争才会真的加锁,如果没有别的线程竞争就不会加锁. 轻量级锁:一个线程占领锁资源后,另一个线程通过自旋的方式反复确认锁是否被是否(这个过程比较…

重零搭建SpringSecurity +JWT

1、前期工作(创建父工程,导入依赖) 2、创建启动类 3、测试项目,启动后访问8080端口、hello看有没有页面 4、引入springSecurity依赖(重新启动,再访问/hello,会跳转到登录页面,用户名是 user,密码…

websocket

一、聊天室模式 0.效果图&#xff1a; 1.后端代码 1.1 导入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId><exclusions><exclusion><groupId>org.s…

windows部署springboot项目 jar项目 (带日志监听和开机自起脚本)

windows部署springboot项目 jar项目 &#xff08;带日志监听&#xff09; 1.把项目打包成jar包&#xff0c;本例演示打包后的jar文件名为demo.jar ———————————————— 2.需要装好java环境&#xff0c;配置好JAVA_HOME&#xff0c;CLASSPATH&#xff0c;PATH等…

vue-baidu-map-3x 使用记录

在 Vue3 TypeScript 项目中&#xff0c;为了采用 标签组件 的方式&#xff0c;使用百度地图组件&#xff0c;冲浪发现了一个开源库 ovo&#xff0c;很方便&#xff01;喜欢的朋友记得帮 原作者 点下 star ~ vue-baidu-map-3xbaidu-map的vue3/vue2版本&#xff08;支持v2.0、v…

【笔记】第94期-冯永吉-《湖仓集一体关键技术解读》-大数据百家讲坛-厦大数据库实验室主办20221022

https://www.bilibili.com/video/BV1714y1j7AU/?spm_id_from333.337.search-card.all.click&vd_sourcefa36a95b3c3fa4f32dd400f8cabddeaf

【es6】Promise实现

友情链接 关于promise的介绍&#xff0c;请看此篇水文 本篇文章只是介绍实现promise以及promise常用方法。 正文 Promise使用 let promise new Promise((resolve,reject)>{resolve(success); //这里如果是reject(fail) }); promise.then((res)>{console.log(res); …