栈和队列习题精选(持续更新中)
第一题(括号匹配)
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。
char pairs(char* ch)
{if(*ch=='}')return '{';if(*ch==')')return '(';if(*ch==']')return '[';return 0;
}
bool isValid(char * s){char stack[10000]={0};int top=0,i=0;while(*(s+i)){char ch=pairs(s+i);if(ch){if(top==0||ch!=stack[top-1])//这里需要判断栈是否为空的原因是没有左括号还在匹配会造成越界{return false;}else{top--;}}else{stack[top++]=*(s+i);}i++;}return top==0;}
第二题(用队列模拟栈)
这里需要判断栈是否为空的原因是没有左括号还在匹配会造成越界
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* obj = (MyStack*)malloc(sizeof(MyStack));QueueInit(&obj->q1);QueueInit(&obj->q2);return obj;
}void myStackPush(MyStack* obj, int x) {assert(obj);if (!QueueEmpty(&obj->q1)){QueuePush(&obj->q1);}else{QueuePush(&obj->q2);}return;
}int myStackPop(MyStack* obj) {Queue* pEmpty = &obj->q1;//注意左右两边的类型要匹配Queue* pNonEmpty = &obj->q2;if (!QueueEmpty(pEmpty)){Queue* pEmpty = &obj->q2;Queue* pNonEmpty = &obj->q1;}while (QueueSize(pNonEmpty) > 1){QueuePush(pNonEmpty, QueueFront(pNonEmpty));QueuePop(pNonEmpty);}int top = QueueFront(pNonEmpty);QueuePop(pNonEmpty);return top;
}int myStackTop(MyStack* obj) {Queue* pEmpty = &obj->q1;Queue* pNonEmpty = &obj->q2;if (!QueueEmpty(pEmpty)){Queue* pEmpty = &obj->q2;Queue* pNonEmpty = &obj->q1;}return QueueBack(pNonEmpty);
}bool myStackEmpty(MyStack* obj) {if (!(QueueEmpty(&obj->q2)) && !(QueueEmpty(&obj->q1))){return false;}return true;
}void myStackFree(MyStack* obj) {QueueDestory(&obj->q1);//free可能会free不干净,万一是链式结构呢?QueueDestory(&obj->q2);free(obj);
}
第三题(用栈模拟队列)
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false
说明:
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
解题思路
可以用两个栈实现,一个栈进行入队操作,我们称为入队栈,另一个栈进行出队操作,我们称为出队栈
出队操作: 当出队栈不为空是,直接进行出栈操作,如果为空,需要把入队栈元素全部导入到出队的栈,然后再进行出栈操作。
#define maxSize 100
typedef struct {//入队栈Stack pushST;//出队栈Stack popST;
} MyQueue;/** Initialize your data structure here. */
MyQueue* myQueueCreate(int maxSize) {MyQueue* pqueue = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&pqueue->pushST, maxSize);StackInit(&pqueue->popST, maxSize);return pqueue;
}/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {//入队栈进行入栈操作StackPush(&obj->pushST, x);
}/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {//如果出队栈为空,导入入队栈的元素if(StackEmpty(&obj->popST) == 0){while(StackEmpty(&obj->pushST) != 0){StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}int front = StackTop(&obj->popST);//出队栈进行出队操作StackPop(&obj->popST);return front;
}/** Get the front element. */
int myQueuePeek(MyQueue* obj) {//类似于出队操作if(StackEmpty(&obj->popST) == 0){while(StackEmpty(&obj->pushST) != 0){StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}return StackTop(&obj->popST);
}//判断栈是否为空
bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->pushST) == 0&& StackEmpty(&obj->popST) == 0;
}void myQueueFree(MyQueue* obj) {StackDestroy(&obj->pushST);//与上题一样不能直接free,要交给栈的销毁函数来做StackDestroy(&obj->popST);free(obj);
}
第四题(设计循环队列)
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k): 构造器,设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空,返回 -1 。
Rear: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
#define dataType int typedef struct {dataType* arr;int front;int rear;int size;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* ret = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if (ret == NULL){perror("malloc::fail");}ret->arr = (dataType*)malloc(sizeof(dataType) * (k + 1));ret->front = ret->rear = 0;ret->size =k+1;return ret;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (((obj->rear + 1) %obj->size) == obj->front)//判断循环队列是否为满,%不是/{return false;}obj->arr[obj->rear] = value;obj->rear=(obj->rear+1)%obj->size;//不需要加MaxSizereturn true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (obj->rear == obj->front){return false;}obj->front= (obj->front +1) % obj->size;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if (obj->rear == obj->front){return -1;}return obj->arr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if (obj->rear==obj->front){return -1;}//因为是先存数据在加加,所以rear实际上是指向队尾的下一个元素//故最好在此处进行分类讨论if(obj->rear==0){return obj->arr[obj->size-1];}else{return obj->arr[obj->rear-1];}}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if (obj->front == (obj->rear + 1 + obj->size) % obj->size){return true;}return false;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);//双层释放free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/
相关文章:
栈和队列习题精选(持续更新中)
第一题(括号匹配)给定一个只包括 (,),{,},[,] 的字符串 s ,判断字符串是否有效。有效字符串需满足:1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。…...

大数据开发 - Java入门6
目录标题do-while循环练习1:从键盘输入单词,讲输入的单词输出到控制台,输入是exit时退出循环练习2:键盘输入密码和确认密码,两次密码一致就退出循环打印注册成功,两次密码不一致就循环输入两次密码死循环fo…...

开源超级终端工具——WindTerm
1、下载和安装(我的是win10,其他版本各位自选) Releases kingToolbox/WindTerm GitHub 安装的话,相信大家不用我赘述了。 初始界面是这样的: 2、WindTerm使用 2.1 本地会话(最下面那个框,发…...

【Linux】信号常见概念
文章目录信号入门生活中的信号技术应用角度的信号signal函数注意事项信号的概念信号的产生信号的记录(保存)信号处理常见方式概述信号入门 生活中的信号 你在网上买了很多件商品,在等待不同商品快递的到来 但即便快递还没有到来,你也知道快递到了的时候应该怎么处理快递,也就…...

15000 字的 SQL 语句大全 第一部分
一、基础 1、说明:创建数据库CREATE DATABASE database-name 2、说明:删除数据库drop database dbname 3、说明:备份sql server--- 创建 备份数据的 device USE master EXEC sp_addumpdevice disk, testBack, c:\mssql7backup\MyNwind_1.dat …...

突发——字节跳动被要求出售 TikTok 股票,否则禁令,低代码也曾被打压
一、欲加之罪,何患无辞! 正值人们对TikTok和其它社交媒体平台对年轻用户的影响进行更广泛、持续的反思之际,美政客们以数据安全为由要求TikTok出售股票,已然不顾文明国家的体面。 在美国,TikTok拥有1.4亿用户&#x…...

2023年网络安全趋势
数据安全越来越重要。 我国《数据安全法》提出“建立健全数据安全治理体系”,各地区部门均在探索和简历数据分类分级、重要数据识别与重点保护制度。 数据安全治理不仅是一系列技术应用或产品,更是包括组织构建、规范制定、技术支撑等要素共同完成数据…...

html练习
1.用户注册界面 代码: <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title></head><body><form action"#" method"get"><table border"1" widt…...

【Redis】Redis 是如何保证高可用的?(背诵版)
Redis 是如何保证高可用的?1. 说一下 Redis 是如何保证高可用的?2. 了解过主从复制么?2.1 Redis 主从复制主要的作用是什么?2.2 Redis 主从模式的拓扑结构?(1)一主一从结构(2)一主多…...
Qt---去掉标题栏后,最大化应用程序窗口时,窗口遮住了任务栏
// showMaximized(); // Qt最大化显示函数 任务栏都会覆盖static bool max false;static QRect location this->geometry();if (max) {this->setGeometry(location);//回复窗口原大小和位置// ui->maxBtn->setIcon(QIcon(":/MAX_.png"));}else {// ui-…...
Cadence Allegro 导出Netin(non-back)报告详解
⏪《上一篇》 🏡《上级目录》 ⏩《下一篇》 目录 1,概述2,Netin(non-back)作用3,Netin(non-back)示例4,Netin(non-back)导出方法4.1,方法1:4.2,方法2:B站关注“硬小二”浏览更多演示视频...

HTML语言
1.什么是HTML? 1、HTML是超文本标记语言(Hyper Text Markup Language) 2、HTML由各种各样的标签(tag)组成,如、 3、HTML文档 网页 (1)一种纯文本文件,扩展名为.html或.html; (2)最终显示结果取决…...

线性代数之行列式
一、思维导图二、二阶、三阶行列式的定义1、二阶行列式2、三阶行列式沙路法展开3、解方程3.1解二元一次方程组观察上面两个未知量的值不难发现,它 们的分母均是上述方程组未知量的系数形成的二阶行列式,𝑥1的分子是将系数行列 式的第一列换成…...

【FPGA-Spirit_V2】小精灵V2开发板初使用
🎉欢迎来到FPGA专栏~小精灵V2开发板初使用 ☆* o(≧▽≦)o *☆嗨~我是小夏与酒🍹 ✨博客主页:小夏与酒的博客 🎈该系列文章专栏:FPGA学习之旅 文章作者技术和水平有限,如果文中出现错误,希望大家…...

STL与其空间配置器
目录什么是STLSTL的六大组件STL的缺陷什么是空间配置器为什么需要空间配置器GI-STL空间配置器实现原理一级空间配置器二级空间配置器内存池SGI-STL中二级空间配置器设计SGI-STL二级空间配置器之空间申请前期的准备申请空间填充内存块向内存池中索要空间SGI-STL二级空间配置器之…...

leetcode刷题之回文链表
目录 做题思路 代码实现 1.找到链表的中间节点 2.反转中间节点之后的链表 3.判断倒置的后半部分的链表是否等于前半部分的链表 整体代码展示 总结: 这里是题目链接。 这道题目的意思是:判断该链表中后半部分倒置是否跟前半部分相同,如…...

复制带随机指针的链表最长连续递增序列数组的度写字符串需要的行数最短补全词
复制带随机指针的链表来源:杭哥138. 复制带随机指针的链表 - 力扣(LeetCode)typedef struct Node Node; Node* BuyNode(int x) {Node* newnode (Node*)malloc(sizeof(Node));newnode->valx;newnode->nextNULL;newnode->randomNULL;…...

「ML 实践篇」回归系统:房价中位数预测
文章目录1. 项目分析1. 框架问题2. 性能指标2. 获取数据1. 准备工作区2. 下载数据3. 查看数据4. 创建测试集3. 数据探索1. 地理位置可视化2. 寻找相关性3. 组合属性4. 数据准备1. 数据清理2. Scikit-Learn 的设计3. 处理文本、分类属性4. 自定义转换器5. 特征缩放6. 流水线5. 选…...

深度学习 Day27——利用Pytorch实现运动鞋识别
深度学习 Day27——利用Pytorch实现运动鞋识别 文章目录深度学习 Day27——利用Pytorch实现运动鞋识别一、查看colab机器配置二、前期准备1、导入依赖项并设置GPU2、导入数据三、构建CNN网络四、训练模型1、编写训练函数2、编写测试函数3、设置动态学习率4、正式训练五、结果可…...
Springboot 整合dom4j 解析xml 字符串 转JSONObject
前言 本文只介绍使用 dom4j 以及fastjson的 方式, 因为平日使用比较多。老的那个json也能转,而且还封装好了XML,但是本文不做介绍。 正文 ①加入 pom 依赖 <dependency><groupId>dom4j</groupId><artifactId>dom4j…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...