栈和队列题目练习

本节小编选了两道题来加深对栈和队列的认识理解！

有效的括号

方法1：直接用栈的结构（动态数组）

本题可以用栈这个结构来解答，将'(','{','['  左括号压入栈中，然后取出栈顶元素与右括号')','}',']'匹配。不匹配的话，返回false,我们同时也要考虑空集的情况，即栈中元素为空，则返回false。

因为本题使用c语言写的，所以需要手撕栈的结构，可以运用上篇博客所写的栈的代码。

typedef  char  datatype;
typedef struct stack {datatype* a;int top;//栈顶int capacity;
}ST;
void STInit(ST* pst){assert(pst);pst->a = NULL;//top指向栈顶数据的下一个位置,可以理解为下标pst->top = 0;pst->capacity = 0;
}
void STDestory(ST* pst) {assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}
//容量检查
void Checkcapacity(ST* pst) {assert(pst);if (pst->top == pst->capacity) {int newcapacity = pst->capacity==0?4:pst->capacity * 2;datatype* temp = (datatype*)realloc(pst->a, newcapacity * sizeof(datatype));if (temp == NULL) {perror("relloc fail");return;}pst->a = temp;pst->capacity = newcapacity;}
}
//入栈和出栈
void STPush(ST* pst, datatype x) {assert(pst);Checkcapacity(pst);pst->a[pst->top] = x;pst->top++;
}
void STPop(ST* pst) {assert(pst);assert(pst->top>0);pst->top--;
}
//获取栈顶数据
datatype STTop(ST* pst) {assert(pst);assert(pst->top > 0);return pst->a[pst->top-1];
}
//判空
bool STEmpty(ST* pst) {assert(pst);return pst->top == 0;//表达式判断
}
//栈的数据个数
int STSize(ST* pst) {assert(pst);return pst->top;
}
bool isValid(char* s) {ST st;STInit(&st);while(*s){//左括号入栈if(*s=='('||*s=='{'||*s=='['){STPush(&st,*s);}else{//空集的情况，入栈结束后检查是否为空，if(STEmpty(&st)){STDestory(&st);return false;}char top=STTop(&st);STPop(&st);//通过括号不匹配的情况判断if((top=='('&& *s!=')') ||(top=='['&& *s!=']')||(top=='{'&& *s!='}')){STDestory(&st);return false;//STPop(&st);}}s++;}
//看最后是否栈为空，探讨左右括号数量不匹配的情况。bool ret=(STEmpty(&st));STDestory(&st);return ret;
}

方法2：通过数组模拟栈来实现

使用一个字符数组作为栈，通过使用top标记栈顶的位置来实现栈的操作。在遍历字符串的过程中，遇到左括号就将其压入栈中，遇到右括号就与栈顶元素进行匹配。如果匹配成功，则将栈顶元素出栈，否则返回false。最后，如果栈为空，则说明所有的括号都匹配成功，返回true；否则，返回false。

bool isValid(char* s) {char stack[10000];int top = -1;int len = strlen(s);for (int i = 0; i < len; i++) {if (s[i] == '(' || s[i] == '{' || s[i] == '[') {stack[++top] = s[i];} else {if (top == -1) {return false;}if ((s[i] == ')' && stack[top] == '(') || (s[i] == '}' && stack[top] == '{') || (s[i] == ']' && stack[top] == '[')) {top--;} else {return false;}}}return top == -1;
}

设计循环队列

方法1:使用动态数组

通过画图发现，当head==tail时，既是队列为空的条件，也是队列满的条件，所以我们可以通过增加一个空间来辅助判满，当tail+1=head时。还有另外一个方法，通过定义size变量，当size大小等于k时，也是队列满的时候。

在后续解决回绕的问题时，我们多次采用取模的方法，因为一个数除以比他大的数，取模后大小不变，当相等时，模为0，刚好回到起点处，完美的解决了回绕问题。

//循环队列先进先出
typedef struct {int *arr;int head;int tail;//指向尾下一个int k;
} MyCircularQueue;//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//多开辟一个空间obj->arr=(int*)malloc(sizeof(int)*(k+1));obj->head=0;obj->tail=0;obj->k=k;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//头尾相等时队列为空return (obj->head)==obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//当tail+1=head时，为满，通过取模解决回绕问题return((obj->tail+1)%(obj->k+1))==obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满的时候，返回falseif(myCircularQueueIsFull(obj))return false;//插入一个数据，tail后移obj->arr[obj->tail]=value;obj->tail++;//解决回绕，重头再来obj->tail %=(obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;//head前进，删除数据obj->head++;//解决回绕问题obj->head %=(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->arr[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;else//分类讨论取尾元素return obj->tail==0?obj->arr[obj->k]:obj->arr[obj->tail-1];//return obj->arr[(obj->tail-1+obj->k+1)%(obj->k+1)];//取模的方法很巧妙
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);free(obj);
}

方法2：双向链表实现

使用双向链表实现，其中每个节点（Node）包含一个整数值（val），以及指向前一个节点和后一个节点的指针（prev和next）。循环队列（MyCircularQueue）包含一个指向队列头部和尾部的指针（head和tail），以及队列的大小（size）和容量（capacity）。

//节点建立
typedef struct Node {int val;struct Node* prev;struct Node* next;
} Node;
//双向链表实现队列
typedef struct {Node* head;Node* tail;int size;int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->head = NULL;obj->tail = NULL;obj->size = 0;obj->capacity = k;return obj;
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->size == 0;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size == obj->capacity;
}
//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)) {return false;}Node* newNode = (Node*)malloc(sizeof(Node));newNode->val = value;newNode->prev = NULL;newNode->next = NULL;//队列为空时if (myCircularQueueIsEmpty(obj)) {obj->head = newNode;obj->tail = newNode;newNode->next = newNode;newNode->prev = newNode;} // 不为空时else {newNode->prev = obj->tail;newNode->next = obj->head;obj->tail->next = newNode;obj->head->prev = newNode;obj->tail = newNode;}obj->size++;return true;
}
//数据的删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) {return false;}Node* del = obj->head;if (obj->size == 1) {obj->head = NULL;obj->tail = NULL;} else {obj->head = obj->head->next;obj->head->prev = obj->tail;obj->tail->next = obj->head;}obj->size--;free(del);return true;
}
//头数据
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) {return -1;}return obj->head->val;
}
//尾数据
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) {return -1;}return obj->tail->val;
}
//队列销毁
void myCircularQueueFree(MyCircularQueue* obj) {Node* curr = obj->head;while (curr != obj->tail) {Node* next = curr->next;free(curr);curr = next;}obj->tail=NULL;free(obj);
}

补充方法3：

使用链表（单链表）-投机取巧哈哈哈

不过这种方法没有关系到循环队列，也能通过该题目。

可以用链表实现队列，用链表实现队列则较为简单，因为链表可以在 O(1)时间复杂度完成插入与删除。入队列时，将新的元素插入到链表的尾部；出队列时，将链表的头节点返回，并将头节点指向下一个节点。

循环队列的属性如下:

head：链表的头节点，队列的头节点。
tail：链表的尾节点，队列的尾节点。
capacity：队列的容量，即队列可以存储的最大元素数量。
size：队列当前的元素的数量。

相比较与数组，我们使用了size的方法来判断队列为空为满的状态，

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//中间节点创建和函数主体
typedef struct node {int val;struct node* next;
} node;
//循环队列先进先出
typedef struct {node* head;node* tail;int size;int capacity;
} MyCircularQueue;//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->head=obj->tail=NULL;obj->size=0;obj->capacity=k;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->size==0)return true;elsereturn false;
//return obj->size==0;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->size==obj->capacity;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;node* newnode=(struct node*)malloc(sizeof(node));newnode->val=value;newnode->next=NULL;if(obj->size==0){obj->head=newnode;obj->tail=newnode;}else{obj->tail->next=newnode;obj->tail=newnode;}obj->size++;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;node*del=obj->head;obj->head=obj->head->next;free(del);obj->size--;return true;}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->head->val;
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->tail->val;
}void myCircularQueueFree(MyCircularQueue* obj) {node* curr = obj->head;while (curr != NULL) {node* next = curr->next;free(curr);curr = next;}obj->size = obj->capacity = 0;obj->head = obj->tail = NULL;free(obj);
}//手动测试部分
int main() {MyCircularQueue* obj = myCircularQueueCreate(5);myCircularQueueEnQueue(obj, 1);myCircularQueueEnQueue(obj, 2);myCircularQueueEnQueue(obj, 3);myCircularQueueEnQueue(obj, 4);myCircularQueueEnQueue(obj, 5);printf("%d\n", myCircularQueueRear(obj));printf("%d\n", myCircularQueueFront(obj));myCircularQueueDeQueue(obj);printf("%d\n", myCircularQueueFront(obj));myCircularQueueFree(obj);return 0;
}

OK，本节内容到此结束，各位友友留下三连和评论吧，有更好的方法希望各位佬私信交流！！！

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

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

相关文章

单片机通信协议（1）：SPI简介

单片机通信协议（1）：SPI简介

关于SPI SPI&#xff08;串行外设接口&#xff09;是板载设备间通信接口之一。它是由摩托罗拉公司&#xff08;飞思卡尔半导体&#xff09;推出的。由于其简单性和通用性&#xff0c;它被纳入各种外围设备中&#xff0c;并与飞利浦I2C总线并列。 SPI的三线或四线信号数量比IIC…
阅读更多...
OSPF状态机+SPF算法

OSPF状态机+SPF算法

OSPF状态机 1.点到点网络类型 down-->init-->(前提为可以建立邻接)exstart——>exchange-->若查看邻接的DBD 目录后发现不用进行LSA 直接进入ful。若查看后需要进行查询、应答先进入loading&#xff0c;在查询应答完后再进入 fuIl: 2.MA网络类型 down --&g…
阅读更多...
【C++修行之道】类和对象（三）拷贝构造函数

【C++修行之道】类和对象（三）拷贝构造函数

目录 一、 概念 二、特征 正确的拷贝构造函数写法&#xff1a; 拷贝函数的另一种写法 三、若未显式定义&#xff0c;编译器会生成默认的拷贝构造函数。 四、编译器生成的默认拷贝构造函数已经可以完成字节序的值拷贝了&#xff0c;还需要自己显式实现吗&#xff1f; 深拷…
阅读更多...
Transformer 动画讲解：数据处理的四大关键步骤

Transformer 动画讲解：数据处理的四大关键步骤

节前&#xff0c;我们组织了一场算法岗技术&面试讨论会&#xff0c;邀请了一些互联网大厂朋友、今年参加社招和校招面试的同学。 针对大模型技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备面试攻略、面试常考点等热门话题进行了深入的讨论。 汇总合集…
阅读更多...
读《Diffusion Models: A Comprehensive Survey of Methods and Applications》综述

读《Diffusion Models: A Comprehensive Survey of Methods and Applications》综述

读《Diffusion Models: A Comprehensive Survey of Methods and Applications》综述 关于此文&#xff0c;我的一个见解想法&#xff0c;重点关注他怎么描述 「Diffusion Model」的引用的&#xff0c;以及未来方向就好了。当然从这篇文章可以知道 「Diffusion Model」的一个基石…
阅读更多...
【哈希】用哈希桶封装unordered_map unordered_set

【哈希】用哈希桶封装unordered_map unordered_set

&#x1f389;博主首页&#xff1a; 有趣的中国人 &#x1f389;专栏首页&#xff1a; C进阶 &#x1f389;其它专栏&#xff1a; C初阶 | Linux | 初阶数据结构 小伙伴们大家好&#xff0c;本片文章将会讲解 用哈希桶封装 unordered_map & unordered_set 的相关内容。 如…
阅读更多...
Linux系统使用Docker安装Drupal结合内网穿透实现远程访问管理后台

Linux系统使用Docker安装Drupal结合内网穿透实现远程访问管理后台

目录 前言 1. Docker安装Drupal 2. 本地局域网访问 3 . Linux 安装cpolar 4. 配置Drupal公网访问地址 5. 公网远程访问Drupal 6. 固定Drupal 公网地址 前言 作者简介&#xff1a; 懒大王敲代码&#xff0c;计算机专业应届生 今天给大家聊聊Linux系统使用Docker安装Drupal…
阅读更多...
python在cmd中运行.exe文件时报错：不是内部或外部命令，也不是可运行的程序或批处理文件。的解决办法

python在cmd中运行.exe文件时报错：不是内部或外部命令，也不是可运行的程序或批处理文件。的解决办法

添加系统环境变量&#xff1a; 设置环境变量&#xff0c;在用户变量里面添加 【PATH&#xff1a;%SystemRoot%\system32;%SystemRoot%;%SystemRoot%\System32\Wbem;C:\Windows\SysWOW64】 在系统变量里面添加,【变量名&#xff1a;ComSpec】 【变量值&#xff1a;%SystemRoo…
阅读更多...
ROS2从入门到精通2-1：launch多节点启动与脚本配置

ROS2从入门到精通2-1：launch多节点启动与脚本配置

目录 0 专栏介绍1 ROS2的启动脚本优化2 ROS2多节点启动案例2.1 C架构2.2 Python架构 3 其他格式的启动文件3.1 .yaml启动3.2 .xml启动 0 专栏介绍 本专栏旨在通过对ROS2的系统学习&#xff0c;掌握ROS2底层基本分布式原理&#xff0c;并具有机器人建模和应用ROS2进行实际项目的…
阅读更多...
适合能源企业的文档安全外发系统应该是什么样的？

适合能源企业的文档安全外发系统应该是什么样的？

能源企业是市场经济中的重要组成&#xff0c;也是社会可持续长远发展的关键组成之一&#xff0c;能源行业在开拓新能源业务线、提升产能的日常经营中&#xff0c;也需要与外部合作伙伴、客户间进行密切的业务往来&#xff0c;文档可能涉及多个领域多个类型。 能源供应合同&…
阅读更多...
IDEA2023.2单击Setting提示报错：Cannot get children Easy Code

IDEA2023.2单击Setting提示报错：Cannot get children Easy Code

1、单击Setting&#xff0c;不能弹出对话框 2、打开IDE Internal Errors发生错误 原因&#xff1a; 报错信息 "Cannot get children Easy Code" 通常指的是 IntelliJ IDEA 在尝试访问或操作 Easy Code 插件的子设置时遇到了问题。 主要检查是有网络&#xff08;断断…
阅读更多...
【排序算法】选择排序以及需要注意的问题

【排序算法】选择排序以及需要注意的问题

选择排序的基本思想&#xff1a;每一次从待排序的数据元素中选出最小&#xff08;或最大&#xff09;的一个元素&#xff0c;存放在序列的起始位置&#xff0c;直到全部待排序的数据元素排完 。 第一种实现方法&#xff1a; void SelectSort(int* arr, int n) {for (int j 0…
阅读更多...
安装 Android Studio 2024.1.1.6（Koala SDK35）和过程问题解决

安装 Android Studio 2024.1.1.6（Koala SDK35）和过程问题解决

记录更新Android Studio版本及适配Android V应用配置的一些过程问题。 安装包&#xff1a;android-studio-2024.1.1.6-windows.exe原版本&#xff1a;Android Studio23.2.1.23 Koala 安装过程 Uninstall old version 不会删除原本配置&#xff08;左下角提示&#xff09; Un…
阅读更多...
数据结构第二篇【关于java线性表（顺序表）的基本操作】

数据结构第二篇【关于java线性表（顺序表）的基本操作】

【关于java线性表&#xff08;顺序表&#xff09;的基本操作】 线性表是什么&#xff1f;&#x1f435;&#x1f412;&#x1f98d;顺序表的定义&#x1f9a7;&#x1f436;&#x1f435;创建顺序表新增元素,默认在数组最后新增在 pos 位置新增元素判定是否包含某个元素查找某个…
阅读更多...
如何解决研发数据传输层面安全可控、可追溯的共性需求？

如何解决研发数据传输层面安全可控、可追溯的共性需求？

研发数据在企业内部跨网文件交换&#xff0c;是相对较为普遍而频繁的文件流转需求&#xff0c;基于国家法律法规要求及自身安全管理需要&#xff0c;许多企业进行内部网络隔离。不同企业隔离方案各不相同&#xff0c;比如银行内部将网络隔离为生产网、办公网、DMZ区&#xff0c…
阅读更多...
Linux编程基础 8.4：epoll工作模式

Linux编程基础 8.4：epoll工作模式

1 简介 poll机制的工作原理及流程与select类似&#xff0c;但poll可监控的进程数量不受select中第二个因素——fd_set集合容量的限制&#xff0c;用户可在程序中自行设置被监测的文件描述符集的容量&#xff0c;当然poll在阻塞模式下也采用轮询的方式监测文件描述符集&#xf…
阅读更多...
相对位姿估计

相对位姿估计

相对位姿估计 示意图 理论推导 离线数据库&#xff1a; P的位置 P [ X , Y , Z ] T P[X,Y,Z]^{T} P[X,Y,Z]T 相机内参 k 1 k_{1} k1​ 安卓手机&#xff1a; 相机内参 k 2 k_{2} k2​ 两个像素点位置 &#xff1a; p 1 和 p 2 p_1和p_2 p1​和p2​ 公式一&#xff1a;…
阅读更多...
Python魔法之旅-魔法方法(04)

Python魔法之旅-魔法方法(04)

目录 一、概述 1、定义 2、作用 二、主要应用场景 1、构造和析构 2、操作符重载 3、字符串和表示 4、容器管理 5、可调用对象 6、上下文管理 7、属性访问和描述符 8、迭代器和生成器 9、数值类型 10、复制和序列化 11、自定义元类行为 12、自定义类行为 13、类…
阅读更多...
2年go蓝炎科技、爱诗科技面试经历，期望薪资22K

2年go蓝炎科技、爱诗科技面试经历，期望薪资22K

广州蓝炎科技一面 1、简单自我介绍&#xff1f;用的什么技术栈&#xff1f; 2、go的map是线程安全的吗&#xff1f; 3、Channel一般会在什么场景下使用&#xff1f;往一个未初始化的channel发送数据&#xff0c;会怎样&#xff1f; 4、关于go里头的随机数是线程安全的吗&am…
阅读更多...
网卡配置基础知识

网卡配置基础知识

1、网络设置方式 首先科普下Virtual Box虚拟机的几种主流的网络设置方式&#xff0c;官方文档&#xff1a; 2解释 Host-only&#xff1a;仅主机模式 虚拟机和宿主机、虚拟机之间能互通&#xff0c;但是不能访问外网&#xff0c;虚拟机和宿主机同网段的其他主机不能互通这种…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023