【Leedcode】栈和队列必备的面试题（第二期）

news/2024/4/26 15:44:10/文章来源:https://blog.csdn.net/2201_75587702/article/details/129270427

【Leedcode】栈和队列必备的面试题（第二期）

文章目录

  • 【Leedcode】栈和队列必备的面试题（第二期）
  • 一、题目（用两个队列实现栈）
  • 二、思路+图解
    • 1.定义两个队列
    • 2.初始化两个队列
    • 3.往两个队列中放入数据
    • 4.两个队列出数据
    • 5.显示栈顶信息
    • 6.判断栈或者队列是否为空
    • 7.销毁栈或者队列
  • 三、总代码展示
  • 总结

一、题目（用两个队列实现栈）

Leedcode链接

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
这几个接口使我们需要实现的我会一 一实现并讲解！

二、思路+图解

注意：这里会用到很多栈和队列接口实现的一些知识，这里不再深究，如果想了解可以去下面两个博客！
栈的接口模拟实现 + 队列的接口模拟实现

做本题需要的接口和结构体声明！

代码如下（示例）：

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;void QueueInit(Queue* pq);//初始化队列
void QueueDestroy(Queue* pq);//销毁队列
void QueuePush(Queue* pq, QDataType x);//放入数据
void QueuePop(Queue* pq);//删除数据
QDataType QueueFront(Queue* pq);//取头数据
QDataType QueueBack(Queue* pq);//取尾数据
size_t QueueSize(Queue* pq);//计算数据个数
bool QueueEmpty(Queue* pq);//判断队列是不是空void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}void QueueDestroy(Queue* pq)//销毁队列
{assert(pq);//创建一个cur指针 指向队列头 用于挨个释放空间QueueNode* cur = pq->head;//当cur不为NULL 一直循环执行  挨个释放列表成员空间while (cur != NULL){QueueNode* next = cur->next;free(cur);cur = next;}//当循环结束 将 head与tail 置为NULLpq->head = pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x)//放入数据
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->data = x;newnode->next = NULL; if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq)//删除数据
{assert(pq);assert(!QueueEmpty(pq));QueueNode* next = pq->head->next;free(pq->head);if (pq->head == pq->tail){pq->tail = NULL;}pq->head = next; 
}QDataType QueueFront(Queue* pq)//取头数据
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)//取尾数据
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
size_t QueueSize(Queue* pq)//计算数据个数
{assert(pq);assert(!QueueEmpty(pq));QueueNode* cur = pq->head;int n = 0;while (cur){cur = cur->next;n++;}return n;
}bool QueueEmpty(Queue* pq)//判断队列是不是空
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}

1.定义两个队列

代码如下（示例）：

typedef struct{Queue q1;Queue q2;
} MyStack;

2.初始化两个队列

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码如下（示例）：

MyStack* myStackCreate() {MyStack* st = (MyStack*)malloc(sizeof(MyStack));QueueInit(&st->q1);QueueInit(&st->q2);return st;
}

3.往两个队列中放入数据

在这里插入图片描述

在这里插入图片描述

代码如下（示例）：

void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else{QueuePush(&obj->q2, x);}
}

4.两个队列出数据

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码如下（示例）：

int myStackPop(MyStack* obj) {Queue* emptyQ = &obj->q1;Queue* nonemptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){nonemptyQ = &obj->q1;emptyQ = &obj->q2;}while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ, QueueFront(nonemptyQ));QueuePop(nonemptyQ);}int ret = QueueFront(nonemptyQ);QueuePop(nonemptyQ);return ret;
}

5.显示栈顶信息

在这里插入图片描述

代码如下（示例）：

int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

6.判断栈或者队列是否为空

在这里插入图片描述

代码如下（示例）：

bool myStackEmpty(MyStack* obj) 
{return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

7.销毁栈或者队列

在这里插入图片描述

在这里插入图片描述

代码如下（示例）：

void myStackFree(MyStack* obj) 
{QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

三、总代码展示

代码如下（示例）：

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;
}Queue;void QueueInit(Queue* pq);//初始化队列
void QueueDestroy(Queue* pq);//销毁队列
void QueuePush(Queue* pq, QDataType x);//放入数据
void QueuePop(Queue* pq);//删除数据
QDataType QueueFront(Queue* pq);//取头数据
QDataType QueueBack(Queue* pq);//取尾数据
size_t QueueSize(Queue* pq);//计算数据个数
bool QueueEmpty(Queue* pq);//判断队列是不是空void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}void QueueDestroy(Queue* pq)//销毁队列
{assert(pq);//创建一个cur指针 指向队列头 用于挨个释放空间QueueNode* cur = pq->head;//当cur不为NULL 一直循环执行  挨个释放列表成员空间while (cur != NULL){QueueNode* next = cur->next;free(cur);cur = next;}//当循环结束 将 head与tail 置为NULLpq->head = pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x)//放入数据
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->data = x;newnode->next = NULL; if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq)//删除数据
{assert(pq);assert(!QueueEmpty(pq));QueueNode* next = pq->head->next;free(pq->head);if (pq->head == pq->tail){pq->tail = NULL;}pq->head = next; 
}QDataType QueueFront(Queue* pq)//取头数据
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)//取尾数据
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
size_t QueueSize(Queue* pq)//计算数据个数
{assert(pq);assert(!QueueEmpty(pq));QueueNode* cur = pq->head;int n = 0;while (cur){cur = cur->next;n++;}return n;
}bool QueueEmpty(Queue* pq)//判断队列是不是空
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}//定义两个队列
typedef struct{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {//函数内定义变量出了函数就没了，所以我们在这里选择用malloc开辟动态空间 并将这个空间的地址返回给函数MyStack* st = (MyStack*)malloc(sizeof(MyStack));//调用自己的队列初始化函数 将定义的2个队列初始化QueueInit(&st->q1);QueueInit(&st->q2);//函数要求 返回新开辟的地址(栈地址)return st;
}void myStackPush(MyStack* obj, int x) {//往栈中放入数据if(!QueueEmpty(&obj->q1))//当q1不是空的时 将数据放入q1队列中{//调用队列函数，自定义函数传过来的是栈的指针，所以要&obj的地址指向q1QueuePush(&obj->q1, x);}else//当q2不是空的时 将数据放入q1队列中  由于这里是else 所以假设q1 q2都是空也会将数据放入q2队列中{QueuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {//emptyQ表示空队列   nonEmptuQ 表示有元素队列//先假设定义队列 q1为空 q2 非空Queue* emptyQ = &obj->q1;Queue* nonemptyQ = &obj->q2;//然后调用判断是否为空函数if(!QueueEmpty(&obj->q1))//如果队列q1 非空进入循环{//向q1道歉 将q1改为非空  将q2改为空nonemptyQ = &obj->q1;emptyQ = &obj->q2;}//此时 nonempyuQ 与 emptyQ 经历了修正 队列nonempyuQ 是非空 emptyQ是空 （特殊情况下两者都是空）while(QueueSize(nonemptyQ)>1)//循环条件 非空的nonemptyQ队列数据个数最少是大于1就可以进入循环，假设等于或小于1不进入循环{//将非空nonemptyQ队列元素数据放入，空emptyQ队列中QueuePush(emptyQ, QueueFront(nonemptyQ));//放进去一个就删除一个非空nonemptyQ队列元素QueuePop(nonemptyQ);}//当循环结束来到这里nonempty内只有一个元素，这个元素也表示的是栈顶的元素(特殊情况下nonempty也是空的)int ret = QueueFront(nonemptyQ);QueuePop(nonemptyQ);//最后删除这个元素（表达出栈行为）return ret;//函数要求返回这个被删除的元素数据
}
int myStackTop(MyStack* obj) {//显示栈顶信息if(!QueueEmpty(&obj->q1))//栈顶不为空进入{//返回q1队列尾部数据return QueueBack(&obj->q1);}else{//返回q2队列尾部数据return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {//当q1为空 并且 q2为空 则返回真 return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {//先将q1 和 q2 空间销毁QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);//最后释放obj空间free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

总结

以上就是今天要讲的内容，本文为【Leedcode】栈和队列必备的面试题（第二期）
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！
在这里插入图片描述

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

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

相关文章

对账平台设计

对账平台设计

背景 随着公司业务的蓬勃发展，交易履约清结算业务的复杂性也在不断的增高，资金以及各种数据的一致性和准确性也变得越发重要。 以交易链路为例，存在着如下一些潜在的不一致场景： 订单支付成功了，但是订单状态却还是“…
阅读更多...
JVM方法区详解有这篇就够了

JVM方法区详解有这篇就够了

1、方法区在哪里《Java虚拟机规范》中明确说明：“尽管所有的方法区在逻辑上是属于堆的一部分，但一些简单的实现可能不会选择去进行垃圾收集或者进行压缩。”但对于HotSpotJVM而言，方法区还有一个别名叫做Non-Heap（非堆&#xff09…
阅读更多...
机械键盘不只有轴体的区别！键帽高度也有些学问

机械键盘不只有轴体的区别！键帽高度也有些学问

键盘键帽的学问有很多，上篇文章中，笔者和大家聊了键帽的材质和耐油污的问题。 除此之外，键帽的高度和字符的印刷方式也有不同，对于多数机械键盘来说，会发现每一列键帽的倾斜角度都略有不同，使用起来可以减少…
阅读更多...
Android TV UI开发常用知识

Android TV UI开发常用知识

导入依赖 Google官方为Android TV的UI开发提供了一系列的规范组件，在leanback的依赖库中，这里介绍一些常用的组件，使用前需要导入leanback库。 implementation androidx.leanback:leanback:$version常用的页面 这些Fragment有设计好的样式&…
阅读更多...
3.ffmpeg命令行环境搭建、ffmpeg命令行初步了解

3.ffmpeg命令行环境搭建、ffmpeg命令行初步了解

在上章,我们讲过: ffmpeg.exe: 主要用于转码或者剪切的应用程序, 也可以从url/现场音频/视频源抓取输入源ffplay.exe: 主要用于播放视频的应用程序,该应用程序源码是开源的,我们后面章节会去源码分析ffprobe.exe: 主要用于分析视频码流的应用程序, 可以获取媒体文件的详细信息,…
阅读更多...
【Azure 架构师学习笔记】-Azure Data Factory (4)-触发器详解-事件触发器

【Azure 架构师学习笔记】-Azure Data Factory (4)-触发器详解-事件触发器

本文属于【Azure 架构师学习笔记】系列。 本文属于【Azure Data Factory】系列。 接上文【Azure 架构师学习笔记】-Azure Data Factory (3)-触发器详解-翻转窗口 前言 事件触发指的是存储事件，所以在新版的ADF 中，已经明确了是“存储事件”，…
阅读更多...
【C语言】结构体进阶

【C语言】结构体进阶

一、结构体 1. 结构体的声明 （1） 结构的基础知识 结构是一些值的集合，这些值称为成员变量。结构的每个成员可以是不同类型的变量。（2）结构的声明 struct tag {member-list; }variable-list;例如描述一个学生&#x…
阅读更多...
【SPSS】两配对样本T检验分析详细操作教程（附案例实战）

【SPSS】两配对样本T检验分析详细操作教程（附案例实战）

🤵‍♂️ 个人主页：艾派森的个人主页 ✍🏻作者简介：Python学习者 🐋 希望大家多多支持，我们一起进步！😄 如果文章对你有帮助的话， 欢迎评论 💬点赞&#x1f4…
阅读更多...
RocketMQ的一些使用理解

RocketMQ的一些使用理解

1.RocketMQ的生产者生产负载策略（3种） (1)SelectMessageQueueByHash （一致性hash） (2)SelectMessageQueueByMachineRoom （机器随机） (3)SelectMessageQueueByRandom （随机） 第1种一…
阅读更多...
VBA之正则表达式（41）-- 快速标记两个星号之后的字符

VBA之正则表达式（41）-- 快速标记两个星号之后的字符

实例需求：工作表中的数据保存在A列~G列，现需要识别D列中包含超过两个星号的内容，并将第3个星号及其之后的字符设置为红色字体，如图所示。 示例代码如下。 Sub Demo1()Dim objRegExp As ObjectDim objMatch As ObjectDim strMatch…
阅读更多...
08 自研or借力（上）：集成Gin替换已有核心

08 自研or借力（上）：集成Gin替换已有核心

我们的框架和这些顶级的框架相比，差了什么呢？如何才能快速地把我们的框架可用性，和这些框架提升到同一个级别？我们做这个框架除了演示每个实现细节，它的优势是什么呢？ 不妨带着这些问题，把我们…
阅读更多...
ClickHouse的架构与基本概念

ClickHouse的架构与基本概念

一、ClickHouse的定义 ClickHouse是一个完全的列式分布式数据库管理系统(DBMS)，允许在运行时创建表和数据库，加载数据和运行查询，而无需重新配置和重新启动服务器，支持线性扩展，简单方便，高可靠性&#xf…
阅读更多...
C++学习笔记-内存空间

C++学习笔记-内存空间

考虑这样一种情况，当我们使用相同的名称，叫Zara的两个人在同一个班级。我们需要明确区分它们将不得不使用一些额外的信息，如他们的名字，如他们生活在不同的区域或母亲或父亲的名字等等。 同样的情况也出现在C应用程序中。例如&am…
阅读更多...
iphone系统崩溃数据能恢复吗?教你三招方法

iphone系统崩溃数据能恢复吗?教你三招方法

最近有些苹果用户反应自己手机的屏幕无法滑动，桌面上APP也无法点开，想要关机重启下试试，可是，连关机都关不了，甚至连Siri都罢工了。苹果手机系统崩溃，出现黑屏、白屏、无限重启之类的故障，导致手…
阅读更多...
大数据处理学习笔记1.6 Scala数据结构

大数据处理学习笔记1.6 Scala数据结构

文章目录零、本讲学习目标一、数组 (Array)（一）定长数组1、数组定义（1）定义数组时初始化数据（2）定义时指定数组长度，后赋值2、数组遍历（1）传统for循环方式（2&…
阅读更多...
Databend 开源周报 第 82 期

Databend 开源周报 第 82 期

Databend 是一款现代云数仓。专为弹性和高效设计，为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务：https://app.databend.com 。Whats New探索 Databend 本周新进展，遇到更贴近你心意的 Databend 。Features & Improvements :…
阅读更多...
【沐风老师】3dmax一键窗户生成器插件使用方法详解

【沐风老师】3dmax一键窗户生成器插件使用方法详解

3dmax一键窗户生成器插件教程 3dMax一键窗户生成器是一个在3dMax中自动创建3D窗户模型的脚本。它有28种风格的窗户样式，可以在Archviz项目中灵活应用，同时为3D艺术家节省大量时间。 【适用版本】 适用3dMax 2018.2及更高版本 【安装方法】 1.解压缩包&…
阅读更多...
林心如常驻《向往的生活》，周杰却陷地域黑，做人的差别太大了吧

林心如常驻《向往的生活》，周杰却陷地域黑，做人的差别太大了吧

十年前如果有人提起周杰，就算是不能如雷贯耳，最起码也是妇孺皆知，毕竟那时候他太有名气了。因为拍摄《还珠格格》，让他和林心如等人一起爆红，不过此后的林心如，却很少再有优秀作品问世。 而周杰却不一样&am…
阅读更多...
AOP在PowerJob中的使用，缓存锁保证并发安全，知识细节全总结

AOP在PowerJob中的使用，缓存锁保证并发安全，知识细节全总结

这是一篇简简单单的文章，需要你简简单单看一眼就好，如果有不明白的地方，欢迎留言讨论。 在之前的文章中出现过一次AOP的使用，就是在运行任务之前，需要判断一下，触发该任务执行的server，是不是数…
阅读更多...
AIGC被ChatGPT带火！底层基础算力有望爆发式增长

AIGC被ChatGPT带火！底层基础算力有望爆发式增长

ChatGPT火爆全球的背后，可以窥见伴随人工智能技术的发展，数字内容的生产方式向着更加高效迈进。ChatGPT属于AIGC的具体应用，而AIGC是技术驱动的数字内容新生产方式。AIGC类产品未来有望成为5G时代新的流量入口，率先受益的有望是AI…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业