当前位置: 首页 > 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内部的坐标变换矩阵自动转换为绘图设…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...