栈和队列习题精选(持续更新中)
第一题(括号匹配)
给定一个只包括 '(',')','{','}','[',']' 的字符串 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…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
flow_controllers
关键点: 流控制器类型: 同步(Sync):发布操作会阻塞,直到数据被确认发送。异步(Async):发布操作非阻塞,数据发送由后台线程处理。纯同步(PureSync…...