Leetcode-每日一题【剑指 Offer 09. 用两个栈实现队列】

题目

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
[[],[3],[],[],[]]
输出:[null,null,3,-1,-1]


示例 2:

输入:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]


提示:

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

解题思路

1.题目要求我们用两个栈实现队列,但是给出的示例看起来不太明白,那就让我们换成图片的形式来理解一下吧!

举个例子:假设我们所要进行的操作如下

 我们先新建两个栈 stack1 和 stack2,再建立一个queue(队列)帮助理解

接下来我们开始执行操作

 入栈的元素我们都先放入 Stack1 中,同时也给队列入队来做对比。

 此时下一步是出队,如果我们直接从Stack1出,那就不满足我们队列先进先出的性质,所以这个时候我们就要用到我们的 Stack2,在执行出队操作时,我们要先判断 Stack2 是否有元素,若有则直接从 Stack2 出栈,若没有我们就需要将 Stack1 中的所有元素出栈再将元素入栈到 Stack2 中。

 这时我们可以看到 Stack2 出栈的顺序就与队列一致了,我们就可以将最先入队的 1 让它出队

下一操作还是入队,我们依旧要将入队的元素先放入 Stack1 中,

 然后开始出队,Stack2 中有元素就让 Stack2 出栈,若 Stack2 为空 就将 Stack1 中的元素入栈到 Stack2 中,直到 两个栈都为空,则说明队列中所有元素已经出队了。

 2.代码的实现,我们需要先设置两个栈,然后将两个栈进行初始化,在appendTail()入队操作时,我们只需将元素入栈到Stack1即可,在deleteHead()出队操作时,我们需要先判断 Stack2 是否为空,若不为空则直接从 Stack2 出栈,若为空我们就需要将 Stack1 中的所有元素出栈再将元素入栈到 Stack2 中。然后从Stack2出栈即可。当两个栈都为空时,就代表队列已经为空,返回 -1。

 

代码实现

class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }
        if(!stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
    }
    return -1;
}
}

测试结果

 

 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

三款Notion网页插件,让你的Notion更好用

今天给大家分享一下我常用的Notion插件&#xff1a;Bookmarks to Notion&#xff0c;Save to Notion&#xff0c;Notion boost。这三款插件大大提升了我的Notion网页端使用体验。 Bookmarks to Notion 这款软件可以把你的网页书签保存到Notion&#xff0c;你甚至可以快速的用…

深度学习入门必读 | 深度学习算法技术原理和发展

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。随着人工智能技术的发展&#xff0c;深度学习已经成为了一个热门话题。为了让大家能够更清晰直观的了解深度学习&#xff0c;今天这篇文章就重点给大家介绍一下深度学习算法的技术原理和发展&#xff01;&#x1f308; 目录…

Linux学习之正则表达式元字符和grep命令

cat /etc/redhat-release看到操作系统的版本是CentOS Linux release 7.6.1810 (Core)&#xff0c;uname -r可以看到内核版本是3.10.0-957.21.3.el7.x86_64。 正则表达式是一种搜索字符串的模式&#xff0c;通俗点理解&#xff0c;也就是普通字符和元字符共同组成的字符集合匹…

【Megatron-DeepSpeed】张量并行工具代码mpu详解(三):张量并行层的实现及测试

相关博客 【Megatron-DeepSpeed】张量并行工具代码mpu详解(三)&#xff1a;张量并行层的实现及测试 【Megatron-DeepSpeed】张量并行工具代码mpu详解(一)&#xff1a;并行环境初始化 【Megatron-DeepSpeed】张量并行工具代码mpu详解(二)&#xff1a;Collective通信操作的封装ma…

生成式 AI 简介:使用 Python 从头开始学习 GenAI

一、介绍 大家好&#xff01;&#xff0c;欢迎来到“使用 Python 从头开始学习生成 AI”系列。本系列涵盖了数据科学家和软件工程师可以了解的有关生成式 AI 的所有内容&#xff0c;并在这个奇妙的 GenAI 领域开始他们的旅程。我将告诉你从Python到机器学习&#xff0c;然后是深…

多线程案例(3)-定时器

文章目录 多线程案例三三、 定时器 大家好&#xff0c;我是晓星航。今天为大家带来的是 多线程案例三 相关的讲解&#xff01;&#x1f600; 多线程案例三 三、 定时器 定时器是什么 定时器也是软件开发中的一个重要组件. 类似于一个 “闹钟”. 达到一个设定的时间之后, 就…

Python Opencv实践 - 基本图像IO操作

import numpy as np import cv2 as cv import matplotlib.pyplot as plt#读取图像 #cv2.IMREAD_COLOR&#xff1a; 读取彩色图像&#xff0c;忽略alpha通道&#xff0c;也可以直接写1 #cv2.IMREAD_GRAYSCALE: 读取灰度图&#xff0c;也可以直接写0 #cv2.IMREAD_UNCHANGED: 读取…

SQL ASNI where from group order 顺序

SQL语句执行顺序&#xff1a; from–>where–>group by -->having — >select --> order 第一步&#xff1a;from语句&#xff0c;选择要操作的表。 第二步&#xff1a;where语句&#xff0c;在from后的表中设置筛选条件&#xff0c;筛选出符合条件的记录。 …

JavaScript实践:用Canvas开发一个可配置的大转盘抽奖功能

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;全栈领域新星创作者✌&#xff0c;阿里云社区专家博主&#xff0c;2023年6月csdn上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &#x1f3c6;本文已…

【瑞吉外卖项目复写】基本部分复写笔记

Day1 瑞吉外卖项目概述 mysql的数据源配置 spring:datasource:druid:driver-class-name: com.mysql.cj.jdbc.Driverurl: jdbc:mysql://localhost:3306/regie?serverTimezoneAsia/Shanghai&useUnicodetrue&characterEncodingutf-8&zeroDateTimeBehaviorconvertTo…

【C++】深入浅出STL之vector类

文章篇幅较长&#xff0c;越3万余字&#xff0c;建议电脑端访问 文章目录 一、前言二、vector的介绍及使用1、vector的介绍2、常用接口细述1&#xff09;vector类对象的默认成员函数① 构造函数② 拷贝构造③ 赋值重载 2&#xff09;vector类对象的访问及遍历操作① operator[]…

windows永久暂停更新

目录 1.winr,输入regedit打开注册表 2.打开注册表的这个路径: 计算机\HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsUpdate\UX\Settings 右键空白地方新建QWORD值命名为:FlightSettingsMaxPauseDays 3.双击FlightSettingsMaxPauseDays,修改里面的值为100000,右边基数设置…

区块链实验室(14) - 编译FISCO-BCOS

FISCO-BCOS是一种区块链平台&#xff0c;与Hyperledger和Ethereum有些不同&#xff0c;详见FISCO BCOS 区块链 编译FISCO BCOS源码的目的是修改或者新增其中功能模块&#xff0c;进行对比实验&#xff0c;验证新想法、新创意的效果。编译的步骤很简单&#xff0c;按技术文档一…

JavaWeb三大组件 —— Servlet

目录 servlet 注册servlet 父pom pom文件 1、通过注解注册 2、使用ServletRegistrationBean注册 API三生三世 第一生Servlet 第二生SpringMVC 今生SpringBoot servlet Servlet的作用&#xff1a; 接受请求参数、处理请求&#xff0c;响应结果&#xff0c;&#xff08;就…

flask中的应用上下文

flask中的应用上下文 Flask应用上下文主要包含两个对象&#xff1a;current_app和g。这两个对象在处理请求期间都是全局可访问的&#xff0c;但在每个请求结束时都会被重置。 current_app&#xff1a;这是当前激活的Flask应用的实例。在大多数情况下&#xff0c;你可以将其视为…

回归预测 | MATLAB实现SO-CNN-GRU蛇群算法优化卷积门控循环单元多输入单输出回归预测

回归预测 | MATLAB实现SO-CNN-GRU蛇群算法优化卷积门控循环单元多输入单输出回归预测 目录 回归预测 | MATLAB实现SO-CNN-GRU蛇群算法优化卷积门控循环单元多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现SO-CNN-GRU蛇群算法优化卷积门控循…

go-zero超强工具goctl的常用命令api,rpc,model及其构建的服务解析

goctl api 详情移步&#xff1a; go-zero的路由机制解析 基于go-zero的api服务刨析并对比与gin的区别 goctl rpc goctl支持多种rpc&#xff0c;较为流行的是google开源的grpc&#xff0c;这里主要介绍goctl rpc protoc的代码生成与使用。 protoc是grpc的命令&#xff0c;作用…

uniapp uview文件上传的文件不是文件流,该如何处理?用了uni.chooseImage预览功能要如何做

在使用uniapp开发&#xff0c;运用的ui是用uview&#xff0c;这边需要做一个身份认证&#xff0c;如下图 使用的是uview的u-upload组件&#xff0c;可是这个组件传给后端的不是文件流 后端接口需要的是文件流格式&#xff0c;后面使用了uniapp的选择图片或者拍照的api&#x…

UltraToolBars Crack,动画菜单和多种显示样式

UltraToolBars Crack,动画菜单和多种显示样式 创建模仿Microsoft Office 2000外观的健壮应用程序。 UltraToolBars包括11个用于创建可自定义工具栏的界面增强控件&#xff0c;包括&#xff1a;个性化菜单、弹出型工具栏、集成选项卡控件等。PictureRegion技术使表单和组件能够采…

实现vscode上用gdb调试stm32

实现vscode上用gdb调试stm32 这周负责编写设备的某个模块&#xff0c;其中遇到了一些变量地址不正确的错误&#xff0c;按理这种底层变量错误用gdb一类的调试器就能很快查到&#xff0c;可是初入嵌入式一行&#xff0c;此C语言非彼C语言&#xff0c;对于gdb怎么对接到项目上根…