当前位置: 首页 > news >正文

【LeetCode刷题(数据结构与算法)】:用队列实现栈

在这里插入图片描述
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)
实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶
int pop() 移除并返回栈顶元素
int top() 返回栈顶元素
boolean empty() 如果栈是空的,返回 true ;否则,返回 false
注意:
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作
你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可
示例:

输入:
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]
解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
提示:
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空
在这里插入图片描述
这里有一个动图我一会儿上传到评论区大家可以看一下加深理解
为了满足栈的特性,即最后入栈的元素最先出栈,在使用队列实现栈时,应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作,其中 queue1
用于存储栈内的元素,queue2
作为入栈操作的辅助队列
入栈操作时,首先将元素入队到 queue2
然后将 queue1​
的全部元素依次出队并入队到 queue2
此时queue2​
的前端的元素即为新入栈的元素,再将 queue1​
和queue2​
互换,则queue1
的元素即为栈内的元素,queue1
​的前端和后端分别对应栈顶和栈底
由于每次入栈操作都确保 queue1​
的前端元素为栈顶元素,因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 queue1​
的前端元素并返回即可,获得栈顶元素操作只需要获得 queue1​
的前端元素并返回即可(不移除元素)
由于 queue1
用于存储栈内的元素,判断栈是否为空时,只需要判断 queue1
是否为空即可

动图链接
动图链接

#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>typedef int QueueDataType;typedef struct QNode
{struct QNode* next;QueueDataType data;
}QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;QueueDataType size;
}Que;
void QueueInit(Que* pq);void QueuePush(Que* pq, QueueDataType x);void QueuePop(Que* pq);void QueueDestroy(Que* pq);QueueDataType QueueFront(Que* pq);QueueDataType QueueBack(Que* pq);bool QueueEmpty(Que* pq);QueueDataType QueueSize(Que* pq);//#include"Queue.h"void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size =0;
}void QueuePush(Que* pq, QueueDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->head == NULL && pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;//tail指针指向下一个结构体---//--存放地址pq->tail = newnode;//尾节点}pq->size++;
}void QueuePop(Que* pq)
{assert(pq);//assert(!QueueEmpty(Que * pq));//写法错误 不允许使用类命名assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}QueueDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QueueDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}QueueDataType QueueSize(Que* pq)
{assert(pq);return pq->size;
}void QueueDestroy(Que* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* current = pq->head;while (current){QueueNode* next = current->next;free(current);current = next;}pq->head = pq->tail = NULL;pq->size = 0;
}typedef struct {Que q1;Que q2;
}MyStack;MyStack* myStackCreate() {//动态内存开辟函数malloc在堆区 无free不会主动销毁MyStack*pst=(MyStack*)malloc(sizeof(MyStack)*2);QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;//避免野指针NULL
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Que*Empty=&obj->q1;Que*NonEmpty=&obj->q2;if(!QueueEmpty(&obj->q1)){NonEmpty=&obj->q1;Empty=&obj->q2;}while(QueueSize(NonEmpty)>1){QueuePush(Empty,QueueFront(NonEmpty));QueuePop(NonEmpty);}//题目要求移除并返回栈顶元素topint top=QueueFront(NonEmpty);QueuePop(NonEmpty);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else {return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj=NULL;
}/*** 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);
*/

相关文章:

【LeetCode刷题(数据结构与算法)】:用队列实现栈

请你仅使用两个队列实现一个后入先出&#xff08;LIFO&#xff09;的栈&#xff0c;并支持普通栈的全部四种操作&#xff08;push、top、pop 和 empty&#xff09; 实现 MyStack 类&#xff1a; void push(int x) 将元素 x 压入栈顶 int pop() 移除并返回栈顶元素 int top() 返…...

“客户端到服务器的数据传递”和“服务器上的数据传递”这两种数据传递的方式的区别

“客户端到服务器的数据传递”和“服务器上的数据传递”这两种数据传递方式的主要区别如下&#xff1a; 数据的流动方向&#xff1a; 在“客户端到服务器的数据传递”中&#xff0c;数据是从客户端&#xff08;如浏览器&#xff09;流向服务器。在“服务器上的数据传递”中&…...

LCR 181 字符串中的单词反转

​​题目来源&#xff1a; leetcode题目&#xff0c;网址&#xff1a;LCR 181. 字符串中的单词反转 - 力扣&#xff08;LeetCode&#xff09; 解题思路&#xff1a; 倒叙遍历&#xff0c;获得每个单词的起始位置与终止位置&#xff0c;然后将每次遇到的单词插入结果中。 解题…...

百度OCR识别图片文本字符串——物联网上位机软件

一、开发背景 根据项目需求&#xff0c;我们需要完成LED显示屏实时显示歌词的效果。最优的方法是调用歌曲播放器的API获取歌词&#xff0c;但是由于这个开发资格不是很好申请&#xff0c;因此我们采用其他方案&#xff0c;即通过OCR识别获取歌词&#xff0c;并投射到LED显示屏上…...

JAVA学习(6)-全网最详细~

&#x1f308;write in front&#x1f308; &#x1f9f8;大家好&#xff0c;我是Aileen&#x1f9f8;.希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流. &#x1f194;本文由Aileen_0v0&#x1f9f8; 原创 CSDN首发&#x1f412; 如…...

睿趣科技:未来抖音开网店还有前景吗

随着科技的快速发展&#xff0c;电商平台已经成为了人们生活中不可或缺的一部分。在中国&#xff0c;抖音作为一个短视频平台&#xff0c;近年来迅速崛起&#xff0c;吸引了大量的用户和商家。那么&#xff0c;在未来&#xff0c;抖音是否还能为商家提供一个有效的电商平台呢?…...

第六章 应用层 | 计算机网络(谢希仁 第八版)

文章目录 第六章 应用层6.1 域名系统DNS6.1.1 域名系统概述6.1.2 互联网的域名结构6.1.3 域名服务器 6.2 文件传送协议6.2.1 FTP概述6.2.2 FTP的基本工作原理6.2.3 简单文件传送协议TFTP 6.3 远程终端协议TELNET6.4 万维网www6.4.1 万维网概述6.4.2 统一资源定位符URL6.4.3 超文…...

c++ lambda 表达式

1. 简介 lambda&#xff08;匿名函数&#xff09;是C11引入的一种函数对象&#xff0c;它允许我们在需要函数的地方创建一个临时的、匿名的函数。lambda表达式表示一个可以执行的代码单元&#xff0c;可以理解为一个未命名的内联函数。Lambda函数可以用于简化代码、提高可读性…...

Go语言入门心法(七): 并发与通道

Go语言入门心法(一): 基础语法 Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 一: go语言并发与通道...

前端组件封装:构建模块化、可维护和可重用的前端应用

前端组件封装&#xff1a;构建模块化、可维护和可重用的前端应用 前端开发领域的快速演进已经将前端应用的规模和复杂性提升到了一个新的水平。在这个背景下&#xff0c;前端组件封装成为了一项关键实践&#xff0c;旨在构建模块化、可维护和可重用的前端应用。在本文中&#…...

GPT绘制流程图咒语

【咒语】下面是我的一篇论文选取部分&#xff0c;为了让读者更好理解&#xff0c;我准备画一张图&#xff0c;请你阅读后为我设计一下这个图应该怎么画&#xff0c;更有说服力&#xff0c;更容易理解 论文片段&#xff1a; 多模态数据融合研究的基础在于有效的数据采集。首先&a…...

【扩散模型从原理到实战】Chapter1 扩散模型简介

文章目录 1.1 扩散模型的原理生成模型扩散过程DDPM的扩散过程前向过程反向过程优化目标 1.2 扩散模型的发展开始扩散&#xff1a;DDPM加速生成&#xff1a;采样器刷新记录&#xff1a;基于CLIP的多模态图像生成引爆网络&#xff1a;基于CLIP的多模态图像生成再次“出圈”&#…...

使用轮廓分数提升时间序列聚类的表现

我们将使用轮廓分数和一些距离指标来执行时间序列聚类实验&#xff0c;并且进行可视化 让我们看看下面的时间序列: 如果沿着y轴移动序列添加随机噪声&#xff0c;并随机化这些序列&#xff0c;那么它们几乎无法分辨&#xff0c;如下图所示-现在很难将时间序列列分组为簇: 上面…...

蔬菜水果生鲜配送团购商城小程序的作用是什么

蔬菜水果是人们生活所需品&#xff0c;从业者众多&#xff0c;无论小摊贩还是超市商场都有不少人每天光临&#xff0c;当然这些只是自然流量&#xff0c;在实际经营中&#xff0c;蔬菜水果商家还是面临着一些难题。 对蔬菜水果商家而言&#xff0c;线下门店是重要的&#xff0…...

金融用户实践|分布式存储支持数据仓库业务系统性能验证

作者&#xff1a;深耕行业的 SmartX 金融团队 闫海涛 估值是指对资产或负债的价值进行评估的过程&#xff0c;这对于投资决策具有重要意义。每个金融公司资管业务人员都期望能够实现实时的业务估值&#xff0c;快速获取最新的数据和指标&#xff0c;从而做出更明智的投资决策。…...

代码随想录二刷 Day41

509. 斐波那契数 这个题简单入门&#xff0c;注意下N小于等于1的情况就可以 class Solution { public:int fib(int n) {if (n < 1) return n; //这句不写的话test能过但是另外的过不了vector<int> result(n 1); //定义存放dp结果的数组&#xff0c;还要定义大小r…...

C++项目实战——基于多设计模式下的同步异步日志系统-⑪-日志器管理类与全局建造者类设计(单例模式)

文章目录 专栏导读日志器建造者类完善单例日志器管理类设计思想单例日志器管理类设计全局建造者类设计日志器类、建造者类整理日志器管理类测试 专栏导读 &#x1f338;作者简介&#xff1a;花想云 &#xff0c;在读本科生一枚&#xff0c;C/C领域新星创作者&#xff0c;新星计…...

Hadoop3教程(十四):MapReduce中的排序

文章目录 &#xff08;99&#xff09;WritableComparable排序什么是排序什么时候需要排序排序有哪些分类如何实现自定义排序 &#xff08;100&#xff09;全排序案例案例需求思路分析实际代码 &#xff08;101&#xff09;二次排序案例&#xff08;102&#xff09; 区内排序案例…...

测试需要写测试用例吗?

如何理解软件的质量 我们都知道&#xff0c;一个软件从无到有要经过需求设计、编码实现、测试验证、部署发布这四个主要环节。 需求来源于用户反馈、市场调研或者商业判断。意指在市场行为中&#xff0c;部分人群存在某些诉求或痛点&#xff0c;只要想办法满足这些人群的诉求…...

Qt 视口和窗口的区别

视口和窗口 绘图设备的物理坐标是基本的坐标系&#xff0c;通过QPainter的平移、旋转等变换可以得到更容易操作的逻辑坐标 为了实现更方便的坐标&#xff0c;QPainter还提供了视口(Viewport)和窗口(Window)坐标系&#xff0c;通过QPainter内部的坐标变换矩阵自动转换为绘图设…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

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

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...