OJ题目【栈和队列】

题目导入

栈:

  • 题目一:有效的括号
  • 题目二:用栈实现队列

队列

  • 题目:实现循环队列

题目一 有效的括号

题目要求

给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

下图为力扣的示例
在这里插入图片描述
题目代码原型

bool isValid(char* s) {//The code is written here
}

这题就很适合用栈来实现,当是左括号的时候就入栈,如果是右括号就与栈顶的左括号进行对比,如果匹配成功就将栈顶的左括号给Pop掉
创建栈

    Stack st;StackInit(&st);

入栈函数:

 if (*s == '(' || *s == '[' || *s == '{'){StackPush(&st, *s);}

但是匹配了没有意义,因为栈内可能还有多个元素,所以我们要判断不匹配的情况(不匹配可以直接出结果)
代码如下:

 else{STDataType tmp = StackTop(&st);StackPop(&st);if ((tmp == '(' && *s != ')') ||(tmp == '[' && *s != ']') ||(tmp == '{' && *s != '}')){StackDestroy(&st);return false;}}

这是判断一次,题目的s不可能就这这么点字符,所以我们要使用循环

    while (*s){if (*s == '(' || *s == '[' || *s == '{'){StackPush(&st, *s);}else{STDataType tmp = StackTop(&st);StackPop(&st);if ((tmp == '(' && *s != ')') ||(tmp == '[' && *s != ']') ||(tmp == '{' && *s != '}')){StackDestroy(&st);return false;}}s++;}

循环走出来了,就代表s已经走到\0了,这时候我们就需要判断栈内是否还有元素,如果还有就代表s并不是一个有效的字符串(有效字符串需满足:每个右括号都有一个对应的相同类型的左括号。)
代码如下

    if (!StackEmpty(&st))//栈为非空,还有元素{StackDestroy(&st);return false;}StackDestroy(&st);return true;

这样大体就写完了,但是这还有个问题:s的第一个元素就是右括号该怎么办?
其实很简单,当s的第一个元素就是右括号的时候,就代表s并不是一个有效的字符串,并且这时候的栈是空的,所以我们只需要对栈进行判空操作就好了。

    while (*s){if (*s == '(' || *s == '[' || *s == '{'){StackPush(&st, *s);}else{if (StackEmpty(&st))//当s的第一个元素就是右括号{StackDestroy(&st);return false;}STDataType tmp = StackTop(&st);StackPop(&st);if ((tmp == '(' && *s != ')') ||(tmp == '[' && *s != ']') ||(tmp == '{' && *s != '}')){StackDestroy(&st);return false;}}

完整代码:

bool isValid(char* s) {Stack st;//创建栈StackInit(&st);while (*s){if (*s == '(' || *s == '[' || *s == '{'){StackPush(&st, *s);}else{if (StackEmpty(&st)){StackDestroy(&st);return false;}//方法一STDataType tmp = StackTop(&st);StackPop(&st);if ((tmp == '(' && *s != ')') ||(tmp == '[' && *s != ']') ||(tmp == '{' && *s != '}')){StackDestroy(&st);return false;}//方法二(任选其一)if ((StackTop(&st) == '(' && *s != ')') ||(StackTop(&st) == '[' && *s != ']') ||(StackTop(&st) == '{' && *s != '}')){StackDestroy(&st);return false;}else{StackPop(&st);}}s++;}if (!StackEmpty(&st)){StackDestroy(&st);return false;}StackDestroy(&st);return true;
}

在函数结束先,将自己在该函数开辟的空间个释放掉,这是一个好习惯。

题目二 用栈实现队列

在这里插入图片描述
队列是先进先出,栈是先进后出,这题我们就需要使用两个栈来实现了。
先入栈的元素是在栈底,而先出的元素是在栈顶,所以我们把有元素的栈里面的元素入到没有元素的栈里面,就能完成队列的出队操作,类似下图
在这里插入图片描述

我们入队列(用栈实现的)是入到有元素的栈里面,因为我将数据入到非空栈的时候是入到栈顶的,当我要进行出队列的时候,是将栈下标一及以后的元素入到空栈,再将非空栈的栈底元素Pop掉
在这里插入图片描述

peek的要求是返回队列开头的元素,这样我们直接返回非空栈中下标为0的元素。

完整代码

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top;		// 栈顶int _capacity;  // 容量 
}Stack;// 初始化栈 
void StackInit(Stack* ps)
{assert(ps);ps->_a = NULL;ps->_top = 0;ps->_capacity = 0;
}// 入栈 
void StackPush(Stack* ps, STDataType data)
{if (ps->_top == ps->_capacity){int _NewCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;STDataType* _tmp = (STDataType*)realloc(ps->_a, _NewCapacity * sizeof(STDataType));ps->_a = _tmp;ps->_capacity = _NewCapacity;}ps->_a[ps->_top++] = data;
}// 出栈 
void StackPop(Stack* ps)
{assert(ps && ps->_top > 0);ps->_top--;
}// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(ps && ps->_top > 0);return ps->_a[ps->_top - 1];
}// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{assert(ps && ps->_top > 0);return ps->_top;
}// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{return (ps->_top == 0);
}// 销毁栈 
void StackDestroy(Stack* ps)
{free(ps->_a);ps->_a = NULL;ps->_top = ps->_capacity = 0;
}typedef struct {Stack s1;Stack s2;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&(obj->s1));StackInit(&(obj->s2));return obj;
}void myQueuePush(MyQueue* obj, int x) {if(!StackEmpty(&obj->s1)){StackPush(&obj->s1,x);}else{StackPush(&obj->s2,x);}}int myQueuePop(MyQueue* obj) {//假设法Stack* Empty = &obj->s1;Stack* NotEmpty = &obj->s2;if(!StackEmpty(Empty)){Empty = &obj->s2;NotEmpty = &obj->s1;}int top = StackSize(NotEmpty);int tmp = 1;while(tmp != top){StackPush(Empty,NotEmpty->_a[tmp++]);StackPop(NotEmpty);}int val = StackTop(NotEmpty);StackPop(NotEmpty);return val;
}int myQueuePeek(MyQueue* obj)
{if(!StackEmpty(&obj->s1)){return obj->s1._a[0];}else{return obj->s2._a[0];}}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}void myQueueFree(MyQueue* obj) {StackDestroy(&obj->s1);StackDestroy(&obj->s2);free(obj);obj = NULL;
}

队列

题目:实现循环队列

在这里插入图片描述
循环队列可以用数组和链表来实现,本文是用数组实现。
可能有很多人看到题目就设计一个数组,定一个headtailhead或者tail到了数组结尾的时候,就绕回到数组开头。
在这里插入图片描述

但是这里有个问题:我的判空和判满该这么区分呢?
判空很简单,判断head是否等于tail,是的话就是空。但是,在这个数组中,判满的逻辑也是判断head是否等于tail。
这种情况也别称为假溢出。

这时候我们就有两种方法来解决。

  • 第一种:使用一个size来记录,数组元素的个数,如果等于数组长度就是满,如果等于零就是空
  • 第二种:在开辟数组的时候多开一个空间,这个空间在逻辑上是不存放数组的,这里的不存放是说在存放数据的时候,就是有某块空间不存放数据,并不是多开的那个空间不存放数据。如下图在这里插入图片描述

如图所示,当判满成立的时候,就是有某块空间不存放数据,上图tail所指向的空间,那里面的元素已经被我Pop掉了,已经不认为是队列内的元素了
所以方法二也可以将判满和判空给区分开来

判满:看tail+1是否等于head(当然要解决回绕的问题)
判空就还是看tail是否等于head。

本文使用的是第二种方法。

循环队列的创建(myCircularQueueCreate)

假设队列的长度为k

typedef struct {int * _a;int _head;int _tail;int _k; //该队列的长度
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {//先开辟队列MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//再开辟队列的数组部分obj->_a = (int*)malloc(sizeof(int)* (k+1));//多开一个空间obj->_head = obj->_tail = 0;obj->_k = k;//将队列长度k赋值给我的_kreturn obj;
}

注:因为力扣上的动态开辟基本不会报错,所以可以省略判断开辟成功的步骤(在日常敲代码的时候还是判断比较好)

解决回绕问题:

当我的tail等于k+1的时候,直接取模就好了
当然也可以暴力一点,不管tail的值,直接取模

obj->_tail %= obj->_k+1;

所以我们就可以直接写判空和判满的代码了:

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->_head == obj->_tail;
}//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->_tail+1) % (obj->k+1) == obj->_head;
}

入队列(myCircularQueueEnQueue)

题目代码:

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {}

题目对这段代码的要求: 向循环队列插入一个元素。如果成功插入则返回真。

那么插入不成功就返回假(队列满了就不能插入了)
所以可以直接调用判满函数

if(myCircularQueueIsFull(obj))
{return false;
}

如果没满,就继续插入,然后解决回绕问题,也可以使用暴力方法(不管tail的大小,直接%上k+1)

//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->_a[obj->_tail++] = value;//方法一(暴力)obj->_tail %= (obj->_k+1);//方法二(判断)if(obj->_tail == obj->_k+1){obj->_tail = 0;}return true;
}

出队列(myCircularQueueDeQueue)

题目代码:

//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {}

题目对这段代码的要求:从循环队列中删除一个元素。如果成功删除则返回真。

那么删除不成功就返回假(队列空了就不能插入了)
所以可以直接调用判空函数

    if(myCircularQueueIsEmpty(obj)){return false;}

因为队列是先进先出(FIFO),所以我们继续出队列的时候并不是对tail操作,而是对head操作。
出队列的时候直接++head就好了(当然也要解决回绕问题)。
解决回绕问题和入队列的操作是一样的。

//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->_head++;obj->_head %= (obj->_k + 1);return true;}

取队头元素(myCircularQueueFront)

题目对这个函数的要求:从队首获取元素。如果队列为空,返回 -1 。
直接返回head位置的元素就好了

//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->_a[obj->_head];
}

取队尾元素(myCircularQueueRear)

题目对这个函数的要求:获取队尾元素。如果队列为空,返回 -1 。

注意:我这里的tail其实是指向待插入数据的空间,也就是最后一个元素的下一个空间。
所以我们返回尾元素,其实是返回tail的前一个空间。
一般情况下只需要返回tail - 1就可以了,但是,有一种特殊情况,就是当入完队列后我的tail进行了回绕,这时候tail0,我这时返回tail - 1的元素就会造成越界。在这里插入图片描述
有两种方法处理

  • 第一种:判断tail是否等于0,是的话返回下标为 k 个元素。
  • 第二种:先tail-1然后加上k+1%k+1,这种方法不需要判断tail,可以直接返回值。
//第一种
return obj->_a[obj->_tail == 0 ? k ; obj->_tail-1];//第二种
return obj->_a[(obj->_tail-1 + obj->_k+1) %  (obj->_k+1)]

第二种方法解决正常情况
将tail=3带入,k=5带入

((3-1) + (5+1)) % (5+1)
= (2+6) % 6
= 8 % 6
= 2

第二种方法解决特殊情况
将tail=0带入,k=5带入

((0-1) + (5+1)) % (5+1)
= (-1+6) % 6
= 5 % 6
= 5

所以第二种也可以写成这样

return obj->_a[(obj->_tail + obj->_k) %  (obj->_k+1)]// -1 和 1 抵消了

函数代码如下

//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->_a[(obj->_tail - 1 + obj->_k + 1) % (obj->_k + 1)];
}

销毁循环队列(myCircularQueueFree)

从内到外释放,先释放内部,再释放外部。

//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->_a);obj->_a = NULL;obj->_head = obj->_tail = obj->_k = 0;free(obj);
}

完整代码

typedef struct {int * _a;int _head;int _tail;int _k; 
} MyCircularQueue;//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->_a = (int*)malloc(sizeof(int)* (k+1));obj->_head = obj->_tail = 0;obj->_k = k;return obj;
}//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->_head == obj->_tail;
}//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->_tail+1) % (obj->_k + 1) == obj->_head;
}//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->_a[obj->_tail++] = value;//obj->_tail %= (obj->_k+1);if(obj->_tail == obj->_k+1){obj->_tail = 0;}return true;
}//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->_head++;obj->_head %= (obj->_k + 1);return true;}//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->_a[obj->_head];
}//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->_a[(obj->_tail - 1 + obj->_k + 1) % (obj->_k + 1)];
}//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->_a);obj->_a = NULL;obj->_head = obj->_tail = obj->_k = 0;free(obj);
}

结语

最后感谢您能阅读完此片文章,如果有任何建议或纠正欢迎在评论区留言,也可以前往我的主页看更多好文哦(点击此处跳转到主页)。
如果您认为这篇文章对您有所收获,点一个小小的赞就是我创作的巨大动力,谢谢!!!

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

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

相关文章

信号稳定,性能卓越!德思特礁鲨系列MiMo天线正式发布!

作者介绍 礁鲨系列天线,以其独特的外观设计和强大的性能,成为德思特Panorama智能天线家族的最新成员。这款天线不仅稳定提供5G、WIFI和GNSS信号,更能在各类复杂环境中展现出卓越的性能。它的设计灵感来源于海洋中的礁鲨,象征着力量…

Julia编程11:变量作用域 Scope of Variables

There are two main types of scopes in Julia, global* scope* and local* scope*. Julia有全局变量作用域和局部变量作用域,函数或者一些结构体、循环体如for等是否内部是局部环境可以参照下表。 ConstructScope typeAllowed withinmodule, baremoduleglobalglo…

边缘计算网关:企业数字化转型的重要支撑-天拓四方

在数字化浪潮席卷全球的今天,企业对于数据处理和传输的需求日益增强。然而,传统的数据处理模式往往依赖于中心化的数据中心,这种方式在处理大量数据时存在延迟高、成本高、安全性差等问题。数据量的激增和实时性要求的提高,使得传…

视频汇聚EasyCVR平台视图库GA/T 1400协议与GB/T 28181协议的区别

在公安和公共安全领域,视频图像信息的应用日益广泛,尤其是在监控、安防和应急指挥等方面。为了实现视频信息的有效传输、接收和处理,GA/T 1400和GB/T 28181这两个协议被广泛应用。虽然两者都服务于视频信息处理的目的,但它们在实际…

智能合约引领:探索Web3的商业革新之路

随着区块链技术的迅速发展,智能合约作为其重要应用之一,正在逐步改变着商业世界的格局。Web3作为下一代互联网的代表,正引领着智能合约在商业领域的广泛应用和创新。本文将深入探讨智能合约在Web3中的作用,以及智能合约如何引领着…

Vue总结

介绍 Vue 是一套前端框架,免除原生IavaScript中的DOM操作,简化书写。基于MVVM(Model-View-ViewModel)思想,实现数据的双向绑定,将编程的关注点放在数据上。框架:是一个半成品软件,是一套可重用的、通用的、软件基础代…

免费,Scratch蓝桥杯比赛历年真题--第15届蓝桥杯STEMA真题-2024年3月份(含答案解析和代码)

第15届蓝桥杯STEMA真题-2024年3月份 一、单选题 答案&#xff1a;D 解析&#xff1a;y坐标正值表示上&#xff0c;负值表示下&#xff0c;故答案为D。 答案&#xff1a;C 解析&#xff1a;18<25为真&#xff0c;或关系表示一真即为真&#xff0c;故答案为C。 答案&#xff…

Excel 将分组头信息填入组内明细行

Excel由多个纵向的分组表组成&#xff0c;组之间由空白行隔开&#xff0c;每组第1、2行的第2格是分组表头&#xff0c;第3行是列头&#xff0c;第1列和第6列数据是空白的&#xff1a; ABCDEF1ATLANTIC SPIRIT2Looe3VesselSpeciesSizeKgDateLocation4POLLACK22.523/04/20245POL…

音视频开发13 FFmpeg 音频 相关格式分析 -- AAC ADTS格式分析

这一节&#xff0c;我们学习常用的音频的格式 AAC&#xff0c;重点是掌握 AAC的传输格式 ADTS 头部的信息&#xff0c;目的是 &#xff1a; 当音频数据有问题的时候&#xff0c;如果是AAC的编码&#xff0c;在分析 头部信息的时候能够根据头部信息 判断问题是否出现在 头部。 A…

京东笔试-校招

2022京东数据分析笔试&#xff08;0821&#xff09; 一、选择题&#xff1a;30道 1.解决数据不平衡的方法主要有&#xff08;pca&#xff1f;&#xff09; 2.等频&#xff08;等宽&#xff09;划分问题 3.参数估计&#xff1a;矩估计与极大似然估计的用法&#xff0c;问题分…

python之生成xmind

今天为啥要说这个呢&#xff0c;因为前几天做接口测试&#xff0c;还要写测试用例&#xff0c;我觉得麻烦&#xff0c;所以我就用了python里面xmind的插件。自动生成了测试用例&#xff0c;数据来源是json。 &#x1f366; 第一步安装 pip install xmind &#x1f366; 第二…

测绘GIS和遥感领域比较好的公众号有哪些

测绘GIS和遥感领域&#xff0c;微信公众号作为信息传播和知识分享的重要渠道&#xff0c;为从业者提供了一个快速获取行业动态、技术进展和职业发展机会的平台。分享一些在测绘GIS和遥感领域表现突出的公众号推荐&#xff1a; 1. 慧天地&#xff1a;慧天地是一个知名的测绘公众…

纯js仿淘宝多图片封面图插件模板/带视频,带放大镜,带前后端完整代码PHP

功能预览,他依赖jq插件,请自已引入 类似这样 <script type"text/javascript" src"/Application/Admin/Static/js/jquery-2.0.3.min.js"></script>一,前端模板代码 <!--多图功能--><style> charset "utf-8"; .wrap_imgs…

【设计模式深度剖析】【1】【行为型】【模板方法模式】| 以烹饪过程为例加深理解

&#x1f448;️上一篇:结构型设计模式对比 文章目录 模板方法模式定义英文原话直译如何理解呢&#xff1f; 2个角色类图代码示例 应用优点缺点使用场景 示例解析&#xff1a;以烹饪过程为例类图代码示例 模板方法模式 模板方法模式&#xff08;Template Method Pattern&…

MySQL 关键特性一:插入缓冲、双写缓冲

前言 ​ 本文主要介绍 mysql 的几大特性之几&#xff0c;如&#xff1a;双写缓冲和插入缓存。 双写缓冲 基本概念 ​ 双写缓冲&#xff08;doublewrite buffer&#xff09;是MySQL/InnoDB中用于支持原子页面更新的一种机制。在传统的数据库系统中&#xff0c;为了保证数据的…

计网ppt标黄知识点整理第(4)章节——谢希仁版本、期末复习自用

路由器&#xff1a;查找转发表&#xff0c;转发分组。 IP网的意义&#xff1a;当互联网上的主机进行通信时&#xff0c;就好像在一个网络上通信一样&#xff0c;看不见互连的各具体的网络异构细节。如果在这种覆盖全球的 IP 网的上层使用 TCP 协议&#xff0c;那么就…

VB.net实战(VSTO):Excel插件的安装与卸载

1. 安装 1.1编程环境&#xff1a;Visual Studio 2022 1.2创建新项目&#xff1a; 1.3 加入一行测试程序&#xff1a;MsgBox&#xff08;“hello”&#xff09;&#xff0c;点击启动&#xff0c;确认可以弹窗 1.4 点击发布 1.5 找到安装程序&#xff0c;点击安装。打开Excel程…

radsystems教程的基本使用之时间字段范围检索

前言&#xff1a; 根据之前的文章&#xff0c;我相信大部分人都能够做到&#xff0c;页面的数据展示&#xff0c;基本的查询功能。我们知道的是这个数值范围检索是非常容易实现的&#xff0c;但是这个时间字段范围检索并不是很如愿。 细心的朋友会发现每次用Date Fied这个组件…

Java18+​App端采用uniapp+开发工具 idea hbuilder智能上门家政系统源码,一站式家政服务平台开发家政服务

Java18​App端采用uniapp开发工具 idea hbuilder智能上门家政系统源码&#xff0c;一站式家政服务平台开发 家政服务 家政服务是一个专为家政服务人员设计的平台&#xff0c;该平台旨在提供便捷、高效的工作机会&#xff0c;同时确保服务质量和客户体验。 以下是关于家政服务师…

【HarmonyOS】应用振动效果实现

一、问题背景&#xff1a; 应用在强提醒场景下&#xff0c;一般会有马达振动的效果&#xff0c;提示用户注意力的关注。 比如消息提醒&#xff0c;扫码提示&#xff0c;删除键确认提示等。 针对高定制化或者固定的振动方式&#xff0c;我们需要有不同的方案实现&#xff0c;马…